Questions Tagged With cuthttp://www.or-exchange.com/tags/cut/?type=rssquestions tagged <span class="tag">cut</span>enTue, 16 Jan 2018 23:49:07 -0500Slow Convergence with Benders Decomposition Algorithmhttp://www.or-exchange.com/questions/15279/slow-convergence-with-benders-decomposition-algorithm<p>I have been trying to solve a large MILP with Benders Decomposition. I cannot solve its original MILP formulation as such, since it is a really huge problem with 2.8 Million (1.9 Million continuous & 0.9 Million integer) variables and 2.5 Million constraints. CPLEX doesnt start until quite a long time and then it runs outs of memory. In the application of BD algorithm: The subproblem solves in 3 minutes. The master problem in its integer form takes quite a bit of time to solve, and hence I chose to relax the integrality until the gap between LB and UB is within a certain limit before solving the MP with integrality applied. So the relaxed MP takes around 3 minutes per iteration. Hence per iteration I lose around 8 minutes. The initial movement of UB (the problem is a maximization problem) to a lower number is pretty fast then the algorithm goes on with relatively small improvement in UB and LB, and takes forever to converge 400 iterations and more (around 3 days).</p>
<p>I tried implementing the Independent Magnanti Wong method, and multiple cut insert per iteration (generated out of multiple answers for the degenerate sub problem), and none of those have helped in faster convergence. Maybe the problem I am trying to solve is too big for even Benders Decomposition to help solve in a 16GB RAM, i7-2600 CPU <a href="/users/72/3d-brille-kaufen">@3</a>.4 GHz. Or maybe the structure of the problem is not conducive for Benders Decomposition to help. The sub problem has the following structure to it:</p>
<p>\(\begin{align*}
\mathrm{max } \sum_w Output_w \\
\mathrm{st\quad}
\sum_i (c_{i}x_{i})_{w} & = Output_w \quad \forall w,grp , i \subset grp \\
\sum_i x_i & \le y_i \quad \forall i
\end{align*}\)</p>
<p>Where the problem is to maximize Output which is basically a maximization of the minimum of output from different groups. The constraint shown above is not the only constraint, but is the main one. I wonder if the max-min structure of the problem does not work well with Benders Decomposition. </p>
<p>Another doubt I have is with Regards to M-W method. The way I was choosing the core point was to run a solve on the relaxed Master problem, in each iteration, and use the values from the solution as core point. I have a ton of equality constraints in the Master Problem formulation. Is that not conducive to the application of M-W method?</p>
<p>Any help related to these doubts would be greatly appreciated. I basically want to know if I should give up on applying Benders Decomposition, or whether there is more that I need to learn on re-formulation of the problem or other acceleration techniques, before I jump to other heuristics to solve the optimization problem.</p>Naveen DivakaranTue, 16 Jan 2018 23:49:07 -0500http://www.or-exchange.com/questions/15279/slow-convergence-with-benders-decomposition-algorithmbenders-decompositioncutmagnanti-wongmilpGomory cuts with integral coefficientshttp://www.or-exchange.com/questions/12888/gomory-cuts-with-integral-coefficients<p>Hi, I am trying to learn how to generate cutting planes within a Branch and Bound algorithm to solve a 0-1 Integer Program. I read that Gomory cuts could be written as:</p>
<p>sum(i) (a[i,j] - floor(a[i,j])) x[i,j] >= b[j] - floor(b[j]), forall j </p>
<p>where x[i,j] is a binary variable and floor() is a rounding down function.</p>
<p>However, if I have a constraint of the type: </p>
<p>sum(i) x[i,j] = 1, forall j </p>
<p>is it possible to generate a Gomory cut from this constraint that is different from the constraint? Because all the coefficients and the right-hand side term are equal to 1, it seems that rounding will not help at all (the Gomory cut would then be identical to the original constraint) but I feel that I am missing something.. </p>
<p>If my definition of a Gomory cut is correct, then this seems to imply that any constraint with integral coefficients and RHS would not be able to be used to create a such a cut, is this true?</p>
<p>thanks</p>davidrey123Mon, 19 Oct 2015 01:10:47 -0400http://www.or-exchange.com/questions/12888/gomory-cuts-with-integral-coefficientscutgomory-cutscuttingplanecombinatorial benders cuts in l-shapedhttp://www.or-exchange.com/questions/12510/combinatorial-benders-cuts-in-l-shaped<p>I am working on a two-stage stochastic program where the master is a mip model, and slaves only have continuous variables.
For each scenario, I pass three variables set (k, a, b: first stage decisions, all binary) from master to slave. Then stochastic parameters realize. The slave problem has M constraints between decision variables a,b and contiunous s,c,x variables (slave variables). The first stage variable k is not in any M constraint in the slave problem, but it constraints s,c variables.</p>
<p>I have two questions:
1. With these conditions, can I use combinatorial benders cuts in the form: a(sum where/=1)+(1-a)(sum where/=0)+b(sum where/=1)+(1-b)(sum where/=0) >= 1 for this problem?
2. I havent seen any papers using combinatorial benders cuts in stochastic programming to generate feasibilty cuts. Are there any other conditions? Since we generate feasibility cuts for each scenario subproblem, I believe we can use these cuts as feasibility cuts for l-shaped algorithm.</p>
<p>Thanks for the help in advance.</p>paretSat, 13 Jun 2015 08:43:08 -0400http://www.or-exchange.com/questions/12510/combinatorial-benders-cuts-in-l-shapedbenders-decompositionstochastic-optimizationcutdecompositionK-cut with enemy constraintshttp://www.or-exchange.com/questions/7619/k-cut-with-enemy-constraints<p>Is there a way of solving(approximate or exact) a min-k-cut problem with the additional constraint that certain pairs of vertices cannot be in the same partition .</p>prateekFri, 15 Mar 2013 06:30:30 -0400http://www.or-exchange.com/questions/7619/k-cut-with-enemy-constraintscutModeling on special cut problem with directed flowhttp://www.or-exchange.com/questions/6151/modeling-on-special-cut-problem-with-directed-flow<p>I have a problem which is to find a cut from a set of items. However, the flow between the cut is directed, and the objective function is to find the smallest accumulated flow between the cut, but the accumulated flow is defined as the larger one between the two directions. </p>
<p>For instance, if I have three items \(A\), \(B\) and \(C\). if the optimal cut is \(AB|C\), then \(\max\,(f_{AC} + f_{BC} , f_{CA} + f_{CB})\) should be smaller than any other case, say the one for cut \(A|BC\). (\(f\) is the known flow value between two items.)</p>
<p>To model this case as a MIP, I think a lot more indicators are needed. For instance, one needs to model the flow for both diretions, so each item pair will need two indicators and maybe two constraints.</p>
<p>For instance, for pair \((A,C):\; f_{AC} \times I_{AC};\; f_{CA} \times I_{CA}\) where \(I_{CA} \ge X_{C} - X_A + \frac{1}{2}\), \(I_{CA}\) is binary and \(I_{AC}\) ... so only when \(X_C = 1, X_A = 0\) then \(I_{CA} = 1\).</p>
<p>The issue is that when the number of itmes is big, the constraint matrix becomes too big as at least for me it seems i need to model all item pairs, so it brings me a lot of additional variables.</p>
<p>So is there a workaround on reducing the number of variables? Or... is a linear formula the best choice?</p>jc WMon, 06 Aug 2012 22:19:07 -0400http://www.or-exchange.com/questions/6151/modeling-on-special-cut-problem-with-directed-flowmipcutmodeling