Originally posted by: waldstein

Classicly, a branching constraint will be inserted to original model and the model will be solved by column generation. My question is : Should the column generation process consider the branching constraints? e.g., in a classic multicommodity network flow problem?

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Please note that CPLEX does not support branch-and-price: you cannot add new columns during a MIP solve. What you can do with CPLEX is what people often just call "column generation": you solve the LP relaxation, generate new columns, and iterate. At some point you stop (e.g., you have solved the LP to optimality) and then just convert the variables to binary or integer as needed and solve the resulting problem as a MIP. Of course, this will not necessarily produce an optimal solution to your problem since you are ignoring all the columns that were not needed for the root LP solve. But as a heuristic, this procedure is often useful.

Another heuristic approach that you can do with CPLEX is branch-and-generate. Here you would basically implement branching yourself and only use CPLEX as LP solver: solve the LP relaxation with column generation as before, then manually change bounds or introduce other branching constraints, resolve with column generation and continue like this.

If you really want to do branch-and-price, then you have to use a branch-and-price framework. For example, you could use SCIP: http://scip.zib.de
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Thanks!
I used CPLEX as a solver for solveing LP in branch and price process. I can also use other solve to do this. The major branch and price procedure is implemented by other language.
So the problem is not related to CPLEX, but the very process of column generation in the B&B.

Let me explain my problem in detail:
In a certain node of branch and bound, we obtain another two node. The branching constraint (like x <= 0 or x >=1) will be inserted to original model, which was solved by column generation. The two new models have branching constraints and it is slightly different with the original one. Could the column generation solve the two new models as it solved the original one?

Thanks again!

Bao Hua
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Ah, now I understand the question, which is not really related to CPLEX.

This is one of the fundamental issues for branch-and-price. Namely, you need to use a branching rule that is compatible with your pricing algorithm. For example, if your problem is specified on a directed graph, the variables are binary and each of them says whether you would use a path in the graph (i.e., a set of arcs) or not. The pricing problem is the shortest path problem using the dual solution as weights on the arcs.
Now at the root node, everything is clear: you just query the dual solution, calculate the arc weights, and call a shortest path algorithm to check if there exists a path of negative length (which means negative reduced costs in the LP). If so, add the path as variable to the problem and resolve.

Now branching on a single variable (i.e., ruling out a certain path on the one side, and explicitly forcing to use a path on the other side) gives you issues in the pricing problem of the child node, in particular the one where you rule out the path. If you force the path you may be able to modify the graph accordingly to get back again into the situation where the pricing can be solved via the shortest path problem in a modified graph. But for the case where you rule out the graph, the pricing problem would be the shortest path problem excluding one particular solution. This means, the resulting pricing problem is the 2-shortest paths problem: the shortest path could be the one that you ruled out, so you need the second shortest path as well. And if you continue branching, you will get the k-shortest path problem, which is exponential in k. So, you have killed the performance of your pricing problem.

For this reason, you often want to branch, e.g., on the set of outgoing arcs of a node (say, you have to use exactly one of those arcs). Split the set into two subsets S and T. On the one side of the branching you want to rule out the arcs of S (i.e., only those paths are valid that do not use those arcs), on the other side you want to rule out the paths that go through arcs in T. Now the pricing problem stays simple: just remove the respective arcs from the graph in the pricing problem of each of the children, and the problem stays a simple shortest path problem. This type of branching is called Ryan-Foster or "follow-on" branching.

So, as a summary, in branch-and-price applications the pricing problem and the branching rule are tightly connected. A nice pricing algorithm does not help if you do not have a compatible branching rule.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Tobias,

thanks very much!

Your example is similar to my problem!

You were saying "But for the case where you rule out the graph, the pricing problem would be the shortest path problem excluding one particular solution. This means, the resulting pricing problem is the 2-shortest paths problem: the shortest path could be the one that you ruled out...."

How to know "the shortest path could be the one that you ruled out"? Is there any proposition for this?

bao hua
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You cannot know in advance. It just could be that the shortest path algorithm that you apply will produce a path that is already ruled out by the branching decisions. And if this is the case, then you have to find the next shortest path. And if this is also already ruled out by branching, you have to find again the next shortest path and so on. This means, you need to solve the k-shortest paths problem at your pricing step, and this is exponential in k. Therefore, you typically want to use a different branching rule.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

well, I c! Thanks!

I also wondering : After some branching operations, if we do not change the path set and treat the branching as a normal constraint, do we have to update the column generation process? (take multicommodity network flow as the example). You know, if the branching constraint (x < 0 or sth else) is inserted in to a classic model, the formulation is slightly changed....

bao hua
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, of course you need to consider branching decisions in the pricing problem. With each new constraint you will get a new dual variable, and hence you need to consider this in your pricing.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Tobias,

thanks very much for your help!

Could you tell me What the major strategy of CPLEX is when solving MIP? As CPLEX does not provide eternal Branch-and-price algorithm.....Is it because branch-and-price is not the most useful or apropriate method for solving MIP?

bao hua
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

CPLEX is basically a black-box MIP solver. It uses branch-and-cut to solve the MIPs.

Branch-and-price is almost the opposite of "black-box" solving, because many components (branching, pricing, heuristics, presolve, ...) must be tailored towards the specific application. Many of the generic features that CPLEX implements would just not apply to branch-and-price applications.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Hi Tobias,

when I try to update my algorithm, I think I am not very clear on the "follow-on" strategy that you mentioned before

"For this reason, you often want to branch, e.g., on the set of outgoing arcs of a node (say, you have to use exactly one of those arcs). Split the set into two subsets S and T. On the one side of the branching you want to rule out the arcs of S (i.e., only those paths are valid that do not use those arcs), on the other side you want to rule out the paths that go through arcs in T. Now the pricing problem stays simple: just remove the respective arcs from the graph in the pricing problem of each of the children, and the problem stays a simple shortest path problem. This type of branching is called Ryan-Foster or "follow-on" branching."

How to choose the node in "the set of outgoing arcs of a node"? I am solving a binary multi-commodity network flow problem and my model is path-based formulation. My understanding is: after I found a path need to branching, I used the origin node of this path as the "node". Am I correct on this?

Thanks.

Bao hua
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Any node that is contained in at least one fractional path is suitable for branching.
The question which node to pick is a matter of what performs best, similar to the standard branching rules in MIP solving that need to pick a fractional variable.
Which is the best choice depends on your problem. You need to experiment with different ideas.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Hi Tobias,

I tried this branching strategy. It is faster than other strategy to find a same optimum.
However, after it found the optimum. It still needed quite a long time to terminate.
I think I may have to try inserting cutting process.

Thanks for all of your help!

bao hua
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: waldstein

Hi Tobias,

I was testing based on your suggestion as follows:

"For this reason, you often want to branch, e.g., on the set of outgoing arcs of a node (say, you have to use exactly one of those arcs). Split the set into two subsets S and T. On the one side of the branching you want to rule out the arcs of S (i.e., only those paths are valid that do not use those arcs), on the other side you want to rule out the paths that go through arcs in T. Now the pricing problem stays simple: just remove the respective arcs from the graph in the pricing problem of each of the children, and the problem stays a simple shortest path problem. This type of branching is called Ryan-Foster or "follow-on" branching."

2 strategies are tested:
1 In each node, find the subset S and T, and forbid the paths which in the current path set, then use a K-shrotest path to find other attrative paths (after K=10, terminate). But do not forbid the related arcs.
2 In each node, find the subset S and T, and forbid the paths which in the current path set and the related arcs in S or T,then use a K-shrotest path to find other attrative paths (after K=10, terminate)

Although I think 1 is more reasonable because once the arcs are forbidden, new path should not include them. But actually 1 cound obtain a better result than 2.

Could you please give me some suggestions on why?

Thanks!
#CPLEXOptimizers
#DecisionOptimization