# Slow Convergence with Benders Decomposition Algorithm

 0 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). 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 @3.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: \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*} 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. 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? 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. asked 16 Jan '18, 23:49 Naveen Divak... 74●1●8 accept rate: 25% Paul Rubin ♦♦ 14.6k●4●12

 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: