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
Re: Branch and Price2013-02-06T22:59:42ZThis is the accepted answer. This is the accepted answer.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.
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)
Re: Branch and Price2013-02-13T08:27:59ZThis is the accepted answer. This is the accepted answer.
- SystemAdmin 110000D4XK
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.
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.
Re: Branch and Price2013-03-05T09:12:16ZThis is the accepted answer. This is the accepted answer.
- SystemAdmin 110000D4XK
I'm not sure if I wish one day CPLEX would include branch and price (and cut).