| 1 | <?xml version="1.0" encoding="ISO-8859-1" standalone="no"?> |
|---|
| 2 | <html xmlns="http://www.w3.org/1999/xhtml"><head><title>Pseudo Cost 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="ch05.html" title="Chapter 5. Branching "/><link rel="previous" href="ch05.html" title="Chapter 5. Branching "/><link rel="next" href="ch05s03.html" title="Follow-On Branching"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Pseudo Cost Branching</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch05.html">Prev</a> </td><th width="60%" align="center">Chapter 5. |
|---|
| 3 | Branching |
|---|
| 4 | </th><td width="20%" align="right"> <a accesskey="n" href="ch05s03.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 id="branching"/>Pseudo Cost Branching</h2></div></div><div/></div><p> |
|---|
| 5 | |
|---|
| 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 section 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. Pseudo costs can be used both for branching and for choosing a node. |
|---|
| 9 | The full code is in <tt class="filename">longthin.cpp</tt> located in the CBC Samples directory, see |
|---|
| 10 | <a href="ch08.html" title="Chapter 8. More Samples ">Chapter 8, <i> |
|---|
| 11 | More Samples |
|---|
| 12 | </i></a>. |
|---|
| 13 | </p><p> |
|---|
| 14 | The idea is simple for set covering problems. |
|---|
| 15 | Branching up gets us much closer to an integer solution so we will encourage that direction by branch up if variable value > 0.333333. |
|---|
| 16 | The expected cost of going up obviously depends on the cost of the |
|---|
| 17 | variable. The pseudo costs are choosen to reflect that fact. |
|---|
| 18 | |
|---|
| 19 | </p><div class="example"><a id="pseudo"/><p class="title"><b>Example 5.1. <tt class="classname">CbcSimpleIntegerPseudoCosts</tt></b></p><pre class="programlisting"> |
|---|
| 20 | |
|---|
| 21 | int iColumn; |
|---|
| 22 | int numberColumns = solver3->getNumCols(); |
|---|
| 23 | // do pseudo costs |
|---|
| 24 | CbcObject ** objects = new CbcObject * [numberColumns]; |
|---|
| 25 | // Point to objective |
|---|
| 26 | const double * objective = model.getObjCoefficients(); |
|---|
| 27 | int numberIntegers=0; |
|---|
| 28 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
|---|
| 29 | if (solver3->isInteger(iColumn)) { |
|---|
| 30 | double cost = objective[iColumn]; |
|---|
| 31 | CbcSimpleIntegerPseudoCost * newObject = |
|---|
| 32 | new CbcSimpleIntegerPseudoCost(&model,numberIntegers,iColumn, |
|---|
| 33 | 2.0*cost,cost); |
|---|
| 34 | newObject->setMethod(3); |
|---|
| 35 | objects[numberIntegers++]= newObject; |
|---|
| 36 | } |
|---|
| 37 | } |
|---|
| 38 | // Now add in objects (they will replace simple integers) |
|---|
| 39 | model.addObjects(numberIntegers,objects); |
|---|
| 40 | for (iColumn=0;iColumn<numberIntegers;iColumn++) |
|---|
| 41 | delete objects[iColumn]; |
|---|
| 42 | delete [] objects; |
|---|
| 43 | |
|---|
| 44 | </pre></div><p> |
|---|
| 45 | The code in <a href="ch05s02.html#pseudo" title="Example 5.1. CbcSimpleIntegerPseudoCosts">Example 5.1</a> also tries to give more importance to variables with more |
|---|
| 46 | coefficients. Whether this sort of thing is worthwhile should be the subject of experimentation. |
|---|
| 47 | |
|---|
| 48 | |
|---|
| 49 | </p></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch05.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch05.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch05s03.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 5. |
|---|
| 50 | Branching |
|---|
| 51 | </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Follow-On Branching</td></tr></table></div></body></html> |
|---|
