Follow-On Branching

In crew scheduling, the problems are long and thin. A problem may have a few rows but many thousands of variables. Branching a variable to 1 is very powerful as it fixes many other variables to zero, but branching to zero is very weak as thousands of variables can increase from zero. In crew scheduling problems, each constraint is a flight leg, e.g., JFK airport to DFW airport. From DFW there may be several flights the crew could take next - suppose one flight is the 9:30 flight from DFW to LAX airport. A binary branch is that the crew arriving at DFW either take the 9:30 flight to LAX or they don't. This "follow-on" branching does not fix individual variables. Instead this branching divides all the variables with entries in the JFK-DFW constraint into two groups - those with entries in the DFW-LAX constraint and those without entries.

The full sample code for follow-on brancing is in crew.cpp located in the CBC Samples directory, see Chapter 8, More Samples ). In this case, the simple integer variables are left which may be necessary if other sorts of constraints exist. Follow-on branching rules are to be considered first, so the priorities are set to indicate the follow-on rules take precedence. Priority 1 is the highest priority.