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?
Hossein
Benders (linear) decomposition is a nice and elegant method designed to tackle with mixed-integer programming problems "with a especial structure", i.e. by fixing a set of "complicating variables" the resultant linear subproblem(s) becomes easier to solve. The optimal dual variables of the subproblem are then used to construct a Benders cut added to the master problem which is solved again. The iteractive scheme evolves until an acceptable tolerance is reached. This is possible because subproblems give us an upper bound (min problems) and master gives us a lower bound. If this difference is less than tolerance, the method finishes. I would say you have chosen the wrong method for solving your problem, since in the first case your master is too hard, and in the second one your subproblem contains "complicating" integer variables yet.
Dear prof. Paulo França,
I also encounter a large-scale MIP problem which has block-angular structure. Could you please recommend any document that describes the above technique ? It's more wonderful if it has examples and code.
Sincerely,
Phuong.
Dear Phuong
Benders method is described in details in the seminal paper (attached) and also in L. Lasdon book (Lasdon, Leon S. (2002). Optimization theory for large systems (reprint of the 1970 Macmillan ed.). Mineola, New York: Dover Publications, Inc.). An interesting Benders decomposition application can be found in Geoffrion's paper (attached). A tutorial with examples can be found in Taskin (attached).
Dear prof. Paulo França,
Thank you so much for your kindly support.
Yours sincerely,
Phuong.
If your MIP subproblem is a pure binary IP (or can be reformulated as it), you can do a similar decomposition with combinatorial "no-good" cuts instead of Benders cuts. It depends on the problem whether it will work or not (computationally). Search internet for "Logic-based Benders decomposition".
I think column and constraints generation would have been a better approach
- Badges
- Science topic
- Similar topics
- Linguistics
- Composition Studies
- Writing