I have developed a very large LP model (let's call it Model 1), which has been solved using primal simplex method provided by CPLEX.
Now I am considering using Bender decomposition to break down the LP model into two separate LP models. The master problem is a normal LP problem without integer constraint, while the worker LP is a standard 01 integer problem. I have a few questions about how to do this using CPLEX.
1) How to utilise Model 1 to generated the worker LP? I can split Model 1 into two LP appropriately, but both the LP problems will be in primal form. I understand the worker LP should be in dual form, and then I can use its solution to generate Bender's cuts. Is there a CPLEX function which can convert a LP model in primal form into dual form? As my model is very large, the manual conversion will be very difficult. Further, if there exists such a function, how can I trace the corresponding relation (or matchup) of the constraint in primal form and decision variables in dual form.
2)I am also thinking of an alternative method, which may need not generate the dual problem for the worker LP. I noticed that CPLEX provide a getduals() function. Shall I just use primal simplex method to solve the worker LP in primal form, and then use getduals() to get the solutions of dual problem. My workder LP is always feasible regardless of the solution of master problem, and there always exist solutions to dual problem. However, as the workder LP is 01 problem, does the getduals() function return a solution which make sense. I heard that MIP has no duals. :(
Many thanks for reading the long message. Your help will be highly appreciated.
Topic
This topic has been locked.
5 replies
Latest Post
 20130203T15:04:33Z by JasonDonne
ACCEPTED ANSWER
Pinned topic A few questions about Bender decomposition
20130131T14:44:44Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20130203T15:04:33Z at 20130203T15:04:33Z by JasonDonne

ACCEPTED ANSWER
Re: A few questions about Bender decomposition
20130131T17:19:23Z in response to JasonDonneHello,
Usually the master problem is an integer ILP model and worker problem is a continuous LP model. For example, in FAM, master could give a fleet assignment for which revenue would be computed using the worker problem or something like ATSP problem found here:
http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.studio.help%2FCPLEX%2FReleaseNotes%2Ftopics%2Freleasenotes123%2Freleasenotescplex123_22.html
All CPLEX's LP optimizers like primal/dual simplex and barrier would give you the optimal dual solution for the optimal primal solution. But if you still would like to solve the dual LP instead of primal LP, then that is still possible and relatively easy. You don't have to do it manually. CPLEX allows you to write down the dual form of an LP to a file. Then you could read that file back into your program again in a new problem object.
It's correct that there are no duals available for a MIP so if you could make your worker model as a LP, then it should be possible to get duals which you could use to generate cuts for the master problem.
Dr. Paul Rubin has some good references related to Benders you might find useful here:
http://orinanobworld.blogspot.in/2011/10/bendersdecompositionthenandnow.html
http://orinanobworld.blogspot.in/2012/07/bendersdecompositionincplex.html
http://orinanobworld.blogspot.in/2012/09/separablebendersdecomposition.html
Hope it helps!
Regards,
Vivek.
ACCEPTED ANSWER
Re: A few questions about Bender decomposition
20130131T20:18:37Z in response to SystemAdminHello Vivek,
I greatly appreciate your information. I've read Paul's blog. It looks to me that he used getduals() to get the solutions of dual problem, which is the second option in my first post.
As my worker problem is a complicated 01 integer programming, it cannot be relaxed to a continuous LP. Does it mean I could not use Benders decomposition for my problem? I am also very curious to know what getduals() will return if I use CPLEX solve a 01 programming problem.
Many thanks.
ACCEPTED ANSWER
Re: A few questions about Bender decomposition
20130131T22:41:51Z in response to JasonDonne> JasonDonne wrote:
> As my worker problem is a complicated 01 integer programming, it cannot be relaxed to a continuous LP. Does it mean I could not use Benders decomposition for my problem?
Correct: Benders is off the table. The reason is that it relies on LP duality, which doors not apply to an IP.
> I am also very curious to know what getduals() will return if I use CPLEX solve a 01 programming problem.
I think it throws an exception, but I'm not positive. I am positive that it will not return anything useful. With a MIP, you can fix the integer variables at their optimal values, solve the reduced problem as an LP, and use getduals() to get dual values that apply to the restricted LP, but that is typically not useful.
Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
ACCEPTED ANSWER
Re: A few questions about Bender decomposition
20130202T06:17:21Z in response to SystemAdmin> I think it throws an exception, but I'm not positive.
I get this when I use CPXgetpi() in C callable library which is the equivalent of getduals() in concert.
CPLEX Error 1017: Not available for mixedinteger programs.
Regards,
Vivek.
ACCEPTED ANSWER
Re: A few questions about Bender decomposition
20130203T15:04:33Z in response to SystemAdminGreat thanks to Paul and Vivek. Cheers.



