Originally posted by: SystemAdmin

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
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

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)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks a lot Rubin. As you suggested, I will work on 2nd option. I think SCIP might be a good starting point.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

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
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

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
#DecisionOptimization
#MathematicalProgramming-General