1 | # Branching |
---|
2 | |
---|
3 | CBC's concept of branching is based on the idea of an "object". |
---|
4 | An object has (i) a feasible region, (ii) can be evaluated for infeasibility, (iii) can be branched on, e.g., a method of generating a branching object, which defines an up branch and a down branch, and (iv) allows comparsion of the effect of branching. |
---|
5 | Instances of objects include: |
---|
6 | - `CbcSimpleInteger`, |
---|
7 | - `CbcSimpleIntegerPseudoCosts`, |
---|
8 | - `CbcClique`, |
---|
9 | - `CbcSOS` (type 1 and 2), |
---|
10 | - `CbcFollowOn`, and |
---|
11 | - `CbcLotsize`. |
---|
12 | |
---|
13 | ## Pseudo Cost Branching |
---|
14 | |
---|
15 | If the user declares variables as integer but does no more, then CBC |
---|
16 | will treat them as simple integer variables. In many cases the user |
---|
17 | would like to do some more fine tuning. This section shows how to create |
---|
18 | integer variables with pseudo costs. When pseudo costs are given then it |
---|
19 | is assumed that if a variable is at 1.3 then the cost of branching that |
---|
20 | variable down will be 0.3 times the down pseudo cost and the cost of |
---|
21 | branching up would be 0.7 times the up pseudo cost. Pseudo costs can be |
---|
22 | used both for branching and for choosing a node. The full code is in |
---|
23 | `longthin.cpp` located in the CBC Samples directory. |
---|
24 | |
---|
25 | The idea is simple for set covering problems. Branching up gets us much |
---|
26 | closer to an integer solution so we will encourage that direction by |
---|
27 | branch up if variable value > 0.333333. The expected cost of going up |
---|
28 | obviously depends on the cost of the variable. The pseudo costs are |
---|
29 | choosen to reflect that fact. |
---|
30 | |
---|
31 | ``` |
---|
32 | int iColumn; |
---|
33 | int numberColumns = solver3->getNumCols(); |
---|
34 | // do pseudo costs |
---|
35 | CbcObject ** objects = new CbcObject * [numberColumns]; |
---|
36 | // Point to objective |
---|
37 | const double * objective = model.getObjCoefficients(); |
---|
38 | int numberIntegers=0; |
---|
39 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
40 | if (solver3->isInteger(iColumn)) { |
---|
41 | double cost = objective[iColumn]; |
---|
42 | CbcSimpleIntegerPseudoCost * newObject = |
---|
43 | new CbcSimpleIntegerPseudoCost(&model,numberIntegers,iColumn, |
---|
44 | 2.0*cost,cost); |
---|
45 | newObject->setMethod(3); |
---|
46 | objects[numberIntegers++]= newObject; |
---|
47 | } |
---|
48 | } |
---|
49 | // Now add in objects (they will replace simple integers) |
---|
50 | model.addObjects(numberIntegers,objects); |
---|
51 | for (iColumn=0;iColumn<numberIntegers;iColumn++) |
---|
52 | delete objects[iColumn]; |
---|
53 | delete [] objects; |
---|
54 | ``` |
---|
55 | |
---|
56 | This code also tries to give more importance |
---|
57 | to variables with more coefficients. Whether this sort of thing is |
---|
58 | worthwhile should be the subject of experimentation. |
---|
59 | |
---|
60 | ## Follow-On Branching |
---|
61 | |
---|
62 | In crew scheduling, the problems are long and thin. A problem may have a |
---|
63 | few rows but many thousands of variables. Branching a variable to 1 is |
---|
64 | very powerful as it fixes many other variables to zero, but branching to |
---|
65 | zero is very weak as thousands of variables can increase from zero. In |
---|
66 | crew scheduling problems, each constraint is a flight leg, e.g., JFK |
---|
67 | airport to DFW airport. From DFW there may be several flights the crew |
---|
68 | could take next - suppose one flight is the 9:30 flight from DFW to LAX |
---|
69 | airport. A binary branch is that the crew arriving at DFW either take |
---|
70 | the 9:30 flight to LAX or they don't. This "follow-on" branching does |
---|
71 | not fix individual variables. Instead this branching divides all the |
---|
72 | variables with entries in the JFK-DFW constraint into two groups - those |
---|
73 | with entries in the DFW-LAX constraint and those without entries. |
---|
74 | |
---|
75 | The full sample code for follow-on brancing is in `crew.cpp` located in |
---|
76 | the CBC Samples directory. In this case, the |
---|
77 | simple integer variables are left which may be necessary if other sorts |
---|
78 | of constraints exist. Follow-on branching rules are to be considered |
---|
79 | first, so the priorities are set to indicated the follow-on rules take |
---|
80 | precedence. Priority 1 is the highest priority. |
---|
81 | |
---|
82 | ``` |
---|
83 | int iColumn; |
---|
84 | int numberColumns = solver3->getNumCols(); |
---|
85 | /* We are going to add a single follow-on object but we |
---|
86 | want to give low priority to existing integers |
---|
87 | As the default priority is 1000 we don't actually need to give |
---|
88 | integer priorities but it is here to show how. |
---|
89 | */ |
---|
90 | // Normal integer priorities |
---|
91 | int * priority = new int [numberColumns]; |
---|
92 | int numberIntegers=0; |
---|
93 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
94 | if (solver3->isInteger(iColumn)) { |
---|
95 | priority[numberIntegers++]= 100; // low priority |
---|
96 | } |
---|
97 | } |
---|
98 | /* Second parameter is set to true for objects, |
---|
99 | and false for integers. This indicates integers */ |
---|
100 | model.passInPriorities(priority,false); |
---|
101 | delete [] priority; |
---|
102 | /* Add in objects before we can give them a priority. |
---|
103 | In this case just one object |
---|
104 | - but it shows the general method |
---|
105 | */ |
---|
106 | CbcObject ** objects = new CbcObject * [1]; |
---|
107 | objects[0]=new CbcFollowOn(&model); |
---|
108 | model.addObjects(1,objects); |
---|
109 | delete objects[0]; |
---|
110 | delete [] objects; |
---|
111 | // High priority |
---|
112 | int followPriority=1; |
---|
113 | model.passInPriorities(&followPriority,true); |
---|
114 | ``` |
---|