I encounter with a big MIP model. I have two ideas to decomposing it. The first one is to decompose it to IP and LP problems. The second one is to decompose the mode to two MIPs. The first decomposition is not good for me since the IP is also too big. I want to use my second idea. However, when I solve optimally the MIP sub-problem, the all generation dual variable becomes zero. So, I can not add any benders cut to the MIP master. What is the wrong?

asked 22 Oct '13, 09:26

hkarimi's gravatar image

accept rate: 0%

There have been a few papers in the airline literature that have applied Benders' decomposition with MIPs in the master and subproblem. These papers are Cordeau et. al., Mercier et. al. and Papadakos. The main approach to handle the integer variables in the subproblem is to employ a heuristic three-phase method.

The three-phase method involves: 1. Relax all integrality requirements in the master and subproblem. Solve to optimality to obtain a lower bound (assuming minimisation). 2. Retaining all cuts from phase 1, reintroduce integrality on the master problem variables. Solve to optimality. 3. Reintroduce integrality to the subproblem and test for feasibility.

While this doesn't solve the subproblem to integer optimality, it has been shown in the above papers to have a small optimality gap. Additionally, this approach allows you to generate good cuts quickly in phase 1 that will help reduce the solution runtimes.


answered 27 Oct '13, 19:48

Stephen%20J%20Maher's gravatar image

Stephen J Maher
accept rate: 75%

MIPs don't have dual values. If you want an integer subproblem, then you need to use a technique like combinatorial or logical benders where you don't use duals to generate the cut. You can find an early paper by John Hooker on this here.


answered 22 Oct '13, 10:23

Mike%20Trick's gravatar image

Mike Trick ♦♦
accept rate: 21%

Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 22 Oct '13, 09:26

Seen: 2,433 times

Last updated: 27 Oct '13, 19:48

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