Originally posted by: SystemAdmin

[ttclw said:]

Hi,

I'm working on a 0/1 integer programme which is used to route vehicles. The model is set up like a set-partitioning problem, i.e. each customer must be visited once in the planning horizon and I try to minimise the vehicles needed. So, I modelled the decision variable like a 'route' of the vehicle that includes those customers assigned to one specific vehicle in a certain period of time. Like cutting stock problem, there are too many potential decision variables (each different combination of customers forms a variable), so I use branch and price (i.e column generation).

The plan is to relax the 0/1 IP to form a master problem and use a sub-problem to generate 'columns' to the master, while checking the constraints of feasible new columns to add to the master by using the sub-problem. Since branching on the 'route' variable is useless (too hard to implement), so I followed some papers in the OR literature and chose to use a different branching algorithm, namely 'branch on follow- ons'. So one node is to have two customers, say r & s, visited sequentially, while the other node is not to have these two customers together in a route.

Here comes the implementation & technical issue with CPlex/Concert. My question is about creating branches by using CPlex via Concert (APIs). I'm aware that Goals and CallBacks in CPLEX Concert technology allow us to modify which variable to branch and have more control over the branch-and-bound procedure. However, the new constraints I want to pass on to child nodes are not  like (X>= 5, X<=4), but constraints to be used in the new sub-problem of the new master of the child node. In<br />other words, in the network sub-problem, I will force the link between r and s (Xrs) as 1 for one child node and as 0 for the other branch. By doing this, I hope to generate new feasible columns for each branches and move on to get integer solutions at the end.

Some earlier posts and some literature have mentioned that Branch-and- Price can be done in CPlex, but I just can't find any documentation for this advanced topic. I've tried Goal and CallBack, but seems that they can pass constraints on 'decision variables' to the new master, but not to the new sub?

Any ideas?

ttclw@Sydney
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[ChrisHane said:]

Hello,

When you call one of the makeBranch methods of the branch callback object you may specify the set of constraints that define the new node(s).  The cuts are not just x(i) <= k or x(i) >= k+1, but two sets of constraints.

If your model has a variable, x(r), for each route, then the branch to force the choice of customer B follows customer A is a constraint of the form sum x(s in S) >= 1, where S includes all routes that visit A then B, the other branch is sum (x in S) <= 0 (do not choose any route that goes from A to B).<br />
There are various choices to make for the set S.  Does S include all routes, only routes of a certain vehicle type, or 1 specific vehicle? You may consider nesting these choices, i.e after branching on A must precede B, then branch on the vehicle type before the specific vehicle. 

In addition to writing the branch callback you will need to consider implementing node selection and perhaps other control callbacks.  These are documented at ILOG CPLEX 11.0 User's Manual > Advanced Programming Techniques > Advanced MIP Control Interface.   

You may want to also refer to "USING BRANCH-AND-PRICE-AND-CUT TO SOLVE ORIGIN DESTINATION INTEGER MULTICOMMODITY FLOW PROBLEMS" by Barnhart et al, Operations Research Vol. 48, No. 2, March–April 2000, pp. 318–326.  This paper gives a detailed explanation of branching on edges in a path based model while preserving the ability to use shortest path column generation in branch and price.

Good Luck!
Chris
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[ttclw said:]

Hi Chris,

Thanks for your advise. I've figured out how the makeBranch method can add a set of constraints (from reading the API java-docs) and I'm on the track you've pointed to me right now. My questions are more about technical issues of implementing branch-and-price by using CPLEX and Java.

Since the branch-and-price scheme needs to solve a pair of master-sub problems at each node of the branch-and-bound tree, I suppose that I need to insert the while loop in the makeBranch method that generates new columns to the master. Questions are:

1) where & when the master is first solved? It seems to me that the .solve() of CPLEX for the master problem is implicit in the makeBranch call, so I wonder where & when this .solve() thing is done, because I need to grab the dual prices to kick off the sub-problem loop and generate columns. Or, the master is solved immediately when the procedure enters the makeBranch method. If so, can I grab the duals at the beginning of the makeBranch method?

2) how do I pass constraints to the corresponding sub-problem at each node? Yes, we can pass a set of new constraints to the new master  problems at child nodes according to our branching scheme (and thanks for your suggestion of nested branching). Since the branching is based on "original" variables (not the modelled variables, i.e. x(r)), it's hard to pass the corresponding constraints of x(s in S) >= 1 (for instance) to its sub problem, because the sub-problem is modelled as a network problem (to search for the shortest routes). The arguments we can pass via makeBranch is a set of constraints for new master problems. How can we achieve the new constraint passing for the sub via makeBranch? Or, we need a 'translation' method here?

By the way, thanks for the paper. A good one, indeed. Well written. ^_*

thanks,

TTCLW@Sydney

[quote author=ChrisHane link=topic=130.msg324#msg324 date=1198185784]
Hello,

When you call one of the makeBranch methods of the branch callback object you may specify the set of constraints that define the new node(s).  The cuts are not just x(i) <= k or x(i) >= k+1, but two sets of constraints.

If your model has a variable, x(r), for each route, then the branch to force the choice of customer B follows customer A is a constraint of the form sum x(s in S) >= 1, where S includes all routes that visit A then B, the other branch is sum (x in S) <= 0 (do not choose any route that goes from A to B).<br />
There are various choices to make for the set S.  Does S include all routes, only routes of a certain vehicle type, or 1 specific vehicle? You may consider nesting these choices, i.e after branching on A must precede B, then branch on the vehicle type before the specific vehicle. 

In addition to writing the branch callback you will need to consider implementing node selection and perhaps other control callbacks.  These are documented at ILOG CPLEX 11.0 User's Manual > Advanced Programming Techniques > Advanced MIP Control Interface.   

You may want to also refer to "USING BRANCH-AND-PRICE-AND-CUT TO SOLVE ORIGIN DESTINATION INTEGER MULTICOMMODITY FLOW PROBLEMS" by Barnhart et al, Operations Research Vol. 48, No. 2, March–April 2000, pp. 318–326.  This paper gives a detailed explanation of branching on edges in a path based model while preserving the ability to use shortest path column generation in branch and price.

Good Luck!
Chris

#CPLEXOptimizers
#DecisionOptimization