Originally posted by: clemsonmacrone

Hi, I am working on a customized branch and bound technique for an integer based multicommodity flow problem.

What I am trying to do, and I'm not sure if cplex can do this, but I want used column generation to solve the relaxation. Then implement my customized branching technique using branch callback to create two new subproblems with added constraints. Then solve the subproblem again with column generation, taking into account the new constraints and continue doing this until I get the optimal solution.
I am familiar with branch callback and with column generation but I'm not sure how to combine them like this or if it is even possible

thanks for reading

Cam
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Unfortunately, CPLEX does not support branch-and-price. Once you start a MIP solve, you cannot add more variables to the problem.

What you could do is to solve the MIP to optimality and then add columns based on the integer optimal solution (but you would not get duals for this). Then, resolve the new MIP and iterate. But this is very impractical for most applications.

Sometimes it is possible to cast a branch-and-price approach into a Bender's decomposition approach. In your case, this would mean to formulate the multicommodity flow problem with a compact model (i.e., use arc based variables instead of path based variables). Then, at each node you might be able to solve the subproblem by column generation in the extended space of path variables and then derive stronger dual bounds and Bender's cuts from the solution of the column generation problem to tighten the compact formulation at the node.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

I have had some success using this:

http://www.mathworks.com/matlabcentral/fileexchange/25259-linear-mixed-integer-program-solver

It is a basic branch and bound algorithm. Has a few options (breadth-first, depth-first, etc...) but not nearly the sophistication of Cplex. However, you can easily take control of the subproblems and do column generation, using cplex to solve the LPs. Just letting you know what I did.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Another option would be to use SCIP, see scip.zib.de.
SCIP is one of the fastest non-commercial MIP solvers, but it supports a lot of additional features to MIP, including column generation and branch-and-price.
If you really need to use branch-and-price, I would definitely take a look. The developers are very supportive, and you can link to CPLEX for solving the LP relaxations.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: clemsonmacrone

Thanks for the help.

I am interest in your idea for the Bender's decomposition approach.
My branching rules are based on the compact model and I have written the code to implement the branching rules using this method but my next step is to extend this rule to branch and price using column generation.

For example, one of my branching rules that I implement is to find a commodity with non-integer flow from source to sink and find an arc along that path where the flow is non integer and set that arc to one or zero for the two branches.
The path model for the sub-problem would then be all paths that include that arc, or do not include that arc.

How would I go about telling cplex to solve the the subproblems in extended space of path variables?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: clemsonmacrone

Slight typo when describing the branch and bound rule I'm implementing
When I wrote "set that arc equal to one or zero" I meant to say "set the flow variable of that commodity corresponding to the arc with fractional flow equal to one or zero."
Similarly, the path model would be all paths of that commodity with flow going through that arc or not going through that arc
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The sub problem would probably be solved as usual as a linear program. The question is how you would solve your pricing problem.

Branching on a single arc is often not such a good idea in branch-and-price network flow problems. The reason is that often the pricing problem is a shortest path problem. When you now branch on an arc, you need to introduce this branching into the pricing problem. In the down branch (forbid all paths that use the arc) this is not a problem: just remove the arc from the graph and solve a shortest path problem in the reduced graph. But in the up branch (only paths are allowed that use this arc) the pricing problem becomes (as far as I know) exponential in the number of arcs that you have fixed.

For this reason, people often use something like Ryan-Foster branching. If you have a constraint that you have to use exactly one incoming (or outgoing) arc for each node, then you can branch on the set of incoming (outgoing) arcs. Split the set into two subsets S1 and S2 such that the sum of LP values in S1 is fractional (and hence also in S2, since the sum of the two will always be 1), and in the left child fix all S1 arcs to zero, while in the right branch fix all S2 arcs to zero. This gives a branching split that keeps the easy shortest path pricing problem in both subproblems.
Tobias
#CPLEXOptimizers
#DecisionOptimization