Topic
5 replies Latest Post - ‏2013-02-03T15:04:33Z by JasonDonne
JasonDonne
JasonDonne
9 Posts
ACCEPTED ANSWER

Pinned topic A few questions about Bender decomposition

‏2013-01-31T14:44:44Z |
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 0-1 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 0-1 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.
Updated on 2013-02-03T15:04:33Z at 2013-02-03T15:04:33Z by JasonDonne
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: A few questions about Bender decomposition

    ‏2013-01-31T17:19:23Z  in response to JasonDonne
    Hello,

    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/benders-decomposition-then-and-now.html
    http://orinanobworld.blogspot.in/2012/07/benders-decomposition-in-cplex.html
    http://orinanobworld.blogspot.in/2012/09/separable-benders-decomposition.html

    Hope it helps!

    Regards,
    Vivek.
    • JasonDonne
      JasonDonne
      9 Posts
      ACCEPTED ANSWER

      Re: A few questions about Bender decomposition

      ‏2013-01-31T20:18:37Z  in response to SystemAdmin
      Hello 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 0-1 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 0-1 programming problem.

      Many thanks.
      • SystemAdmin
        SystemAdmin
        7929 Posts
        ACCEPTED ANSWER

        Re: A few questions about Bender decomposition

        ‏2013-01-31T22:41:51Z  in response to JasonDonne
        > JasonDonne wrote:

        > As my worker problem is a complicated 0-1 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 0-1 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)
        • SystemAdmin
          SystemAdmin
          7929 Posts
          ACCEPTED ANSWER

          Re: A few questions about Bender decomposition

          ‏2013-02-02T06: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 mixed-integer programs.

          Regards,
          Vivek.
          • JasonDonne
            JasonDonne
            9 Posts
            ACCEPTED ANSWER

            Re: A few questions about Bender decomposition

            ‏2013-02-03T15:04:33Z  in response to SystemAdmin
            Great thanks to Paul and Vivek. Cheers.