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%20Divakaran's gravatar image

Naveen Divak...
7418
accept rate: 25%

edited 17 Jan '18, 15:47

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412


I think M-W should work in the presence of equality constraints, but the key is to get a starting point in the relative interior (not boundary) of the feasible region. It's not clear from your description that you do so. If your core point is a solution to the LP relaxation, that will be on the boundary of the (relaxed) feasible region, not in the relative interior.

link

answered 17 Jan '18, 15:49

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thank you Paul for your response. Maybe I am not understanding the requirement of a core point very well. Doesnt the core point require there to be a strictly positive slack on all constraints? In the case of equality constraints would there be positive slack for a feasible point?

(17 Jan '18, 17:30) Naveen Divak...
1

With equality constraints, there cannot be any slack. The key is that M-W want the core point to be in the relative interior of the integer hull. (Strictly positive slack on all constraints, including sign restrictions, would put you in the interior ... which the feasible region of a problem with equation constraints does not have.) I just tried to explain this in a blog post.

(17 Jan '18, 18:19) Paul Rubin ♦♦

This is awesome. Thank you Paul for the blog post that helped enlighten me about core point. I will give your recommendation a try, and get back to you in a few days on what happened after trying it out. I bet my LP relaxation method ended up getting points outside of the relative interior of Integer hull, and thus did not help with the convergence.

(18 Jan '18, 01:38) Naveen Divak...

I am a bit confused by the Independent Magnanti Wong Algorithm (based on paper: "Practical enhancements to the Magnanti–Wong method" Algorithm 3), where you dont have to solve the sub problem to generate the Pareto-optimal cut. Based on that algorithm, it seems like I'll have to find different core points every iterations or else I wouldnt be able to generate different cuts as every element - (A), (c^T),& (b) - in the Independent Magnanti-Wong problem is the same if I do not change the core point (y_0). Am I right?

(18 Jan '18, 01:46) Naveen Divak...

I posted a couple more options (and some explanations) on my blog today. Personally, I think the best chance for getting a relative interior point of the integer hull is to both maximize and minimize one or more objective functions over the LP relaxation, then average the solutions. The maximizer and minimizer of any function will tend to be on "opposite sides" of the integer hull, so their mean stands a good chance to be inside it.

(18 Jan '18, 16:23) Paul Rubin ♦♦

Thanks! What are your thoughts on the Independant Magnanti Wong Algorithm? I am not sure if I understand it completely. My doubts are in the previous comment.

(18 Jan '18, 16:39) Naveen Divak...

If I take a feasible solution from the Relaxed Master Problem, and use the half of the solution vector as core point, is it correct? Any ways that approach also did not help me accelerate convergence.

Does the core point always have to be found in the beginning of the algorithm?

(22 Jan '18, 10:50) Naveen Divak...

I am not going to use this forum as a discussion board as has been stated in the rules of this forum. Hence even though I have'nt been able to accelerate the benders decomposition for my problem, I will mark this complete since Professor Paul Rubin helped me understand what core point is and what are the different ways in which it can be found. I will put more questions later that wont appear like discussions going forward.

(22 Jan '18, 12:06) Naveen Divak...
1

As far as I know, a core point needs to be found before adding any Benders optimality cuts - not necessarily at the outset, and not necessarily when Benders feasibility cuts (which do not use the core point) are created. I think you can change core points at will. As for taking 0.5 * feasible solution, that may well be a suitable core point, provided that it is feasible in the relaxation (which it will be if the zero solution is feasible).

(22 Jan '18, 13:47) Paul Rubin ♦♦
1

@Naveen We (the CPLEX team) would be interested in your model instance, if it's possible to share, please send me an email bo.jensen (at) dk.ibm.com

(23 Jan '18, 03:06) Bo Jensen ♦
showing 5 of 10 show 5 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×35
×16
×5
×3

Asked: 16 Jan '18, 23:49

Seen: 301 times

Last updated: 23 Jan '18, 03:06

OR-Exchange! Your site for questions, answers, and announcements about operations research.