Topic
  • 4 replies
  • Latest Post - ‏2013-03-05T09:12:16Z by SystemAdmin
SystemAdmin
SystemAdmin
754 Posts

Pinned topic Branch and Price

‏2013-02-06T15:04:42Z |
Dear All,

I'm doing my research on Location-routing problem by using branch and price (exact solution). I tried to use purely OPL by following Cutting stock example (in my case I used Shortest path for sub-problem). However, I realized that the column could not be added on the fly. After review for the solutions, I (think) have only 2 options.

1. Start on C++ platform and borrow CPLEX library (like cutstock.cpp)
2. Use other framework i.e. ABACUS, BCP, MINTO, SCIP, or Symphony

I have zero knowledge on those two. Could you recommend which approach should I go. Your suggestions are highly appreciated

Best,

Tong
Updated on 2013-03-05T09:12:16Z at 2013-03-05T09:12:16Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and Price

    ‏2013-02-06T22:59:42Z  
    Option 1 will not help; the inability to add columns on the fly is a limitation in CPLEX, not in OPL.

    For option 2, the three COIN-OR projects (ABACUS, BCP and Symphony) all use the COIN-OR Open Solver Interface, which means they can link to CPLEX and use CPLEX as the LP solver in a branch-cut-price approach. They'll all require C++ programming. I'm pretty sure MINTO can also use CPLEX as its solver. I'm not sure if SCIP can, but then I think SCIP comes with a pretty good solver of its own.

    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
    754 Posts

    Re: Branch and Price

    ‏2013-02-07T06:22:55Z  
    Option 1 will not help; the inability to add columns on the fly is a limitation in CPLEX, not in OPL.

    For option 2, the three COIN-OR projects (ABACUS, BCP and Symphony) all use the COIN-OR Open Solver Interface, which means they can link to CPLEX and use CPLEX as the LP solver in a branch-cut-price approach. They'll all require C++ programming. I'm pretty sure MINTO can also use CPLEX as its solver. I'm not sure if SCIP can, but then I think SCIP comes with a pretty good solver of its own.

    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)
    Thanks a lot Rubin. As you suggested, I will work on 2nd option. I think SCIP might be a good starting point.
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and Price

    ‏2013-02-13T08:27:59Z  
    Thanks a lot Rubin. As you suggested, I will work on 2nd option. I think SCIP might be a good starting point.
    What you can do with CPLEX is the following:

    1. Solve the LP relaxation of your (restricted) problem.
    2. Generate new columns using the dual solution. If found, go to 1.
    3. Reintroduce integrality into the final problem and solve it as a MIP.

    optional:
    4. Go back to the LP relaxation and fix all integer variables to the values of the optimal MIP solution (as if you were doing branching and "incidentally" found the solution somewhere deep in the tree).
    5. Generate new columns using the dual solution of this fixed LP as if you were applying your pricing procedure on the local search tree node associated with the fixings.
    6. If new columns have been found, go to 3.

    Of course, this is just a heuristic and will not necessarily yield the optimal solution to your problem. The MIP solutions will be feasible, and the LP bound from 1-2 will provide a dual bound, so you can assess the quality of the solution. But the gap may not be zero.
    Tobias
  • SystemAdmin
    SystemAdmin
    754 Posts

    Re: Branch and Price

    ‏2013-03-05T09:12:16Z  
    What you can do with CPLEX is the following:

    1. Solve the LP relaxation of your (restricted) problem.
    2. Generate new columns using the dual solution. If found, go to 1.
    3. Reintroduce integrality into the final problem and solve it as a MIP.

    optional:
    4. Go back to the LP relaxation and fix all integer variables to the values of the optimal MIP solution (as if you were doing branching and "incidentally" found the solution somewhere deep in the tree).
    5. Generate new columns using the dual solution of this fixed LP as if you were applying your pricing procedure on the local search tree node associated with the fixings.
    6. If new columns have been found, go to 3.

    Of course, this is just a heuristic and will not necessarily yield the optimal solution to your problem. The MIP solutions will be feasible, and the LP bound from 1-2 will provide a dual bound, so you can assess the quality of the solution. But the gap may not be zero.
    Tobias
    Thanks a lot for your recommendation Tobias. However I have only a choice is to maintain my research objective using exact algorithm. I might try SCIP as you recommended in another topic.

    I'm not sure if I wish one day CPLEX would include branch and price (and cut).

    Thank you
    Tong