source: branches/gh-pages/branching.md @ 2521

Last change on this file since 2521 was 2521, checked in by stefan, 3 months ago

migrate Cbc documentation to gh-pages

  • converted docbook to markdown
  • source now in gh-pages branch, so remove Cbc/doc
  • some cleanup
  • update link in README.md
  • Property svn:eol-style set to native
File size: 4.6 KB
Line 
1# Branching
2
3CBC's concept of branching is based on the idea of an "object".
4An 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.
5Instances 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
15If the user declares variables as integer but does no more, then CBC
16will treat them as simple integer variables. In many cases the user
17would like to do some more fine tuning. This section shows how to create
18integer variables with pseudo costs. When pseudo costs are given then it
19is assumed that if a variable is at 1.3 then the cost of branching that
20variable down will be 0.3 times the down pseudo cost and the cost of
21branching up would be 0.7 times the up pseudo cost. Pseudo costs can be
22used both for branching and for choosing a node. The full code is in
23`longthin.cpp` located in the CBC Samples directory.
24
25The idea is simple for set covering problems. Branching up gets us much
26closer to an integer solution so we will encourage that direction by
27branch up if variable value > 0.333333. The expected cost of going up
28obviously depends on the cost of the variable. The pseudo costs are
29choosen to reflect that fact.
30
31```
32int iColumn;
33int numberColumns = solver3->getNumCols();
34// do pseudo costs
35CbcObject ** objects = new CbcObject * [numberColumns];
36// Point to objective
37const double * objective = model.getObjCoefficients();
38int numberIntegers=0;
39for (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)
50model.addObjects(numberIntegers,objects);
51for (iColumn=0;iColumn<numberIntegers;iColumn++)
52  delete objects[iColumn];
53delete [] objects;
54```
55
56This code also tries to give more importance
57to variables with more coefficients. Whether this sort of thing is
58worthwhile should be the subject of experimentation.
59
60## Follow-On Branching
61
62In crew scheduling, the problems are long and thin. A problem may have a
63few rows but many thousands of variables. Branching a variable to 1 is
64very powerful as it fixes many other variables to zero, but branching to
65zero is very weak as thousands of variables can increase from zero. In
66crew scheduling problems, each constraint is a flight leg, e.g., JFK
67airport to DFW airport. From DFW there may be several flights the crew
68could take next - suppose one flight is the 9:30 flight from DFW to LAX
69airport. A binary branch is that the crew arriving at DFW either take
70the 9:30 flight to LAX or they don't. This "follow-on" branching does
71not fix individual variables. Instead this branching divides all the
72variables with entries in the JFK-DFW constraint into two groups - those
73with entries in the DFW-LAX constraint and those without entries.
74
75The full sample code for follow-on brancing is in `crew.cpp` located in
76the CBC Samples directory. In this case, the
77simple integer variables are left which may be necessary if other sorts
78of constraints exist. Follow-on branching rules are to be considered
79first, so the priorities are set to indicated the follow-on rules take
80precedence. Priority 1 is the highest priority.
81
82```
83int iColumn;
84int 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
91int * priority = new int [numberColumns];
92int numberIntegers=0;
93for (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 */
100model.passInPriorities(priority,false);
101delete [] 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*/
106CbcObject ** objects = new CbcObject * [1];
107objects[0]=new CbcFollowOn(&model);
108model.addObjects(1,objects);
109delete objects[0];
110delete [] objects;
111// High priority
112int followPriority=1;
113model.passInPriorities(&followPriority,true);
114```
Note: See TracBrowser for help on using the repository browser.