| 1 | <html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Branching</title><meta name="generator" content="DocBook XSL Stylesheets V1.61.2"><link rel="home" href="index.html" title="CBC User Guide"><link rel="up" href="ch03.html" title="Chapter 3. |
|---|
| 2 | Other Classes and examples |
|---|
| 3 | "><link rel="previous" href="ch03s02.html" title="CbcHeuristic - heuristic methods"><link rel="next" href="ch03s04.html" title="Advanced use of solver"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Branching</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch03s02.html">Prev</a> </td><th width="60%" align="center">Chapter 3. |
|---|
| 4 | Other Classes and examples |
|---|
| 5 | </th><td width="20%" align="right"> <a accesskey="n" href="ch03s04.html">Next</a></td></tr></table><hr></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="branching"></a>Branching</h2></div></div><div></div></div><p> |
|---|
| 6 | If the user declares variables as integer but does no more, then Cbc will treat them |
|---|
| 7 | as simple integer variables. In many cases the user would like to do some more fine tuning. This shows how to create integer variables with pseudo costs. When pseudo costs are given then |
|---|
| 8 | it is assumed that if a variable is at 1.3 then the cost of branching that variable down will be 0.3 times the down pseudo cost and the cost of branching up would be 0.7 times the up pseudo cost. This can be used both for branching and for choosing a node. |
|---|
| 9 | The full code is in <tt class="filename">longthin.cpp</tt> |
|---|
| 10 | (this code can be found in the CBC Samples directory, see |
|---|
| 11 | <a href="ch05.html" title="Chapter 5. |
|---|
| 12 | More Samples |
|---|
| 13 | ">Chapter 5, <i> |
|---|
| 14 | More Samples |
|---|
| 15 | </i></a>). |
|---|
| 16 | The idea is simple for set covering problems. |
|---|
| 17 | Branching up gets us much closer to an integer solution so we want |
|---|
| 18 | to encourage up - so we will branch up if variable value > 0.333333. |
|---|
| 19 | The expected cost of going up obviously depends on the cost of the |
|---|
| 20 | variable so we just choose pseudo costs to reflect that. |
|---|
| 21 | </p><div class="example"><a name="id2903248"></a><p class="title"><b>Example 3.8. Pseudo costs</b></p><pre class="programlisting"> |
|---|
| 22 | |
|---|
| 23 | int iColumn; |
|---|
| 24 | int numberColumns = solver3->getNumCols(); |
|---|
| 25 | // do pseudo costs |
|---|
| 26 | CbcObject ** objects = new CbcObject * [numberColumns]; |
|---|
| 27 | // Point to objective |
|---|
| 28 | const double * objective = model.getObjCoefficients(); |
|---|
| 29 | int numberIntegers=0; |
|---|
| 30 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
|---|
| 31 | if (solver3->isInteger(iColumn)) { |
|---|
| 32 | double cost = objective[iColumn]; |
|---|
| 33 | CbcSimpleIntegerPseudoCost * newObject = |
|---|
| 34 | new CbcSimpleIntegerPseudoCost(&model,numberIntegers,iColumn, |
|---|
| 35 | 2.0*cost,cost); |
|---|
| 36 | newObject->setMethod(3); |
|---|
| 37 | objects[numberIntegers++]= newObject; |
|---|
| 38 | } |
|---|
| 39 | } |
|---|
| 40 | // Now add in objects (they will replace simple integers) |
|---|
| 41 | model.addObjects(numberIntegers,objects); |
|---|
| 42 | for (iColumn=0;iColumn<numberIntegers;iColumn++) |
|---|
| 43 | delete objects[iColumn]; |
|---|
| 44 | delete [] objects; |
|---|
| 45 | |
|---|
| 46 | </pre></div><p> |
|---|
| 47 | The actual coding in the example also tries to give more importance to variables with more |
|---|
| 48 | coefficients. Whether this sort of thing is worthwhile should be the subject of experimentation. |
|---|
| 49 | Here is another example which is for crew scheduling problems. In this case the problem has |
|---|
| 50 | few rows but many thousands of variables. Branching a variable to 1 is very powerful as it |
|---|
| 51 | fixes many other variables to zero, but branching to zero is very weak as thousands of variables |
|---|
| 52 | can increase from zero. But in crew scheduling each constraint is a flight leg e.g. JFK to DFW. |
|---|
| 53 | From DFW (Dallas) there may be several flights the crew could take next - suppose one flight is |
|---|
| 54 | the 9:30 flight from DFW to LAX (Los Angeles). Then a binary branch is that the crew arriving |
|---|
| 55 | at DFW either take the 9:30 flight to LAX or they don't. This follow-on branching does not |
|---|
| 56 | fix individual variables but instead divides all the variables with entries in the JFK-DFW |
|---|
| 57 | constraint into two groups - those with entries in the DFW-LAX constraint and those without |
|---|
| 58 | entries. |
|---|
| 59 | The full code is in <tt class="filename">crew.cpp</tt> |
|---|
| 60 | (this code can be found in the CBC Samples directory, see |
|---|
| 61 | <a href="ch05.html" title="Chapter 5. |
|---|
| 62 | More Samples |
|---|
| 63 | ">Chapter 5, <i> |
|---|
| 64 | More Samples |
|---|
| 65 | </i></a>). In this case we may as well leave the simple integer |
|---|
| 66 | variables and we may have to if there are other sorts of constraints. But we want to |
|---|
| 67 | branch on the follow-on rules first so we use priorities to say that those are the |
|---|
| 68 | important ones. |
|---|
| 69 | </p><div class="example"><a name="id2903330"></a><p class="title"><b>Example 3.9. Follow-on branching</b></p><pre class="programlisting"> |
|---|
| 70 | |
|---|
| 71 | int iColumn; |
|---|
| 72 | int numberColumns = solver3->getNumCols(); |
|---|
| 73 | /* We are going to add a single follow on object but we |
|---|
| 74 | want to give low priority to existing integers |
|---|
| 75 | As the default priority is 1000 we don't actually need to give |
|---|
| 76 | integer priorities but it is here to show how. |
|---|
| 77 | */ |
|---|
| 78 | // Normal integer priorities |
|---|
| 79 | int * priority = new int [numberColumns]; |
|---|
| 80 | int numberIntegers=0; |
|---|
| 81 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
|---|
| 82 | if (solver3->isInteger(iColumn)) { |
|---|
| 83 | priority[numberIntegers++]= 100; // low priority |
|---|
| 84 | } |
|---|
| 85 | } |
|---|
| 86 | /* Second parameter is true if we are adding objects, |
|---|
| 87 | false if integers. So this does integers */ |
|---|
| 88 | model.passInPriorities(priority,false); |
|---|
| 89 | delete [] priority; |
|---|
| 90 | /* Add in objects before we can give priority. |
|---|
| 91 | In this case just one - but this shows general method |
|---|
| 92 | */ |
|---|
| 93 | CbcObject ** objects = new CbcObject * [1]; |
|---|
| 94 | objects[0]=new CbcFollowOn(&model); |
|---|
| 95 | model.addObjects(1,objects); |
|---|
| 96 | delete objects[0]; |
|---|
| 97 | delete [] objects; |
|---|
| 98 | // High priority |
|---|
| 99 | int followPriority=1; |
|---|
| 100 | model.passInPriorities(&followPriority,true); |
|---|
| 101 | |
|---|
| 102 | </pre></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch03s02.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch03.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch03s04.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">CbcHeuristic - heuristic methods </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Advanced use of solver</td></tr></table></div></body></html> |
|---|
