[555] | 1 | <?xml version="1.0" encoding="UTF-8"?> |
---|
| 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
---|
| 3 | <html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>CBC User Guide</title><meta name="generator" content="DocBook XSL Stylesheets V1.61.2" /></head><body><div class="book" lang="en" xml:lang="en"><div class="titlepage"><div><div><h1 class="title"><a id="cbcuserguide"></a>CBC User Guide</h1></div><div><div class="authorgroup"><div class="author"><h3 class="author"><span class="firstname"> |
---|
| 4 | John |
---|
| 5 | </span> <span class="surname"> |
---|
| 6 | Forrest |
---|
| 7 | </span></h3><div class="affiliation"><span class="orgname"> |
---|
| 8 | IBM Research |
---|
| 9 | <br /></span></div></div><div class="author"><h3 class="author"><span class="firstname"> |
---|
| 10 | Robin |
---|
| 11 | </span> <span class="surname"> |
---|
| 12 | Lougee-Heimer |
---|
| 13 | </span></h3><div class="affiliation"><span class="orgname"> |
---|
| 14 | IBM Research |
---|
| 15 | <br /></span></div></div></div></div><div><p class="copyright">Copyright Â© 2005 IBM Coportation</p></div><div><div class="legalnotice"> |
---|
| 16 | CBC and this documentation are provided under the terms of the |
---|
| 17 | <a href="http://opensource.org/licenses/cpl.php" target="_top">Common Public License |
---|
| 18 | ("CPL")</a>. Any use, reproduction or distribution of the programs constitutes |
---|
| 19 | the recipient's acceptance of the license. The |
---|
| 20 | <a href="http://opensource.org/licenses/cpl.php" target="_top">CPL</a> is approved by |
---|
| 21 | the <a href="http://opensource.org/" target="_top">Open Source Initiative</a>. IBM |
---|
| 22 | Corporation, the author of the |
---|
| 23 | <a href="http://opensource.org/licenses/cpl.php" target="_top">CPL</a>, has a |
---|
| 24 | <a href="http://www.ibm.com/developerworks/library/os-cplfaq.html" target="_top"> |
---|
| 25 | CPL FAQ</a> available which is based on IBM's understanding of the |
---|
| 26 | <a href="http://opensource.org/licenses/cpl.php" target="_top">CPL</a>. |
---|
| 27 | </div></div></div><div></div><hr /></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt>1. <a href="#intro"> |
---|
| 28 | Introduction |
---|
[557] | 29 | </a></dt><dd><dl><dt><a href="#id2968004"> |
---|
[555] | 30 | Welcome to CBC |
---|
[557] | 31 | </a></dt><dt><a href="#id2967833"> |
---|
[555] | 32 | Prerequisites |
---|
[557] | 33 | </a></dt><dt><a href="#id2967708">Preliminaries</a></dt><dt><a href="#id3038724"> |
---|
[555] | 34 | Branch-and-Cut Overview |
---|
| 35 | </a></dt></dl></dd><dt>2. <a href="#cbcmodelclass"> |
---|
| 36 | The CBC Model Class |
---|
| 37 | </a></dt><dd><dl><dt><a href="#hierarchy"> |
---|
| 38 | Overview |
---|
| 39 | </a></dt><dt><a href="#firstexample"> |
---|
| 40 | Simple Branch-and-Bound Example |
---|
| 41 | </a></dt><dt><a href="#osiAndCbc"> |
---|
| 42 | The Relationship Between OSI and CBC |
---|
| 43 | </a></dt><dt><a href="#gettingsolution"> |
---|
| 44 | Getting Solution Information |
---|
| 45 | </a></dt><dt><a href="#setsandgets"> |
---|
| 46 | Useful Set and Get Methods in CbcModel |
---|
| 47 | </a></dt><dt><a href="#majormethods"> |
---|
| 48 | Impacting the Solution Process |
---|
| 49 | </a></dt></dl></dd><dt>3. <a href="#otherclasses"> |
---|
| 50 | Selecting the Next Node in the Search Tree |
---|
| 51 | </a></dt><dd><dl><dt><a href="#comparison">CbcCompare - Comparison Methods</a></dt></dl></dd><dt>4. <a href="#hueristicChap"> |
---|
| 52 | Getting Good Bounds in CBC |
---|
| 53 | </a></dt><dd><dl><dt><a href="#heuristics">CbcHeuristic - Heuristic Methods</a></dt></dl></dd><dt>5. <a href="#branchChapter"> |
---|
| 54 | Branching |
---|
[557] | 55 | </a></dt><dd><dl><dt><a href="#branchingIntro">Branching Overview</a></dt><dt><a href="#branching">Pseudo Cost Branching</a></dt><dt><a href="#followOn">Follow-On Branching</a></dt></dl></dd><dt>6. <a href="#CutsChap">Cutting planes</a></dt><dd><dl><dt><a href="#cuts">Using Cut Generators with CBC</a></dt></dl></dd><dt>7. <a href="#SolverChap"> |
---|
| 56 | Advanced Solver Uses |
---|
| 57 | </a></dt><dd><dl><dt><a href="#solver">Creating a Solver via Inheritance</a></dt><dt><a href="#quadratic">Quadratic MIP</a></dt></dl></dd><dt>8. <a href="#moreexamples"> |
---|
[555] | 58 | More Samples |
---|
[557] | 59 | </a></dt><dd><dl><dt><a href="#id3049424">CBC's Samples Directory</a></dt></dl></dd><dt>9. <a href="#messages"> |
---|
[555] | 60 | Messages |
---|
[557] | 61 | </a></dt><dt>A. <a href="#id3055917">FAQ</a></dt><dt>B. <a href="#doxygen">Doxygen</a></dt><dt>C. <a href="#id3055667">Revision History</a></dt></dl></div><div class="list-of-tables"><p><b>List of Tables</b></p><dl><dt>1.1. <a href="#assClasses">Associated Classes</a></dt><dt>2.1. <a href="#id3040696"> |
---|
[555] | 62 | Methods for Getting Solution Information from OSI |
---|
[557] | 63 | </a></dt><dt>2.2. <a href="#setGet">Useful Set and Get Methods in CbcModel</a></dt><dt>2.3. <a href="#id3042180">Classes Used by CbcModel - Most Useful</a></dt><dt>2.4. <a href="#least">Classes Used by CbcModel - Least Useful</a></dt><dt>3.1. <a href="#compareTable">Compare Classes Provided</a></dt><dt>3.2. <a href="#nodeTable">Information Available from CbcNode</a></dt><dt>8.1. <a href="#id3050381">Basic Samples</a></dt><dt>8.2. <a href="#id3050556">Advanced Samples</a></dt><dt>9.1. <a href="#id3051858"> |
---|
| 64 | CBC Messages Passed At Log Level 0 |
---|
| 65 | </a></dt><dt>9.2. <a href="#id3052003"> |
---|
| 66 | CBC Messages Passed At or Above Log Level 1 |
---|
| 67 | </a></dt><dt>9.3. <a href="#id3053367"> |
---|
| 68 | CBC Messages Passed At or Above Log Level 2 |
---|
| 69 | </a></dt><dt>9.4. <a href="#id3053768"> |
---|
| 70 | CBC Messages Passed At or Above Log Level 3 |
---|
| 71 | </a></dt></dl></div><div class="list-of-examples"><p><b>List of Examples</b></p><dl><dt>2.1. <a href="#minimum.cpp">minimum.cpp</a></dt><dt>3.1. <a href="#test">CbcCompareUser::test()</a></dt><dt>3.2. <a href="#newSolution">CbcCompareUser::newSolution()</a></dt><dt>3.3. <a href="#everyK">CbcCompareUser::every1000Nodes()</a></dt><dt>4.1. <a href="#id3047001">Data</a></dt><dt>4.2. <a href="#id3047030">Initialize newSolution</a></dt><dt>4.3. <a href="#id3047111">Create Feasible newSolution from Initial newSolution</a></dt><dt>4.4. <a href="#id3047155">Check Solution Quality of newSolution</a></dt><dt>5.1. <a href="#pseudo">CbcSimpleIntegerPseudoCosts</a></dt><dt>5.2. <a href="#id3047524">CbcFollowOn</a></dt><dt>7.1. <a href="#initialSolve">initialSolve()</a></dt><dt>7.2. <a href="#id3047792">First Few Solves</a></dt><dt>7.3. <a href="#id3047820">Create Small Sub-Problem</a></dt><dt>7.4. <a href="#id3047866">Check Optimal Solution</a></dt><dt>7.5. <a href="#id3047932">Solving a Quadratic MIP</a></dt></dl></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="intro"></a>ChapterÂ 1.Â |
---|
[555] | 72 | Introduction |
---|
[557] | 73 | </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#id2968004"> |
---|
[555] | 74 | Welcome to CBC |
---|
[557] | 75 | </a></dt><dt><a href="#id2967833"> |
---|
[555] | 76 | Prerequisites |
---|
[557] | 77 | </a></dt><dt><a href="#id2967708">Preliminaries</a></dt><dt><a href="#id3038724"> |
---|
[555] | 78 | Branch-and-Cut Overview |
---|
[557] | 79 | </a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2968004"></a> |
---|
[555] | 80 | Welcome to CBC |
---|
| 81 | </h2></div></div><div></div></div><p> |
---|
| 82 | The COIN |
---|
[557] | 83 | <sup>[<a id="id2968015" href="#ftn.id2968015">1</a>]</sup> |
---|
[555] | 84 | Branch and Cut solver (CBC) is an open-source mixed-integer program (MIP) solver written in C++. CBC is intended to be used primarily as a callable library to create customized branch-and-cut solvers. A basic, stand-alone executable version is also available. CBC is an active open-source project led by John Forrest at www.coin-or.org. |
---|
[557] | 85 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2967833"></a> |
---|
[555] | 86 | Prerequisites |
---|
| 87 | </h2></div></div><div></div></div><p> |
---|
| 88 | The primary users of CBC are expected to be developers implementing customized branch-and-cut algorithms in C++ using CBC as a library. Consequently, this document assumes a working knowledge of |
---|
| 89 | <a href="http://www.cplusplus.com/doc/tutorial/" target="_top">C++</a>, including basic |
---|
| 90 | object-oriented programming terminology, and familiarity with the fundamental concepts of |
---|
| 91 | <a href="http://carbon.cudenver.edu/~hgreenbe/courseware/LPshort/intro.html" target="_top"> |
---|
[557] | 92 | linear programming</a> (LP) and |
---|
[555] | 93 | <a href="http://carbon.cudenver.edu/~hgreenbe/courseware/MIP/intro.html" target="_top"> |
---|
[557] | 94 | mixed integer programming</a> (MIP). |
---|
[555] | 95 | </p><p> |
---|
| 96 | |
---|
[557] | 97 | CBC relies on other parts of the COIN repository. CBC needs a LP solver and relies on the COIN Open Solver Inteface (OSI) to communicate with the user's choice of solver. Any LP solver with an OSI interface can be used with CBC. The LP solver expected to be used most commonly is COIN's native linear program solver, CLP. For cut generators, CBC relies on the COIN Cut Generation Library (CGL). Any cut generator written to CGL standards can be used with CBC. Some of the cut generators in CGL rely on other parts of COIN, e.g., CGL's Gomory cut generator rely on the factorization functionality of <tt class="classname">CoinFactorization</tt>. This document assumes basic familiarity with OSI and CGL. |
---|
[555] | 98 | </p><p> |
---|
[557] | 99 | Technically speaking, CBC accesses the solver (and sometime the model and data it contains) through an <tt class="classname">OSISolverInterface</tt>. For the sake of simplicity, we will refer to the <tt class="classname">OsiSolverInterface</tt> as "the solver" in this document, rather than "the standard application programming interface to the solver." We hope any confusion caused by blurring this distinction will be mitigated by the shorter sentences. |
---|
[555] | 100 | |
---|
[557] | 101 | </p><p> |
---|
[555] | 102 | In summary, readers should have the following prerequisites: |
---|
[557] | 103 | </p><div class="itemizedlist"><ul type="disc"><li>C++ knowledge,</li><li>LP and MIP fundamentals, and </li><li>OSI familiarity.</li></ul></div><p> |
---|
| 104 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2967708"></a>Preliminaries</h2></div></div><div></div></div><p> |
---|
| 105 | </p><div class="itemizedlist"><ul type="disc"><li>Unless otherwise stated, the problem being optimized is a minimization problem. </li><li>The terms "model" and "problem" are used synonymously.</li><li>Notation: We use the convention of appending an underscore to |
---|
| 106 | a variable in order to distinguish member data of a class.</li><li>The Cbc Samples directory, <tt class="filename">COIN/Cbc/Samples</tt> |
---|
| 107 | contains the source code for the examples in the Guide.</li><li>The sample code in the Guide is written for illustrative |
---|
| 108 | purposes of the CBC concepts and usage. The sample code is not |
---|
| 109 | necessarily written for performance.</li></ul></div><p> |
---|
| 110 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id3038724"></a> |
---|
[555] | 111 | Branch-and-Cut Overview |
---|
| 112 | </h2></div></div><div></div></div><p> |
---|
| 113 | Before examining CBC in more detail, we tersely describe the basic branch-and-cut algorithm by way of example, (which should really be called branch-and-cut-and-bound) and show the major C++ class(es) in CBC related to each step. The major CBC classes, labeled (A) through (F), are described in <a href="#assClasses" title="TableÂ 1.1.Â Associated Classes">TableÂ 1.1</a>. |
---|
| 114 | </p><p> |
---|
| 115 | Step 1. (Bound) Given a MIP model to minimize where some variables must take on integer values (e.g., 0, 1, or 2), relax the integrality requirements (e.g., consider each "integer" variable to be continuous with a lower bound of 0.0 and an upper bound of 2.0). Solve the resulting linear model with an LP solver to obtain a lower bound on the MIP's objective function value. If the optimal LP solution has integer values for the MIP's integer variables, we are finished. Any MIP-feasible solution provides an upper bound on the objective value. The upper bound equals the lower bound; the solution is optimal. |
---|
| 116 | </p><p> |
---|
[557] | 117 | Step 2. (Branch) Otherwise, there exists an "integer" variable with a non-integral value. Choose one non-integral variable (e.g., with value 1.3) (A)(B) and branch. Create two |
---|
| 118 | <sup>[<a id="id3038892" href="#ftn.id3038892">2</a>]</sup> |
---|
| 119 | nodes, one with the branching variable having an upper bound of 1.0, and the other with the branching variable having a lower bound of 2.0. Add the two nodes to the search tree. |
---|
[555] | 120 | </p><p> |
---|
| 121 | While (search tree is not empty) { |
---|
| 122 | </p><p> |
---|
| 123 | Step 3. (Choose Node) Pick a node off the tree (C)(D) |
---|
| 124 | </p><p> |
---|
| 125 | Step 4. (Re-optimize LP) Create an LP relaxation and solve. |
---|
| 126 | </p><p> |
---|
| 127 | Step 5. (Bound) Interrogate the optimal LP solution, and try to prune the node by one of the following. |
---|
| 128 | </p><div class="itemizedlist"><ul type="disc"><li> |
---|
| 129 | LP is infeasible, prune the node. |
---|
| 130 | </li><li> |
---|
| 131 | Else, the optimal LP solution value of the node exceeds the current upper bound, prune the node. |
---|
| 132 | </li><li> |
---|
| 133 | Else, the optimal LP solution of the node does not exceed the current upper bound and the solution is feasible to the MIP. Update the upper bound, and the best known MIP solution, and prune the node by optimality. |
---|
| 134 | </li></ul></div><p> |
---|
| 135 | </p><p> |
---|
| 136 | Step 6. (Branch) If we were unable to prune the node, then branch. Choose one non-integral variable to branch on (A)(B). Create two nodes and add them to the search tree. |
---|
| 137 | } |
---|
| 138 | </p><p> |
---|
[557] | 139 | This is the outline of a "branch-and-bound" algorithm. If in optimizing the linear programs, we use cuts to tighten the LP relaxations (E)(F), then we have a "branch-and-cut" algorithm. (Note, if cuts are only used in Step 1, the method is called a "cut-and-branch" algorithm.) |
---|
[555] | 140 | |
---|
| 141 | </p><div class="table"><a id="assClasses"></a><p class="title"><b>TableÂ 1.1.Â Associated Classes</b></p><table summary="Associated Classes" border="0"><colgroup><col /><col /><col /></colgroup><thead><tr><th> |
---|
| 142 | Note |
---|
| 143 | </th><th> |
---|
| 144 | Class name |
---|
| 145 | </th><th> |
---|
| 146 | Description |
---|
| 147 | </th></tr></thead><tbody><tr><td align="left" valign="top"> |
---|
| 148 | (A) |
---|
| 149 | </td><td align="left" valign="top"><tt class="classname">CbcBranch...</tt></td><td align="left" valign="top"> |
---|
| 150 | These classes define the nature of MIP's discontinuity. The simplest discontinuity |
---|
| 151 | is a variable which must take an integral value. Other types of discontinuities |
---|
| 152 | exist, e.g., lot-sizing variables. |
---|
| 153 | </td></tr><tr><td align="left" valign="top"> |
---|
| 154 | (B) |
---|
| 155 | </td><td align="left" valign="top"><tt class="classname">CbcNode</tt></td><td align="left" valign="top"> |
---|
| 156 | This class decides which variable/entity to branch on next. |
---|
| 157 | Even advanced users will probably only interact with this class by setting |
---|
| 158 | <tt class="classname">CbcModel</tt> parameters ( e.g., priorities). |
---|
| 159 | </td></tr><tr><td align="left" valign="top"> |
---|
| 160 | (C) |
---|
| 161 | </td><td align="left" valign="top"><tt class="classname">CbcTree</tt></td><td align="left" valign="top"> |
---|
| 162 | All unsolved models can be thought of as being nodes on a tree where each |
---|
[557] | 163 | node (model) can branch two or more times. The interface with this class is helpful to know, but |
---|
| 164 | the user can pretty safely ignore the inner workings of this class. |
---|
[555] | 165 | </td></tr><tr><td align="left" valign="top"> |
---|
| 166 | (D) |
---|
| 167 | </td><td align="left" valign="top"><tt class="classname">CbcCompare...</tt></td><td align="left" valign="top"> |
---|
| 168 | These classes are used in determine which of the unexplored nodes in the tree to consider next. These |
---|
| 169 | classes are very small simple classes that can be tailored to suit the problem. |
---|
| 170 | </td></tr><tr><td align="left" valign="top"> |
---|
| 171 | (E) |
---|
| 172 | </td><td align="left" valign="top"><tt class="classname">CglCutGenerators</tt></td><td align="left" valign="top"> |
---|
| 173 | Any cut generator from CGL can be used in CBC. The cut generators are passed to CBC with parameters |
---|
| 174 | which modify when each generator will be tried. All cut generators should be tried to |
---|
| 175 | determine which are effective. Few users will write their own cut generators. |
---|
| 176 | </td></tr><tr><td align="left" valign="top"> |
---|
| 177 | (F) |
---|
| 178 | </td><td align="left" valign="top"><tt class="classname">CbcHeuristics</tt></td><td align="left" valign="top"> |
---|
| 179 | Heuristics are very important for obtaining valid solutions quickly. Some |
---|
| 180 | heuristics are available, but this is an area where it is useful and interesting to |
---|
| 181 | write specialized ones. |
---|
| 182 | </td></tr></tbody></table></div><p> |
---|
| 183 | There are a number of resources available to help new CBC users get started. |
---|
| 184 | This document is designed to be used in conjunction with the files in the |
---|
| 185 | Samples subdirectory of the main CBC directory (<tt class="filename">COIN/Cbc/Samples</tt>). |
---|
| 186 | The Samples illustrate how to use CBC and may also serve as useful starting points |
---|
| 187 | for user projects. In the event that either this document or the available |
---|
| 188 | <a href="#doxygen" title="AppendixÂ B.Â Doxygen">Doxygen content</a> conflicts with the observed |
---|
| 189 | behavior of the source code, the comments in the header files, found in |
---|
| 190 | <tt class="filename">COIN/Cbc/include</tt>, are the ultimate reference. |
---|
[557] | 191 | </p></div><div class="footnotes"><br /><hr width="100" align="left" /><div class="footnote"><p><sup>[<a id="ftn.id2968015" href="#id2968015">1</a>] </sup> |
---|
[555] | 192 | The complete acronym is "COIN-OR" which stands for the Compuational Infrastructure for Operations Research. For simplicity (and in keeping with the directory and function names) we will simply use "COIN". |
---|
[557] | 193 | </p></div><div class="footnote"><p><sup>[<a id="ftn.id3038892" href="#id3038892">2</a>] </sup> |
---|
| 194 | The current implementation of CBC allow two branches to be created. More general number of branches could be implemented. |
---|
| 195 | </p></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="cbcmodelclass"></a>ChapterÂ 2.Â |
---|
[555] | 196 | The CBC Model Class |
---|
| 197 | </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#hierarchy"> |
---|
| 198 | Overview |
---|
| 199 | </a></dt><dt><a href="#firstexample"> |
---|
| 200 | Simple Branch-and-Bound Example |
---|
| 201 | </a></dt><dt><a href="#osiAndCbc"> |
---|
| 202 | The Relationship Between OSI and CBC |
---|
| 203 | </a></dt><dt><a href="#gettingsolution"> |
---|
| 204 | Getting Solution Information |
---|
| 205 | </a></dt><dt><a href="#setsandgets"> |
---|
| 206 | Useful Set and Get Methods in CbcModel |
---|
| 207 | </a></dt><dt><a href="#majormethods"> |
---|
| 208 | Impacting the Solution Process |
---|
| 209 | </a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="hierarchy"></a> |
---|
| 210 | Overview |
---|
| 211 | </h2></div></div><div></div></div><p> |
---|
| 212 | The main class in CBC is <tt class="classname">CbcModel</tt>. The <tt class="classname">CbcModel</tt> class is where most |
---|
| 213 | of the parameter setting is done. The absolute minimum number of actions taken with <tt class="classname">CbcModel</tt> is two, |
---|
| 214 | </p><div class="itemizedlist"><ul type="disc"><li> |
---|
| 215 | <tt class="function">CbcModel(OsiSolverInterface & linearSolver)</tt> as constructor, and |
---|
| 216 | </li><li> |
---|
| 217 | <tt class="function">branchAndBound()</tt> for solving the problem. |
---|
| 218 | </li></ul></div><p> |
---|
| 219 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="firstexample"></a> |
---|
| 220 | Simple Branch-and-Bound Example |
---|
| 221 | </h2></div></div><div></div></div><p> |
---|
| 222 | The first sample program shows how to perform simple branch-and-bound with CBC. This program is short enough to present in full. Most of the remaining examples will take the form of small code fragments. |
---|
| 223 | The complete code for all the examples in this Guide can be found in the CBC Samples directory, <tt class="filename">COIN/Cbc/Samples</tt>. |
---|
| 224 | |
---|
| 225 | </p><div class="example"><a id="minimum.cpp"></a><p class="title"><b>ExampleÂ 2.1.Â minimum.cpp</b></p><pre class="programlisting"> |
---|
| 226 | |
---|
| 227 | // Copyright (C) 2005, International Business Machines |
---|
| 228 | // Corporation and others. All Rights Reserved. |
---|
| 229 | |
---|
| 230 | #include "CbcModel.hpp" |
---|
| 231 | |
---|
| 232 | // Using CLP as the solver |
---|
| 233 | #include "OsiClpSolverInterface.hpp" |
---|
| 234 | |
---|
| 235 | int main (int argc, const char *argv[]) |
---|
| 236 | { |
---|
| 237 | OsiClpSolverInterface solver1; |
---|
| 238 | |
---|
| 239 | // Read in example model in MPS file format |
---|
| 240 | // and assert that it is a clean model |
---|
| 241 | int numMpsReadErrors = solver1.readMps("../../Mps/Sample/p0033.mps",""); |
---|
| 242 | assert(numMpsReadErrors==0); |
---|
| 243 | |
---|
| 244 | // Pass the solver with the problem to be solved to CbcModel |
---|
| 245 | CbcModel model(solver1); |
---|
| 246 | |
---|
| 247 | // Do complete search |
---|
| 248 | model.branchAndBound(); |
---|
| 249 | |
---|
| 250 | /* Print the solution. CbcModel clones the solver so we |
---|
| 251 | need to get current copy from the CbcModel */ |
---|
| 252 | int numberColumns = model.solver()->getNumCols(); |
---|
| 253 | |
---|
[557] | 254 | const double * solution = model.bestSolution(); |
---|
[555] | 255 | |
---|
| 256 | for (int iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
| 257 | double value=solution[iColumn]; |
---|
| 258 | if (fabs(value)>1.0e-7&&model.solver()->isInteger(iColumn)) |
---|
| 259 | printf("%d has value %g\n",iColumn,value); |
---|
| 260 | } |
---|
| 261 | return 0; |
---|
| 262 | } |
---|
| 263 | |
---|
| 264 | </pre></div><p> |
---|
| 265 | The program in <a href="#minimum.cpp" title="ExampleÂ 2.1.Â minimum.cpp">ExampleÂ 2.1</a> creates a <tt class="classname">OsiClpSolverInterface</tt> solver interface (i.e., <tt class="varname">solver1</tt>), and reads an MPS file. If there are no errors, the program passes the problem to <tt class="classname">CbcModel</tt> which solves the problem using the branch-and-bound algorithm. The part of the program which solves the problem is very small (one line!) but before that one line, the LP solver (i.e., <tt class="varname">solver1</tt>) had to be created and populated with the problem. After that one line, the results were printed out. |
---|
| 266 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="osiAndCbc"></a> |
---|
| 267 | The Relationship Between OSI and CBC |
---|
| 268 | </h2></div></div><div></div></div><p> |
---|
| 269 | The program in <a href="#minimum.cpp" title="ExampleÂ 2.1.Â minimum.cpp">ExampleÂ 2.1</a> illustrates the dependency of CBC on |
---|
[557] | 270 | the <tt class="classname">OsiSolverInterface</tt> class. The constructor of <tt class="classname">CbcModel</tt> takes a pointer to an <tt class="classname">OsiSolverInterface</tt> (i.e., a solver). The <tt class="classname">CbcModel</tt> clones the solver, and uses its own instance of the solver. The <tt class="classname">CbcModel</tt>'s solver and the original solver (e.g., <tt class="varname">solver1</tt>) are not in sync unless the user synchronizes them. The user can always access the <tt class="classname">CbcModel</tt>'s solver through the <tt class="function">model()</tt> class. To synchronize the two solvers, explicitly refreshing the original, e.g., |
---|
[555] | 271 | </p><pre class="programlisting"> |
---|
| 272 | solver1 = model.solver(); |
---|
| 273 | </pre><p> |
---|
[557] | 274 | <tt class="classname">CbcModel</tt>'s method <tt class="function">solver()</tt> returns a pointer to CBC's cloned solver. |
---|
[555] | 275 | </p><p> |
---|
[557] | 276 | For convenience, many of the OSI methods to access problem data have identical method names in <tt class="classname">CbcModel</tt>. (It's just more convenient to type <tt class="function">model.getNumCols()</tt> rather than <tt class="function">model.solver()->getNumCols()</tt>). The <tt class="classname">CbcModel</tt> refreshes its solver at certain logical points during the algorithm. At these points, the information from the <tt class="classname">CbcModel</tt> <tt class="varname">model</tt> will match the information from the <tt class="function">model.solver()</tt>. Elsewhere, the information may vary. For instance, the method <tt class="function">CbcModel::bestSolution()</tt> will contain the best solution so far, the OSI method <tt class="function">getColSolution()</tt> may not. In this case, it is safer to use <tt class="function">CbcModel::bestSolution()</tt>. |
---|
[555] | 277 | </p><p> |
---|
| 278 | While all the OSI methods used in <tt class="filename">minimum.cpp</tt> have equivalent methods in <tt class="classname">CbcModel</tt>, there are some OSI methods which do not. For example, if the program produced a lot of undesired output, one might add the line |
---|
| 279 | </p><pre class="programlisting"> |
---|
| 280 | model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry); |
---|
| 281 | </pre><p> |
---|
| 282 | |
---|
| 283 | to reduce the output. There is no <tt class="function">setHintParam()</tt> method in <tt class="classname">CbcModel</tt>. |
---|
| 284 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="gettingsolution"></a> |
---|
| 285 | Getting Solution Information |
---|
| 286 | </h2></div></div><div></div></div><p> |
---|
| 287 | Optimality can be checked through a call to <tt class="function">model.isProvenOptimal()</tt>. Also |
---|
| 288 | available are <tt class="function">isProvenInfeasible()</tt>, |
---|
| 289 | <tt class="function">isSolutionLimitReached()</tt>, |
---|
| 290 | <tt class="function">isNodeLimitReached()</tt> or the feared |
---|
| 291 | <tt class="function">isAbandoned()</tt>. There is also |
---|
| 292 | <tt class="function">intÂ status()</tt> which returns 0 if finished (which includes the case when the algorithm is finished because it has been proved infeasible), 1 if stopped by user, and 2 if difficulties arose. |
---|
| 293 | </p><p> |
---|
| 294 | In addition to these <tt class="classname">CbcModel</tt> methods, solution values can be accessed via OSI methods. The OSI methods pick up the current solution in the <tt class="classname">CBCModel</tt>. The current solution will match the best solution found so far if called after <tt class="function">branchAndBound()</tt> and a solution was found. |
---|
[557] | 295 | </p><div class="table"><a id="id3040696"></a><p class="title"><b>TableÂ 2.1.Â |
---|
[555] | 296 | Methods for Getting Solution Information from OSI |
---|
| 297 | </b></p><table summary=" Methods for Getting Solution Information from OSI " border="0"><colgroup><col /><col /></colgroup><thead><tr><th> |
---|
| 298 | Purpose |
---|
| 299 | </th><th> |
---|
| 300 | Name |
---|
| 301 | </th><th> |
---|
| 302 | Notes |
---|
| 303 | </th></tr></thead><tbody><tr><td align="left" valign="top"> |
---|
| 304 | Primal column solution |
---|
| 305 | </td><td align="left" valign="top"><tt class="function">const double * getColSolution()</tt></td><td align="left" valign="top"> |
---|
| 306 | The OSI method will return the best solution found thus far, unless none has been found. It is safer to use <tt class="classname">CbcModel</tt> version, <tt class="function">CbcModel::bestSolution()</tt></td></tr><tr><td align="left" valign="top"> |
---|
| 307 | Dual row solution |
---|
| 308 | </td><td align="left" valign="top"><tt class="function">const double * getRowPrice()</tt></td><td align="left" valign="top"> |
---|
| 309 | Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getRowPrice()</tt>. |
---|
| 310 | </td></tr><tr><td align="left" valign="top"> |
---|
| 311 | Primal row solution |
---|
| 312 | </td><td align="left" valign="top"><tt class="function">const double * getRowActivity()</tt></td><td align="left" valign="top"> |
---|
| 313 | Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getRowActivity()</tt>. |
---|
| 314 | </td></tr><tr><td align="left" valign="top"> |
---|
| 315 | Dual column solution |
---|
| 316 | </td><td align="left" valign="top"><tt class="function">const double * getReducedCost()</tt></td><td align="left" valign="top"> |
---|
| 317 | Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::gtReducedCost()</tt>. |
---|
| 318 | </td></tr><tr><td align="left" valign="top"> |
---|
| 319 | Number of rows in model |
---|
| 320 | </td><td align="left" valign="top"><tt class="function">int getNumRows()</tt></td><td align="left" valign="top"> |
---|
| 321 | Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getNumRows()</tt>. Note: the number of rows can change due to cuts. |
---|
| 322 | </td></tr><tr><td align="left" valign="top"> |
---|
| 323 | Number of columns in model |
---|
| 324 | </td><td align="left" valign="top"><tt class="function">int getNumCols()</tt></td><td align="left" valign="top"> |
---|
| 325 | Identical <tt class="classname">CbcModel</tt> version available, <tt class="function">CbcModel::getNumCols()</tt>. |
---|
| 326 | </td></tr></tbody></table></div></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="setsandgets"></a> |
---|
| 327 | Useful Set and Get Methods in <tt class="classname">CbcModel</tt> |
---|
| 328 | </h2></div></div><div></div></div><p> |
---|
| 329 | Most of the parameter setting in CBC is done through <tt class="classname">CbcModel</tt> methods. The most commonly used set and get methods are listed in <a href="#setGet" title="TableÂ 2.2.Â Useful Set and Get Methods in CbcModel">TableÂ 2.2</a>. |
---|
| 330 | </p><div class="table"><a id="setGet"></a><p class="title"><b>TableÂ 2.2.Â Useful Set and Get Methods in <tt class="classname">CbcModel</tt></b></p><table summary="Useful Set and Get Methods in CbcModel" border="0"><colgroup><col /><col /></colgroup><thead><tr><th> |
---|
| 331 | Method(s) |
---|
| 332 | </th><th> |
---|
| 333 | Description |
---|
| 334 | </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="function">boolÂ setMaximumNodes(int value)</tt><br /><tt class="function">intÂ getMaximumNodes() const</tt><br /><tt class="function">boolÂ setMaximumSeconds(double value)</tt><br /><tt class="function">doubleÂ getMaximumSeconds()</tt><br /><tt class="function">boolÂ setMaximumSolutions(double value)</tt><br /><tt class="function">doubleÂ getMaximumSolutions() const</tt></td><td align="left" valign="top"> |
---|
| 335 | These set methods tell CBC to stop after a given number of nodes, |
---|
| 336 | seconds, or solutions is reached. The get methods return the corresponding values. |
---|
| 337 | </td></tr><tr><td align="left" valign="top"><tt class="function">boolÂ setIntegerTolerance(double value) const</tt><br /><tt class="function">doubleÂ getIntegerTolerance() const</tt></td><td align="left" valign="top"> |
---|
| 338 | An integer variable is deemed to be at an integral value if it is no further than this <i class="parameter"><tt>value</tt></i> (tolerance) away. |
---|
| 339 | </td></tr><tr><td align="left" valign="top"><tt class="function">boolÂ setAllowableGap(double value)</tt><br /><tt class="function">doubleÂ getAllowableGap() const</tt><br /><tt class="function">boolÂ setAllowablePercentageGap(double value)</tt><br /><tt class="function">doubleÂ getAllowablePercentageGap() const</tt><br /><tt class="function">boolÂ setAllowableFractionGap(double value)</tt><br /><tt class="function">doubleÂ getAllowableFractionGap() const</tt><br /></td><td align="left" valign="top"><tt class="classname">CbcModel</tt> returns if the gap between the best known solution and the best |
---|
| 340 | possible solution is less than this <i class="parameter"><tt>value</tt></i>, or as a percentage, or a fraction. |
---|
[557] | 341 | </td></tr><tr><td align="left" valign="top"><tt class="function">voidÂ setNumberStrong(double value) </tt><br /><tt class="function">intÂ numberStrong() |
---|
| 342 | <sup>[<a id="id3041432" href="#ftn.id3041432">a</a>]</sup> const </tt></td><td align="left" valign="top"> |
---|
[555] | 343 | These methods set or get the maximum number of candidates at a node to |
---|
| 344 | be evaluated for strong branching. |
---|
| 345 | </td></tr><tr><td align="left" valign="top"><tt class="function">voidÂ setPrintFrequency(int value) </tt><br /><tt class="function">intÂ printFrequency() const</tt></td><td align="left" valign="top"> |
---|
| 346 | Controls the number of nodes evaluated between status prints. |
---|
| 347 | Print frequency has a very slight overhead, if <i class="parameter"><tt>value</tt></i> is small. |
---|
| 348 | </td></tr><tr><td align="left" valign="top"><tt class="function">intÂ getNodeCount() const</tt></td><td align="left" valign="top"> |
---|
| 349 | Returns number of nodes evaluated in the search. |
---|
| 350 | </td></tr><tr><td align="left" valign="top"><tt class="function">intÂ numberRowsAtContinuous() const</tt></td><td align="left" valign="top"> |
---|
[557] | 351 | Returns number of rows in the problem when handed to the solver (i.e., before cuts where added). Commonly used in implementing heuristics. |
---|
| 352 | </td></tr><tr><td align="left" valign="top"><tt class="function">int Â numberIntegers() const</tt><br /><tt class="function">const intÂ *Â integerVariable() const</tt></td><td align="left" valign="top"> |
---|
[555] | 353 | Returns number of integer variables and an array specifying them. |
---|
| 354 | </td></tr><tr><td align="left" valign="top"><tt class="function">boolÂ isBinary(int colIndex) const</tt><br /><tt class="function">boolÂ isContinuous(int colIndex) const</tt><br /><tt class="function">boolÂ isInteger(int colIndex) const</tt></td><td align="left" valign="top"> |
---|
| 355 | Returns information on variable <i class="parameter"><tt>colIndex</tt></i>. OSI methods |
---|
| 356 | can be used to set these attributes (before handing the model to <tt class="classname">CbcModel</tt>). |
---|
| 357 | </td></tr><tr><td align="left" valign="top"><tt class="function">doubleÂ getObjValue() const</tt></td><td align="left" valign="top"> |
---|
| 358 | This method returns the best objective value so far. |
---|
| 359 | </td></tr><tr><td align="left" valign="top"><tt class="function">doubleÂ getCurrentObjValue() const</tt></td><td align="left" valign="top"> |
---|
| 360 | This method returns the current objective value. |
---|
| 361 | </td></tr><tr><td align="left" valign="top"><tt class="function">constÂ doubleÂ *Â getObjCoefficients() const</tt><br /></td><td align="left" valign="top"> |
---|
| 362 | This method return the objective coefficients. |
---|
| 363 | </td></tr><tr><td align="left" valign="top"><tt class="function">constÂ doubleÂ *Â getRowLower() const</tt><br /><tt class="function">constÂ doubleÂ *Â getRowUpper() const</tt><br /><tt class="function">constÂ doubleÂ *Â getColLower() const</tt><br /><tt class="function">constÂ doubleÂ *Â getColUpper() const</tt><br /></td><td align="left" valign="top"> |
---|
| 364 | These methods return the lower and upper bounds on row and column activities. |
---|
[557] | 365 | </td></tr><tr><td align="left" valign="top"><tt class="function">constÂ CoinPackedMatrixÂ *Â getMatrixByRow() const</tt></td><td align="left" valign="top"> |
---|
[555] | 366 | This method returns a pointer to a row copy of matrix stored as a |
---|
| 367 | <tt class="classname">CoinPackedMatrix</tt> which can be further examined. |
---|
[557] | 368 | </td></tr><tr><td align="left" valign="top"><tt class="function">const CoinPackedMatrix * getMatrixByCol() const</tt></td><td align="left" valign="top"> |
---|
[555] | 369 | This method returns a pointer to a column copy of matrix stored as a |
---|
| 370 | <tt class="classname">CoinPackedMatrix</tt> which can be further examined. |
---|
[557] | 371 | </td></tr><tr><td align="left" valign="top"><tt class="function">CoinBigIndexÂ getNumElements() const</tt><sup>[<a id="id3041985" href="#ftn.id3041985">b</a>]</sup></td><td align="left" valign="top"> |
---|
[555] | 372 | Returns the number of nonzero elements in the problem matrix. |
---|
| 373 | </td></tr><tr><td align="left" valign="top"><tt class="function">void setObjSense(doubleÂ value)</tt><br /><tt class="function">double getObjSense() const</tt></td><td align="left" valign="top"> |
---|
| 374 | These methods set and get the objective sense. The parameter |
---|
| 375 | <i class="parameter"><tt>value</tt></i> should be +1 to minimize and -1 to maximize. |
---|
[557] | 376 | </td></tr></tbody><tbody class="footnotes"><tr><td colspan="2"><div class="footnote"><p><sup>[<a id="ftn.id3041432" href="#id3041432">a</a>] </sup> |
---|
| 377 | This methods (and some of the other) do not follow the "get" convention. The convention has changed over time and there are still some inconsistencies to be cleaned up. |
---|
| 378 | </p></div><div class="footnote"><p><sup>[<a id="ftn.id3041985" href="#id3041985">b</a>] </sup> |
---|
[555] | 379 | <span class="type">CoinBigIndex</span> is a <tt class="function">typedef</tt> which in |
---|
| 380 | most cases is the same as <span class="type">int</span>. |
---|
| 381 | </p></div></td></tr></tbody></table></div></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="majormethods"></a> |
---|
| 382 | Impacting the Solution Process |
---|
| 383 | </h2></div></div><div></div></div><p> |
---|
| 384 | <tt class="classname">CbcModel</tt> is extremely flexible and customizable. The class structure of CBC is designed to make the most commonly desired customizations of branch-and-cut possible. These include: |
---|
| 385 | </p><div class="itemizedlist"><ul type="disc"><li> |
---|
| 386 | selecting the next node to consider in the search tree, |
---|
| 387 | </li><li> |
---|
| 388 | determining which variable to branch on, |
---|
| 389 | </li><li> |
---|
| 390 | using heuristics to generate MIP-feasible solutions quickly, |
---|
| 391 | </li><li> |
---|
| 392 | including cut generation when solving the LP-relaxations, and |
---|
| 393 | </li><li> |
---|
| 394 | invoking customized subproblem solvers. |
---|
| 395 | </li></ul></div><p> |
---|
| 396 | |
---|
| 397 | |
---|
| 398 | To enable this flexibility, <tt class="classname">CbcModel</tt> uses other classes in CBC (some of which are virtual and may have multiple instances). Not all classes are created equal. The two tables below list in alphabetical order the classes used by <tt class="classname">CbcModel</tt> that are of most interest and of least interest. |
---|
[557] | 399 | </p><div class="table"><a id="id3042180"></a><p class="title"><b>TableÂ 2.3.Â Classes Used by CbcModel - Most Useful</b></p><table summary="Classes Used by CbcModel - Most Useful" border="0"><colgroup><col /><col /><col /></colgroup><thead><tr><th> |
---|
[555] | 400 | Class name |
---|
| 401 | </th><th> |
---|
| 402 | Description |
---|
| 403 | </th><th> |
---|
| 404 | Notes |
---|
| 405 | </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcCompareBase</tt></td><td align="left" valign="top"> |
---|
| 406 | Controls which node on the tree is selected. |
---|
| 407 | </td><td align="left" valign="top"> |
---|
| 408 | The default is <tt class="classname">CbcCompareDefault</tt>. Other comparison classes in <tt class="filename">CbcCompareActual.hpp</tt> include <tt class="classname">CbcCompareDepth</tt> and <tt class="classname">CbcCompareObjective</tt>. Experimenting with these classes and creating new compare classes is easy. |
---|
| 409 | </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCutGenerator</tt></td><td align="left" valign="top"> |
---|
| 410 | A wrapper for <tt class="classname">CglCutGenerator</tt> with additional data to control when the cut generator is invoked during the tree search. |
---|
| 411 | </td><td align="left" valign="top"> |
---|
| 412 | Other than knowing how to add a cut generator to <tt class="classname">CbcModel</tt>, there is not much the average user needs to know about this class. However, sophisticated users can implement their own cut generators. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcHeuristic</tt></td><td align="left" valign="top"> |
---|
| 413 | Heuristic that attempts to generate valid MIP-solutions leading to good upper bounds. |
---|
| 414 | </td><td align="left" valign="top"> |
---|
| 415 | Specialized heuristics can dramatically improve branch-and-cut performance. As many different heuristics as desired can be used in CBC. Advanced users should consider implementing custom heuristics when tackling difficult problems. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcObject</tt></td><td align="left" valign="top"> |
---|
| 416 | Defines what it means for a variable to be satisfied. Used in branching. |
---|
| 417 | </td><td align="left" valign="top"> |
---|
[557] | 418 | Virtual class. CBC's concept of branching is based on the idea of an "object". 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 comparison of the effect of branching. Instances of objects include <tt class="classname">CbcSimpleInteger</tt>, <tt class="classname">CbcSimpleIntegerPseudoCosts</tt>, <tt class="classname">CbcClique</tt>, <tt class="classname">CbcSOS</tt> (type 1 and 2), <tt class="classname">CbcFollowOn</tt>, and <tt class="classname">CbcLotsize</tt>. |
---|
[555] | 419 | </td></tr><tr><td align="left" valign="top"><tt class="classname">OsiSolverInterface</tt></td><td align="left" valign="top"> |
---|
| 420 | Defines the LP solver being used and the LP model. Normally |
---|
| 421 | a pointer to the desired <tt class="classname">OsiSolverInteface</tt> is passed to <tt class="classname">CbcModel</tt> before branch and cut. |
---|
| 422 | </td><td align="left" valign="top"> |
---|
| 423 | Virtual class. The user instantiates the solver interface of their choice, e.g., |
---|
| 424 | <tt class="classname">OsiClpSolverInterface</tt>. |
---|
| 425 | </td></tr></tbody></table></div><p> |
---|
| 426 | There is not much about the classes listed in <a href="#least" title="TableÂ 2.4.Â Classes Used by CbcModel - Least Useful">TableÂ 2.4</a> that the average user needs to know about. |
---|
| 427 | </p><div class="table"><a id="least"></a><p class="title"><b>TableÂ 2.4.Â Classes Used by CbcModel - Least Useful</b></p><table summary="Classes Used by CbcModel - Least Useful" border="0"><colgroup><col /><col /><col /></colgroup><thead><tr><th> |
---|
| 428 | Class name |
---|
| 429 | </th><th> |
---|
| 430 | Description |
---|
| 431 | </th><th> |
---|
| 432 | Notes |
---|
| 433 | </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcBranchDecision</tt></td><td align="left" valign="top"> |
---|
| 434 | Used in choosing which variable to branch on, however, most of |
---|
| 435 | the work is done by the definitions in <tt class="classname">CbcObject</tt>. |
---|
| 436 | </td><td align="left" valign="top"> |
---|
| 437 | Defaults to <tt class="classname">CbcBranchDefaultDecision</tt>. |
---|
| 438 | </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCountRowCut</tt></td><td align="left" valign="top"> |
---|
| 439 | Interface to <tt class="classname">OsiRowCut</tt>. It counts the usage so cuts can gracefully vanish. |
---|
| 440 | </td><td align="left" valign="top"> |
---|
| 441 | See <tt class="classname">OsiRowCut</tt> for more details. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcNode</tt></td><td align="left" valign="top"> |
---|
| 442 | Controls which variable/entity is selected to be branch on. |
---|
| 443 | </td><td align="left" valign="top"> |
---|
| 444 | Controlled via <tt class="classname">CbcModel</tt> parameters. Information from <tt class="classname">CbcNode</tt> can be useful in creating customized node selection rules. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcNodeInfo</tt></td><td align="left" valign="top"> |
---|
| 445 | Contains data on bounds, basis, etc. for one node of the search tree. |
---|
| 446 | </td><td align="left" valign="top"> |
---|
| 447 | Header is located in <tt class="filename">CbcNode.hpp</tt>. </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcTree</tt></td><td align="left" valign="top"> |
---|
| 448 | Defines how the search tree is stored. |
---|
| 449 | </td><td align="left" valign="top"> |
---|
| 450 | This class can be changed but it is not likely to be modified.</td></tr><tr><td align="left" valign="top"><tt class="classname">CoinMessageHandler</tt></td><td align="left" valign="top"> |
---|
| 451 | Deals with message handling |
---|
| 452 | </td><td align="left" valign="top"> |
---|
| 453 | The user can inherit from <tt class="classname">CoinMessageHandler</tt> to specialize message handling. |
---|
| 454 | </td></tr><tr><td align="left" valign="top"><tt class="classname">CoinWarmStartBasis</tt></td><td align="left" valign="top"> |
---|
| 455 | Basis representation to be used by solver |
---|
| 456 | </td><td align="left" valign="top"></td></tr></tbody></table></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="otherclasses"></a>ChapterÂ 3.Â |
---|
| 457 | Selecting the Next Node in the Search Tree |
---|
| 458 | </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#comparison">CbcCompare - Comparison Methods</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="comparison"></a>CbcCompare - Comparison Methods</h2></div></div><div></div></div><p> |
---|
[557] | 459 | The order in which the nodes of the search tree are explored can strongly influence the performance of branch-and-cut algorithms. CBC give users complete control over the search order, including the ability to dynamically change the node selection logic as the search progresses. The search order is controlled via the <tt class="classname">CbcCompare...</tt> class, and its method <tt class="function">test()</tt>. Dynamic changes can be made whenever |
---|
| 460 | </p><div class="itemizedlist"><ul type="disc"><li>a new solution is found -- by customizing the method <tt class="function">newSolution()</tt>, or </li><li>every 1000 nodes -- by customizing the method <tt class="function">every1000Nodes()</tt>. </li></ul></div><p> |
---|
| 461 | CBC provides an abstract base class, <tt class="classname">CbcCompareBase</tt>, and implementations of several commonly used node selection strategies as Compare Classes, see <a href="#compareTable" title="TableÂ 3.1.Â Compare Classes Provided">TableÂ 3.1</a>. |
---|
[555] | 462 | </p><div class="table"><a id="compareTable"></a><p class="title"><b>TableÂ 3.1.Â Compare Classes Provided</b></p><table summary="Compare Classes Provided" border="0"><colgroup><col /><col /></colgroup><thead><tr><th> |
---|
| 463 | Class name |
---|
| 464 | </th><th> |
---|
| 465 | Description |
---|
| 466 | </th></tr></thead><tbody><tr><td align="left" valign="top"><tt class="classname">CbcCompareDepth</tt></td><td align="left" valign="top"> |
---|
| 467 | This will always choose the node deepest in tree. It gives minimum |
---|
| 468 | tree size but may take a long time to find the best solution. |
---|
| 469 | </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareObjective</tt></td><td align="left" valign="top"> |
---|
| 470 | This will always choose the node with the best objective value. This may |
---|
| 471 | give a very large tree. It is likely that the first solution found |
---|
| 472 | will be the best and the search should finish soon after the first solution |
---|
| 473 | is found. |
---|
| 474 | </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareDefault</tt></td><td align="left" valign="top"> |
---|
| 475 | This is designed to do a mostly depth-first search until a solution has |
---|
| 476 | been found. It then use estimates that are designed to give a slightly better solution. |
---|
| 477 | If a reasonable number of nodes have been explored (or a reasonable number of |
---|
[557] | 478 | solutions found), then this class will adopt a breadth-first search (i.e., making a comparison based strictly on objective function values) unless the tree is very large, in which case it will revert to depth-first search. A better description of <tt class="classname">CbcCompareUser</tt> is given below. |
---|
[555] | 479 | </td></tr><tr><td align="left" valign="top"><tt class="classname">CbcCompareEstimate</tt></td><td align="left" valign="top"> |
---|
[557] | 480 | When pseudo costs are invoked, CBC uses the psuedo costs to guess a solution. This class uses the guessed solution. |
---|
[555] | 481 | </td></tr></tbody></table></div><p> |
---|
[557] | 482 | It is relatively simple for a user to create a customized node selection by creating a new compare class instances. The code in <a href="#test" title="ExampleÂ 3.1.Â CbcCompareUser::test()">ExampleÂ 3.1</a> describes how to build a new comparison class and the reasoning behind it. The complete source can be found in <tt class="filename">CbcCompareUser.hpp</tt> and <tt class="filename">CbcCompareUser.cpp</tt>, located in the CBC Samples directory. Besides the constructor, the only method the user -must- implement in <tt class="classname">CbcCompare</tt> is <tt class="function">bool test(CbcNode* x, CbcNode* y))</tt> which returns <i class="parameter"><tt>true</tt></i> if node <i class="parameter"><tt>y</tt></i> is preferred over node <i class="parameter"><tt>x</tt></i>. In the <tt class="function">test()</tt> method, information from <tt class="classname">CbcNode</tt> can easily be used. <a href="#nodeTable" title="TableÂ 3.2.Â Information Available from CbcNode">TableÂ 3.2</a> lists some commonly used methods to access information at a node. |
---|
[555] | 483 | </p><div class="table"><a id="nodeTable"></a><p class="title"><b>TableÂ 3.2.Â Information Available from <tt class="classname">CbcNode</tt></b></p><table summary="Information Available from CbcNode" border="0"><colgroup><col /><col /></colgroup><tbody><tr><td align="left" valign="top"><tt class="function">double objectiveValue() const</tt></td><td align="left" valign="top"> |
---|
| 484 | Value of objective at the node. |
---|
| 485 | </td></tr><tr><td align="left" valign="top"><tt class="function">int numberUnsatisfied() const</tt></td><td align="left" valign="top"> |
---|
| 486 | Number of unsatisfied integers (assuming branching |
---|
| 487 | object is an integer - otherwise it might be number of unsatisfied sets). |
---|
| 488 | </td></tr><tr><td align="left" valign="top"><tt class="function">int depth() const</tt></td><td align="left" valign="top"> |
---|
| 489 | Depth of the node in the search tree. |
---|
| 490 | </td></tr><tr><td align="left" valign="top"><tt class="function">double guessedObjectiveValue() const</tt></td><td align="left" valign="top"> |
---|
| 491 | If user was setting this (e.g., if using pseudo costs). |
---|
| 492 | </td></tr><tr><td align="left" valign="top"><tt class="function">int way() const</tt></td><td align="left" valign="top"> |
---|
| 493 | The way which branching would next occur from this node |
---|
| 494 | (for more advanced use). |
---|
| 495 | </td></tr><tr><td align="left" valign="top"><tt class="function">int variable() const</tt></td><td align="left" valign="top"> |
---|
| 496 | The branching "variable" (associated with the <tt class="classname">CbcBranchingObject</tt> -- for more advanced use). |
---|
| 497 | </td></tr></tbody></table></div><p> |
---|
| 498 | </p><p> |
---|
| 499 | The node desired in the tree is often a function of the how the search is progressing. In the design of CBC, there is no information on the state of the tree. The CBC is designed so that the method |
---|
| 500 | <tt class="function">newSolution()</tt> is called whenever a solution is found and the method <tt class="function">every1000Nodes()</tt> is called every 1000 nodes. When these methods are called, the user has the opportunity to modify the |
---|
| 501 | behavior of <tt class="function">test()</tt> by adjusting their common variables (e.g., <tt class="varname">weight_</tt>). Because <tt class="classname">CbcNode</tt> has a pointer to the model, the user can also influence the search through actions such as changing the maximum time CBC is allowed, once a solution has been found (e.g., <tt class="function">CbcModel::setMaximumSeconds(double value)</tt>). In <tt class="filename">CbcCompareUser.cpp</tt> of the <tt class="filename">COIN/Cbc/Samples</tt> directory, four items of data are used. |
---|
[557] | 502 | </p><p> |
---|
[555] | 503 | </p><div class="itemizedlist"><ul type="disc"><li><p> |
---|
| 504 | 1) The number of solutions found so far |
---|
| 505 | </p></li><li><p> |
---|
| 506 | 2) The size of the tree (defined to be the number of active nodes) |
---|
| 507 | </p></li><li><p> |
---|
| 508 | 3) A weight, <tt class="varname">weight_</tt>, which is initialized to -1.0 |
---|
| 509 | </p></li><li><p> |
---|
| 510 | 4) A saved value of weight, <tt class="varname">saveWeight_</tt> (for when weight is set back to -1.0 for special reason) |
---|
| 511 | </p></li></ul></div><p> |
---|
[557] | 512 | </p><p> |
---|
| 513 | Initially, <tt class="varname">weight</tt>_ is -1.0 and the search is biased towards depth first. In |
---|
| 514 | fact, <tt class="function">test()</tt> prefers <i class="parameter"><tt>y</tt></i> if <i class="parameter"><tt>y</tt></i> has fewer unsatisfied variables. In the case of a tie, <tt class="function">test()</tt> prefers the node with the greater depth in tree. The full code for the <tt class="function">CbcCompareUser::test()</tt> method is given in <a href="#test" title="ExampleÂ 3.1.Â CbcCompareUser::test()">ExampleÂ 3.1</a>. |
---|
[555] | 515 | </p><div class="example"><a id="test"></a><p class="title"><b>ExampleÂ 3.1.Â <tt class="function">CbcCompareUser::test()</tt></b></p><pre class="programlisting"> |
---|
| 516 | |
---|
| 517 | // Returns true if y better than x |
---|
| 518 | bool |
---|
| 519 | CbcCompareUser::test (CbcNode * x, CbcNode * y) |
---|
| 520 | { |
---|
| 521 | if (weight_==-1.0) { |
---|
| 522 | // before solution |
---|
| 523 | if (x->numberUnsatisfied() > y->numberUnsatisfied()) |
---|
| 524 | return true; |
---|
| 525 | else if (x->numberUnsatisfied() < y->numberUnsatisfied()) |
---|
| 526 | return false; |
---|
| 527 | else |
---|
| 528 | return x->depth() < y->depth(); |
---|
| 529 | } else { |
---|
| 530 | // after solution. |
---|
| 531 | // note: if weight_=0, comparison is based |
---|
| 532 | // solely on objective value |
---|
| 533 | double weight = CoinMax(weight_,0.0); |
---|
| 534 | return x->objectiveValue()+ weight*x->numberUnsatisfied() > |
---|
| 535 | y->objectiveValue() + weight*y->numberUnsatisfied(); |
---|
| 536 | } |
---|
| 537 | } |
---|
| 538 | |
---|
| 539 | </pre></div><p> |
---|
[557] | 540 | CBC calls the method <tt class="function">newSolution()</tt> after a new solution is found. The method <tt class="function">newSolution()</tt> interacts with <tt class="function">test()</tt> by means of the variable <tt class="varname">weight_</tt>. If the solution was achieved by branching, a calculation is made to determine the cost per unsatisfied integer variable to go from the continuous solution to an integer solution. The variable <tt class="varname">weight_</tt> is then set to aim at a slightly better solution. From then on, <tt class="function">test()</tt> returns <i class="parameter"><tt>true</tt></i> if it seems that <i class="parameter"><tt>y</tt></i> will lead to a better solution than <i class="parameter"><tt>x</tt></i>. This source for <tt class="function">newSolution()</tt> in given in <a href="#newSolution" title="ExampleÂ 3.2.Â CbcCompareUser::newSolution()">ExampleÂ 3.2</a>. |
---|
[555] | 541 | </p><div class="example"><a id="newSolution"></a><p class="title"><b>ExampleÂ 3.2.Â <tt class="function">CbcCompareUser::newSolution()</tt></b></p><pre class="programlisting"> |
---|
| 542 | |
---|
| 543 | // This allows the test() method to change behavior by resetting weight_. |
---|
| 544 | // It is called after each new solution is found. |
---|
| 545 | void |
---|
| 546 | CbcCompareUser::newSolution(CbcModel * model, |
---|
| 547 | double objectiveAtContinuous, |
---|
| 548 | int numberInfeasibilitiesAtContinuous) |
---|
| 549 | { |
---|
| 550 | if (model->getSolutionCount()==model->getNumberHeuristicSolutions()) |
---|
[557] | 551 | return; // The number of solutions found by any means equals the |
---|
| 552 | // number of solutions, so this solution was found by rounding. |
---|
| 553 | // Ignore it. |
---|
[555] | 554 | |
---|
| 555 | // set weight_ to get close to this solution |
---|
| 556 | double costPerInteger = |
---|
| 557 | (model->getObjValue()-objectiveAtContinuous)/ |
---|
| 558 | ((double) numberInfeasibilitiesAtContinuous); |
---|
[557] | 559 | weight_ = 0.98*costPerInteger; // this aims for a solution |
---|
| 560 | // slightly better than known. |
---|
| 561 | // why 0.98? why not?! Experiment yourself. |
---|
| 562 | saveWeight_=weight_; // We're going to switching between depth-first and breadth-first |
---|
| 563 | // branching strategies, depending on what we find in the tree. |
---|
| 564 | // When doing depth first, we'll want to retrieve this weight. |
---|
| 565 | // So, let's save it. |
---|
[555] | 566 | numberSolutions_++; |
---|
| 567 | if (numberSolutions_>5) |
---|
| 568 | weight_ =0.0; // comparison in test() will be |
---|
| 569 | // based strictly on objective value. |
---|
| 570 | } |
---|
| 571 | |
---|
| 572 | </pre></div><p> |
---|
| 573 | |
---|
[557] | 574 | As the search progresses, the comparison can be modified. If many nodes (or many solutions) have been generated, then <tt class="varname">weight_</tt> is set to 0.0 leading to a breadth-first search. Breadth-first search can lead to an enormous tree. If the tree size is exceeds 10000, it may be desirable to return to a search biased towards depth first. Changing the behavior in this manner is done by the method <tt class="function">every1000Nodes</tt> shown in <a href="#everyK" title="ExampleÂ 3.3.Â CbcCompareUser::every1000Nodes()">ExampleÂ 3.3</a>. |
---|
[555] | 575 | </p><div class="example"><a id="everyK"></a><p class="title"><b>ExampleÂ 3.3.Â <tt class="function">CbcCompareUser::every1000Nodes()</tt></b></p><pre class="programlisting"> |
---|
| 576 | |
---|
[557] | 577 | // This allows the test() method to change behavior every 1000 nodes. |
---|
[555] | 578 | bool |
---|
| 579 | CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes) |
---|
| 580 | { |
---|
[557] | 581 | if (numberNodes>10000) |
---|
[555] | 582 | weight_ =0.0; // compare nodes based on objective value |
---|
[557] | 583 | // get size of tree |
---|
[555] | 584 | treeSize_ = model->tree()->size(); |
---|
| 585 | if (treeSize_>10000) { |
---|
| 586 | // set weight to reduce size most of time |
---|
| 587 | if (treeSize_>20000) |
---|
| 588 | weight_=-1.0; |
---|
[557] | 589 | else if ((numberNodes%4000)!=0) // Flip-flop between the strategies. |
---|
| 590 | // Why 4000? Why not? Experiment yourself. |
---|
[555] | 591 | weight_=-1.0; |
---|
| 592 | else |
---|
| 593 | weight_=saveWeight_; |
---|
| 594 | } |
---|
| 595 | return numberNodes==11000; // resort if first time |
---|
| 596 | } |
---|
| 597 | |
---|
| 598 | </pre></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="hueristicChap"></a>ChapterÂ 4.Â |
---|
| 599 | Getting Good Bounds in CBC |
---|
| 600 | </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#heuristics">CbcHeuristic - Heuristic Methods</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="heuristics"></a>CbcHeuristic - Heuristic Methods</h2></div></div><div></div></div><p> |
---|
| 601 | In practice, it is very useful to get a good solution reasonably fast. Any MIP-feasible solution produces an upper bound, and a good bound will greatly reduce the run time. Good solutions can satisfy the user |
---|
| 602 | on very large problems where a complete search is impossible. Obviously, heuristics are |
---|
| 603 | problem dependent, although some do have more general use. |
---|
| 604 | At present there is only one heuristic in CBC itself, <tt class="classname">CbcRounding</tt>. Hopefully, the number will grow. Other heuristics are in the <tt class="filename">COIN/Cbc/Samples</tt> |
---|
| 605 | directory. A heuristic tries to obtain a solution to the original |
---|
| 606 | problem so it only needs to consider the original rows and does not have to use the |
---|
| 607 | current bounds. CBC provides an abstract base class <tt class="classname">CbcHeuristic</tt> and a rounding heuristic in CBC. |
---|
| 608 | </p><p> |
---|
[557] | 609 | This chapter describes how to build a greedy heuristic for a set covering problem, e.g., the miplib problem fast0507. A more general (and efficient) version of the heuristic is in <tt class="filename">CbcHeuristicGreedy.hpp</tt> and <tt class="filename">CbcHeuristicGreedy.cpp</tt> located in the <tt class="filename">COIN/Cbc/Samples</tt> directory, see <a href="#moreexamples" title="ChapterÂ 8.Â More Samples ">ChapterÂ 8, <i> |
---|
[555] | 610 | More Samples |
---|
| 611 | </i></a>. |
---|
| 612 | </p><p> |
---|
| 613 | The greedy heuristic will leave all variables taking value one at this node of the |
---|
[557] | 614 | tree at value one, and will initially set all other variables to value zero. |
---|
[555] | 615 | All variables are then sorted in order of their cost |
---|
| 616 | divided by the number of entries in rows which are not yet covered. (We may randomize that |
---|
| 617 | value a bit so that ties will be broken in different ways on different runs of the heuristic.) |
---|
| 618 | The best one is choosen, and set to one. The process is repeated. Because this is |
---|
[557] | 619 | a set covering problem (i.e., all constraints are â¥), the heuristic is guaranteed to find a solution (but not necessarily an improved solution). The speed of the heuristic could be improved by just redoing those affected, but for illustrative purposes we will keep it simple. (The speed could also be improved if all elements are 1.0). |
---|
[555] | 620 | </p><p> |
---|
| 621 | The key <tt class="classname">CbcHeuristic</tt> method is <tt class="function">intÂ solution(double & solutionValue, |
---|
| 622 | doubleÂ *Â betterSolution)</tt>. |
---|
| 623 | The <tt class="function">solution()</tt> method returns 0 if no solution found, and returns 1 if a solution is found, in which case it fills in the objective value and primal solution. The code in <tt class="filename">CbcHeuristicGreedy.cpp</tt> is a little more complicated than this following example. For instance, the code here assumes all variables are integer. The important bit of data is a copy of the matrix (stored by column) before any cuts have been made. The data used are bounds, objective and the matrix plus two work arrays. |
---|
[557] | 624 | </p><div class="example"><a id="id3047001"></a><p class="title"><b>ExampleÂ 4.1.Â Data</b></p><pre class="programlisting"> |
---|
[555] | 625 | |
---|
| 626 | OsiSolverInterface * solver = model_->solver(); // Get solver from CbcModel |
---|
| 627 | const double * columnLower = solver->getColLower(); // Column Bounds |
---|
| 628 | const double * columnUpper = solver->getColUpper(); |
---|
| 629 | const double * rowLower = solver->getRowLower(); // We know we only need lower bounds |
---|
| 630 | const double * solution = solver->getColSolution(); |
---|
| 631 | const double * objective = solver->getObjCoefficients(); // In code we also use min/max |
---|
| 632 | double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
| 633 | double primalTolerance; |
---|
| 634 | solver->getDblParam(OsiPrimalTolerance,primalTolerance); |
---|
| 635 | int numberRows = originalNumberRows_; // This is number of rows when matrix was passed in |
---|
| 636 | // Column copy of matrix (before cuts) |
---|
| 637 | const double * element = matrix_.getElements(); |
---|
| 638 | const int * row = matrix_.getIndices(); |
---|
| 639 | const CoinBigIndex * columnStart = matrix_.getVectorStarts(); |
---|
| 640 | const int * columnLength = matrix_.getVectorLengths(); |
---|
| 641 | |
---|
| 642 | // Get solution array for heuristic solution |
---|
| 643 | int numberColumns = solver->getNumCols(); |
---|
| 644 | double * newSolution = new double [numberColumns]; |
---|
| 645 | // And to sum row activities |
---|
| 646 | double * rowActivity = new double[numberRows]; |
---|
| 647 | |
---|
| 648 | </pre></div><p> |
---|
| 649 | The <tt class="varname">newSolution</tt> is then initialized to the rounded down solution. |
---|
[557] | 650 | </p><div class="example"><a id="id3047030"></a><p class="title"><b>ExampleÂ 4.2.Â Initialize <tt class="varname">newSolution</tt></b></p><pre class="programlisting"> |
---|
[555] | 651 | |
---|
| 652 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
| 653 | CoinBigIndex j; |
---|
| 654 | double value = solution[iColumn]; |
---|
| 655 | // Round down integer |
---|
| 656 | if (fabs(floor(value+0.5)-value)<integerTolerance) |
---|
| 657 | value=floor(CoinMax(value+1.0e-3,columnLower[iColumn])); |
---|
| 658 | // make sure clean |
---|
| 659 | value = CoinMin(value,columnUpper[iColumn]); |
---|
| 660 | value = CoinMax(value,columnLower[iColumn]); |
---|
| 661 | newSolution[iColumn]=value; |
---|
| 662 | if (value) { |
---|
[557] | 663 | double cost = objective[iColumn]; |
---|
[555] | 664 | newSolutionValue += value*cost; |
---|
| 665 | for (j=columnStart[iColumn]; |
---|
| 666 | j<columnStart[iColumn]+columnLength[iColumn];j++) { |
---|
| 667 | int iRow=row[j]; |
---|
| 668 | rowActivity[iRow] += value*element[j]; |
---|
| 669 | } |
---|
| 670 | } |
---|
| 671 | } |
---|
| 672 | |
---|
| 673 | </pre></div><p> |
---|
| 674 | |
---|
| 675 | |
---|
[557] | 676 | At this point some row activities are below their lower bound. To correct the infeasibility, the variable which is cheapest in reducing the sum of infeasibilities is found and updated, and the process repeats. This is a finite process. (The implementation could be faster, but is kept simple for illustrative purposes.) |
---|
| 677 | </p><div class="example"><a id="id3047111"></a><p class="title"><b>ExampleÂ 4.3.Â Create Feasible <tt class="varname">newSolution</tt> from Initial <tt class="varname">newSolution</tt></b></p><pre class="programlisting"> |
---|
[555] | 678 | |
---|
| 679 | while (true) { |
---|
| 680 | // Get column with best ratio |
---|
| 681 | int bestColumn=-1; |
---|
| 682 | double bestRatio=COIN_DBL_MAX; |
---|
| 683 | for (int iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
| 684 | CoinBigIndex j; |
---|
| 685 | double value = newSolution[iColumn]; |
---|
| 686 | double cost = direction * objective[iColumn]; |
---|
| 687 | // we could use original upper rather than current |
---|
| 688 | if (value+0.99<columnUpper[iColumn]) { |
---|
| 689 | double sum=0.0; // Compute how much we will reduce infeasibility by |
---|
| 690 | for (j=columnStart[iColumn]; |
---|
| 691 | j<columnStart[iColumn]+columnLength[iColumn];j++) { |
---|
| 692 | int iRow=row[j]; |
---|
| 693 | double gap = rowLower[iRow]-rowActivity[iRow]; |
---|
| 694 | if (gap>1.0e-7) { |
---|
| 695 | sum += CoinMin(element[j],gap); |
---|
| 696 | if (element[j]+rowActivity[iRow]<rowLower[iRow]+1.0e-7) { |
---|
| 697 | sum += element[j]; |
---|
| 698 | } |
---|
| 699 | } |
---|
| 700 | if (sum>0.0) { |
---|
| 701 | double ratio = (cost/sum)*(1.0+0.1*CoinDrand48()); |
---|
| 702 | if (ratio<bestRatio) { |
---|
| 703 | bestRatio=ratio; |
---|
| 704 | bestColumn=iColumn; |
---|
| 705 | } |
---|
| 706 | } |
---|
| 707 | } |
---|
| 708 | } |
---|
| 709 | if (bestColumn<0) |
---|
| 710 | break; // we have finished |
---|
| 711 | // Increase chosen column |
---|
| 712 | newSolution[bestColumn] += 1.0; |
---|
| 713 | double cost = direction * objective[bestColumn]; |
---|
| 714 | newSolutionValue += cost; |
---|
| 715 | for (CoinBigIndex j=columnStart[bestColumn]; |
---|
| 716 | j<columnStart[bestColumn]+columnLength[bestColumn];j++) { |
---|
| 717 | int iRow = row[j]; |
---|
| 718 | rowActivity[iRow] += element[j]; |
---|
| 719 | } |
---|
| 720 | } |
---|
| 721 | |
---|
| 722 | </pre></div><p> |
---|
[557] | 723 | A solution value of <tt class="varname">newSolution</tt> is compared to the best solution value. If <tt class="varname">newSolution</tt> is an improvement, its feasibility is validated. We expect <tt class="varname">newSolution</tt> to be feasible, and are trapping for unexpected numerical errors. |
---|
| 724 | </p><div class="example"><a id="id3047155"></a><p class="title"><b>ExampleÂ 4.4.Â Check Solution Quality of <tt class="varname">newSolution</tt></b></p><pre class="programlisting"> |
---|
[555] | 725 | |
---|
| 726 | returnCode=0; // 0 means no good solution |
---|
| 727 | if (newSolutionValue<solutionValue) { // minimization |
---|
| 728 | // check feasible |
---|
| 729 | memset(rowActivity,0,numberRows*sizeof(double)); |
---|
| 730 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
| 731 | CoinBigIndex j; |
---|
| 732 | double value = newSolution[iColumn]; |
---|
| 733 | if (value) { |
---|
| 734 | for (j=columnStart[iColumn]; |
---|
| 735 | j<columnStart[iColumn]+columnLength[iColumn];j++) { |
---|
| 736 | int iRow=row[j]; |
---|
| 737 | rowActivity[iRow] += value*element[j]; |
---|
| 738 | } |
---|
| 739 | } |
---|
| 740 | } |
---|
| 741 | // check was approximately feasible |
---|
| 742 | bool feasible=true; |
---|
| 743 | for (iRow=0;iRow<numberRows;iRow++) { |
---|
| 744 | if(rowActivity[iRow]<rowLower[iRow]) { |
---|
| 745 | if (rowActivity[iRow]<rowLower[iRow]-10.0*primalTolerance) |
---|
| 746 | feasible = false; |
---|
| 747 | } |
---|
| 748 | } |
---|
| 749 | if (feasible) { |
---|
| 750 | // new solution |
---|
| 751 | memcpy(betterSolution,newSolution,numberColumns*sizeof(double)); |
---|
| 752 | solutionValue = newSolutionValue; |
---|
| 753 | // We have good solution |
---|
| 754 | returnCode=1; |
---|
| 755 | } |
---|
| 756 | } |
---|
| 757 | |
---|
| 758 | </pre></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="branchChapter"></a>ChapterÂ 5.Â |
---|
| 759 | Branching |
---|
[557] | 760 | </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#branchingIntro">Branching Overview</a></dt><dt><a href="#branching">Pseudo Cost Branching</a></dt><dt><a href="#followOn">Follow-On Branching</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="branchingIntro"></a>Branching Overview</h2></div></div><div></div></div><p> |
---|
| 761 | CBC's concept of branching is based on the idea of an "object". 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. Instances of objects include. |
---|
| 762 | </p><div class="itemizedlist"><ul type="disc"><li><tt class="classname">CbcSimpleInteger</tt>, </li><li><tt class="classname">CbcSimpleIntegerPseudoCosts</tt>, </li><li><tt class="classname">CbcClique</tt>, </li><li><tt class="classname">CbcSOS</tt> (type 1 and 2), </li><li><tt class="classname">CbcFollowOn</tt>, and </li><li><tt class="classname">CbcLotsize</tt>.</li></ul></div><p> |
---|
| 763 | In <a href="#branchChapter" title="ChapterÂ 5.Â Branching ">ChapterÂ 5, <i> |
---|
| 764 | Branching |
---|
| 765 | </i></a>, we give examples of how to use existing branching objects. (The next revision of this Guide should include an example of how to write your own branching object; Contributions of examples are welcome.) |
---|
| 766 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="branching"></a>Pseudo Cost Branching</h2></div></div><div></div></div><p> |
---|
[555] | 767 | |
---|
| 768 | If the user declares variables as integer but does no more, then CBC will treat them |
---|
| 769 | 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 |
---|
| 770 | 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. |
---|
| 771 | The full code is in <tt class="filename">longthin.cpp</tt> located in the CBC Samples directory, see |
---|
[557] | 772 | <a href="#moreexamples" title="ChapterÂ 8.Â More Samples ">ChapterÂ 8, <i> |
---|
[555] | 773 | More Samples |
---|
| 774 | </i></a>. |
---|
| 775 | </p><p> |
---|
| 776 | The idea is simple for set covering problems. |
---|
| 777 | Branching up gets us much closer to an integer solution so we will encourage that direction by branch up if variable value > 0.333333. |
---|
| 778 | The expected cost of going up obviously depends on the cost of the |
---|
| 779 | variable. The pseudo costs are choosen to reflect that fact. |
---|
| 780 | |
---|
| 781 | </p><div class="example"><a id="pseudo"></a><p class="title"><b>ExampleÂ 5.1.Â <tt class="classname">CbcSimpleIntegerPseudoCosts</tt></b></p><pre class="programlisting"> |
---|
| 782 | |
---|
| 783 | int iColumn; |
---|
| 784 | int numberColumns = solver3->getNumCols(); |
---|
| 785 | // do pseudo costs |
---|
| 786 | CbcObject ** objects = new CbcObject * [numberColumns]; |
---|
| 787 | // Point to objective |
---|
| 788 | const double * objective = model.getObjCoefficients(); |
---|
| 789 | int numberIntegers=0; |
---|
| 790 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
| 791 | if (solver3->isInteger(iColumn)) { |
---|
| 792 | double cost = objective[iColumn]; |
---|
| 793 | CbcSimpleIntegerPseudoCost * newObject = |
---|
| 794 | new CbcSimpleIntegerPseudoCost(&model,numberIntegers,iColumn, |
---|
| 795 | 2.0*cost,cost); |
---|
| 796 | newObject->setMethod(3); |
---|
| 797 | objects[numberIntegers++]= newObject; |
---|
| 798 | } |
---|
| 799 | } |
---|
| 800 | // Now add in objects (they will replace simple integers) |
---|
| 801 | model.addObjects(numberIntegers,objects); |
---|
| 802 | for (iColumn=0;iColumn<numberIntegers;iColumn++) |
---|
| 803 | delete objects[iColumn]; |
---|
| 804 | delete [] objects; |
---|
| 805 | |
---|
| 806 | </pre></div><p> |
---|
| 807 | The code in <a href="#pseudo" title="ExampleÂ 5.1.Â CbcSimpleIntegerPseudoCosts">ExampleÂ 5.1</a> also tries to give more importance to variables with more |
---|
| 808 | coefficients. Whether this sort of thing is worthwhile should be the subject of experimentation. |
---|
| 809 | |
---|
| 810 | |
---|
| 811 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="followOn"></a>Follow-On Branching</h2></div></div><div></div></div><p> |
---|
| 812 | 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. |
---|
| 813 | From DFW there may be several flights the crew could take next - suppose one flight is |
---|
| 814 | the 9:30 flight from DFW to LAX airport. A binary branch is that the crew arriving |
---|
| 815 | at DFW either take the 9:30 flight to LAX or they don't. This "follow-on" branching does not |
---|
| 816 | fix individual variables. Instead this branching divides all the variables with entries in the JFK-DFW |
---|
| 817 | constraint into two groups - those with entries in the DFW-LAX constraint and those without |
---|
| 818 | entries. |
---|
| 819 | </p><p> |
---|
| 820 | The full sample code for follow-on brancing is in <tt class="filename">crew.cpp</tt> |
---|
| 821 | located in the CBC Samples directory, see |
---|
[557] | 822 | <a href="#moreexamples" title="ChapterÂ 8.Â More Samples ">ChapterÂ 8, <i> |
---|
[555] | 823 | More Samples |
---|
| 824 | </i></a>). In this case, the simple integer |
---|
[557] | 825 | 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. |
---|
[555] | 826 | |
---|
[557] | 827 | </p><div class="example"><a id="id3047524"></a><p class="title"><b>ExampleÂ 5.2.Â <tt class="classname">CbcFollowOn</tt></b></p><pre class="programlisting"> |
---|
[555] | 828 | |
---|
| 829 | int iColumn; |
---|
| 830 | int numberColumns = solver3->getNumCols(); |
---|
| 831 | /* We are going to add a single follow-on object but we |
---|
| 832 | want to give low priority to existing integers |
---|
| 833 | As the default priority is 1000 we don't actually need to give |
---|
| 834 | integer priorities but it is here to show how. |
---|
| 835 | */ |
---|
| 836 | // Normal integer priorities |
---|
| 837 | int * priority = new int [numberColumns]; |
---|
| 838 | int numberIntegers=0; |
---|
| 839 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
| 840 | if (solver3->isInteger(iColumn)) { |
---|
| 841 | priority[numberIntegers++]= 100; // low priority |
---|
| 842 | } |
---|
| 843 | } |
---|
| 844 | /* Second parameter is set to true for objects, |
---|
| 845 | and false for integers. This indicates integers */ |
---|
| 846 | model.passInPriorities(priority,false); |
---|
| 847 | delete [] priority; |
---|
| 848 | /* Add in objects before we can give them a priority. |
---|
| 849 | In this case just one object |
---|
| 850 | - but it shows the general method |
---|
| 851 | */ |
---|
| 852 | CbcObject ** objects = new CbcObject * [1]; |
---|
| 853 | objects[0]=new CbcFollowOn(&model); |
---|
| 854 | model.addObjects(1,objects); |
---|
| 855 | delete objects[0]; |
---|
| 856 | delete [] objects; |
---|
| 857 | // High priority |
---|
| 858 | int followPriority=1; |
---|
| 859 | model.passInPriorities(&followPriority,true); |
---|
| 860 | |
---|
[557] | 861 | </pre></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="CutsChap"></a>ChapterÂ 6.Â Cutting planes</h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#cuts">Using Cut Generators with CBC</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="cuts"></a>Using Cut Generators with CBC</h2></div></div><div></div></div><p> |
---|
| 862 | In the next version of this Guide, we need to have an example illustrating how to use COIN's CGL with CBC. Contribtions are welcome. |
---|
| 863 | |
---|
| 864 | </p></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="SolverChap"></a>ChapterÂ 7.Â |
---|
| 865 | Advanced Solver Uses |
---|
[555] | 866 | </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#solver">Creating a Solver via Inheritance</a></dt><dt><a href="#quadratic">Quadratic MIP</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="solver"></a>Creating a Solver via Inheritance</h2></div></div><div></div></div><p> |
---|
| 867 | CBC uses a generic <tt class="classname">OsiSolverInterface</tt> and its <tt class="function">resolve</tt> capability. |
---|
| 868 | This does not give much flexibility so advanced users can inherit from their interface |
---|
[557] | 869 | of choice. This section illustrates how to implement a specialized solver for a long thin problem, e.g., fast0507 again. As with the other examples in the Guide, the sample code is not guaranteed to be the fastest way to solve the problem. The main purpose of the example is to illustrate techniques. The full source is in <tt class="filename">CbcSolver2.hpp</tt> and <tt class="filename">CbcSolver2.cpp</tt> located in the CBC Samples directory, see |
---|
| 870 | <a href="#moreexamples" title="ChapterÂ 8.Â More Samples ">ChapterÂ 8, <i> |
---|
[555] | 871 | More Samples |
---|
| 872 | </i></a>. |
---|
| 873 | </p><p> |
---|
| 874 | The method <tt class="function">initialSolve</tt> is called a few times in CBC, and provides a convenient starting point. The <tt class="varname">modelPtr_</tt> derives from <tt class="classname">OsiClpSolverInterface</tt>. |
---|
[557] | 875 | </p><div class="example"><a id="initialSolve"></a><p class="title"><b>ExampleÂ 7.1.Â <tt class="function">initialSolve()</tt></b></p><pre class="programlisting"> |
---|
[555] | 876 | |
---|
| 877 | // modelPtr_ is of type ClpSimplex * |
---|
| 878 | modelPtr_->setLogLevel(1); // switch on a bit of printout |
---|
| 879 | modelPtr_->scaling(0); // We don't want scaling for fast0507 |
---|
| 880 | setBasis(basis_,modelPtr_); // Put basis into ClpSimplex |
---|
| 881 | // Do long thin by sprint |
---|
| 882 | ClpSolve options; |
---|
| 883 | options.setSolveType(ClpSolve::usePrimalorSprint); |
---|
| 884 | options.setPresolveType(ClpSolve::presolveOff); |
---|
| 885 | options.setSpecialOption(1,3,15); // Do 15 sprint iterations |
---|
| 886 | modelPtr_->initialSolve(options); // solve problem |
---|
| 887 | basis_ = getBasis(modelPtr_); // save basis |
---|
| 888 | modelPtr_->setLogLevel(0); // switch off printout |
---|
| 889 | |
---|
| 890 | </pre></div><p> |
---|
| 891 | The <tt class="function">resolve()</tt> method is more complicated than <tt class="function">initialSolve()</tt>. The main pieces of data are a counter <tt class="varname">count_</tt> which is incremented each solve and an integer array <tt class="varname">node_</tt> which stores the last time |
---|
[557] | 892 | a variable was active in a solution. For the first few solves, the normal Dual Simplex is called and |
---|
[555] | 893 | <tt class="varname">node_</tt> array is updated. |
---|
[557] | 894 | </p><div class="example"><a id="id3047792"></a><p class="title"><b>ExampleÂ 7.2.Â First Few Solves</b></p><pre class="programlisting"> |
---|
[555] | 895 | |
---|
| 896 | if (count_<10) { |
---|
| 897 | OsiClpSolverInterface::resolve(); // Normal resolve |
---|
| 898 | if (modelPtr_->status()==0) { |
---|
| 899 | count_++; // feasible - save any nonzero or basic |
---|
| 900 | const double * solution = modelPtr_->primalColumnSolution(); |
---|
| 901 | for (int i=0;i<numberColumns;i++) { |
---|
| 902 | if (solution[i]>1.0e-6||modelPtr_->getStatus(i)==ClpSimplex::basic) { |
---|
| 903 | node_[i]=CoinMax(count_,node_[i]); |
---|
| 904 | howMany_[i]++; |
---|
| 905 | } |
---|
| 906 | } |
---|
| 907 | } else { |
---|
| 908 | printf("infeasible early on\n"); |
---|
| 909 | } |
---|
| 910 | } |
---|
| 911 | |
---|
| 912 | </pre></div><p> |
---|
| 913 | After the first few solves, only those variables which took part in a solution in the last so many |
---|
| 914 | solves are used. As fast0507 is a set covering problem, any rows which are already covered can be taken out. |
---|
[557] | 915 | </p><div class="example"><a id="id3047820"></a><p class="title"><b>ExampleÂ 7.3.Â Create Small Sub-Problem</b></p><pre class="programlisting"> |
---|
[555] | 916 | |
---|
| 917 | int * whichRow = new int[numberRows]; // Array to say which rows used |
---|
| 918 | int * whichColumn = new int [numberColumns]; // Array to say which columns used |
---|
| 919 | int i; |
---|
| 920 | const double * lower = modelPtr_->columnLower(); |
---|
| 921 | const double * upper = modelPtr_->columnUpper(); |
---|
| 922 | setBasis(basis_,modelPtr_); // Set basis |
---|
| 923 | int nNewCol=0; // Number of columns in small model |
---|
| 924 | // Column copy of matrix |
---|
| 925 | const double * element = modelPtr_->matrix()->getElements(); |
---|
| 926 | const int * row = modelPtr_->matrix()->getIndices(); |
---|
| 927 | const CoinBigIndex * columnStart = modelPtr_->matrix()->getVectorStarts(); |
---|
| 928 | const int * columnLength = modelPtr_->matrix()->getVectorLengths(); |
---|
| 929 | |
---|
| 930 | int * rowActivity = new int[numberRows]; // Number of columns with entries in each row |
---|
| 931 | memset(rowActivity,0,numberRows*sizeof(int)); |
---|
| 932 | int * rowActivity2 = new int[numberRows]; // Lower bound on row activity for each row |
---|
| 933 | memset(rowActivity2,0,numberRows*sizeof(int)); |
---|
| 934 | char * mark = (char *) modelPtr_->dualColumnSolution(); // Get some space to mark columns |
---|
| 935 | memset(mark,0,numberColumns); |
---|
| 936 | for (i=0;i<numberColumns;i++) { |
---|
| 937 | bool choose = (node_[i]>count_-memory_&&node_[i]>0); // Choose if used recently |
---|
| 938 | // Take if used recently or active in some sense |
---|
| 939 | if ((choose&&upper[i]) |
---|
| 940 | ||(modelPtr_->getStatus(i)!=ClpSimplex::atLowerBound&& |
---|
| 941 | modelPtr_->getStatus(i)!=ClpSimplex::isFixed) |
---|
| 942 | ||lower[i]>0.0) { |
---|
| 943 | mark[i]=1; // mark as used |
---|
| 944 | whichColumn[nNewCol++]=i; // add to list |
---|
| 945 | CoinBigIndex j; |
---|
| 946 | double value = upper[i]; |
---|
| 947 | if (value) { |
---|
| 948 | for (j=columnStart[i]; |
---|
| 949 | j<columnStart[i]+columnLength[i];j++) { |
---|
| 950 | int iRow=row[j]; |
---|
| 951 | assert (element[j]==1.0); |
---|
| 952 | rowActivity[iRow] ++; // This variable can cover this row |
---|
| 953 | } |
---|
| 954 | if (lower[i]>0.0) { |
---|
| 955 | for (j=columnStart[i]; |
---|
| 956 | j<columnStart[i]+columnLength[i];j++) { |
---|
| 957 | int iRow=row[j]; |
---|
| 958 | rowActivity2[iRow] ++; // This row redundant |
---|
| 959 | } |
---|
| 960 | } |
---|
| 961 | } |
---|
| 962 | } |
---|
| 963 | } |
---|
| 964 | int nOK=0; // Use to count rows which can be covered |
---|
| 965 | int nNewRow=0; // Use to make list of rows needed |
---|
| 966 | for (i=0;i<numberRows;i++) { |
---|
| 967 | if (rowActivity[i]) |
---|
| 968 | nOK++; |
---|
| 969 | if (!rowActivity2[i]) |
---|
| 970 | whichRow[nNewRow++]=i; // not satisfied |
---|
| 971 | else |
---|
| 972 | modelPtr_->setRowStatus(i,ClpSimplex::basic); // make slack basic |
---|
| 973 | } |
---|
| 974 | if (nOK<numberRows) { |
---|
| 975 | // The variables we have do not cover rows - see if we can find any that do |
---|
| 976 | for (i=0;i<numberColumns;i++) { |
---|
| 977 | if (!mark[i]&&upper[i]) { |
---|
| 978 | CoinBigIndex j; |
---|
| 979 | int good=0; |
---|
| 980 | for (j=columnStart[i]; |
---|
| 981 | j<columnStart[i]+columnLength[i];j++) { |
---|
| 982 | int iRow=row[j]; |
---|
| 983 | if (!rowActivity[iRow]) { |
---|
| 984 | rowActivity[iRow] ++; |
---|
| 985 | good++; |
---|
| 986 | } |
---|
| 987 | } |
---|
| 988 | if (good) { |
---|
| 989 | nOK+=good; // This covers - put in list |
---|
| 990 | whichColumn[nNewCol++]=i; |
---|
| 991 | } |
---|
| 992 | } |
---|
| 993 | } |
---|
| 994 | } |
---|
| 995 | delete [] rowActivity; |
---|
| 996 | delete [] rowActivity2; |
---|
| 997 | if (nOK<numberRows) { |
---|
| 998 | // By inspection the problem is infeasible - no need to solve |
---|
| 999 | modelPtr_->setProblemStatus(1); |
---|
| 1000 | delete [] whichRow; |
---|
| 1001 | delete [] whichColumn; |
---|
| 1002 | printf("infeasible by inspection\n"); |
---|
| 1003 | return; |
---|
| 1004 | } |
---|
| 1005 | // Now make up a small model with the right rows and columns |
---|
| 1006 | ClpSimplex * temp = new ClpSimplex(modelPtr_,nNewRow,whichRow,nNewCol,whichColumn); |
---|
| 1007 | |
---|
| 1008 | </pre></div><p> |
---|
[557] | 1009 | If the variables cover the rows, then the problem is feasible (no cuts are being used). (If the rows |
---|
| 1010 | were equality constraints, then this might not be the case. More work would be needed.) After the solution to the subproblem, the reduced costs of the full problem are checked. If the reduced cost of any variable not in the subproblem is negative, the code goes back to the full problem and cleans up with Primal Simplex. |
---|
| 1011 | </p><div class="example"><a id="id3047866"></a><p class="title"><b>ExampleÂ 7.4.Â Check Optimal Solution</b></p><pre class="programlisting"> |
---|
[555] | 1012 | |
---|
| 1013 | temp->setDualObjectiveLimit(1.0e50); // Switch off dual cutoff as problem is restricted |
---|
| 1014 | temp->dual(); // solve |
---|
| 1015 | double * solution = modelPtr_->primalColumnSolution(); // put back solution |
---|
| 1016 | const double * solution2 = temp->primalColumnSolution(); |
---|
| 1017 | memset(solution,0,numberColumns*sizeof(double)); |
---|
| 1018 | for (i=0;i<nNewCol;i++) { |
---|
| 1019 | int iColumn = whichColumn[i]; |
---|
| 1020 | solution[iColumn]=solution2[i]; |
---|
| 1021 | modelPtr_->setStatus(iColumn,temp->getStatus(i)); |
---|
| 1022 | } |
---|
| 1023 | double * rowSolution = modelPtr_->primalRowSolution(); |
---|
| 1024 | const double * rowSolution2 = temp->primalRowSolution(); |
---|
| 1025 | double * dual = modelPtr_->dualRowSolution(); |
---|
| 1026 | const double * dual2 = temp->dualRowSolution(); |
---|
| 1027 | memset(dual,0,numberRows*sizeof(double)); |
---|
| 1028 | for (i=0;i<nNewRow;i++) { |
---|
| 1029 | int iRow=whichRow[i]; |
---|
| 1030 | modelPtr_->setRowStatus(iRow,temp->getRowStatus(i)); |
---|
| 1031 | rowSolution[iRow]=rowSolution2[i]; |
---|
| 1032 | dual[iRow]=dual2[i]; |
---|
| 1033 | } |
---|
| 1034 | // See if optimal |
---|
| 1035 | double * dj = modelPtr_->dualColumnSolution(); |
---|
| 1036 | // get reduced cost for large problem |
---|
| 1037 | // this assumes minimization |
---|
| 1038 | memcpy(dj,modelPtr_->objective(),numberColumns*sizeof(double)); |
---|
| 1039 | modelPtr_->transposeTimes(-1.0,dual,dj); |
---|
| 1040 | modelPtr_->setObjectiveValue(temp->objectiveValue()); |
---|
| 1041 | modelPtr_->setProblemStatus(0); |
---|
| 1042 | int nBad=0; |
---|
| 1043 | |
---|
| 1044 | for (i=0;i<numberColumns;i++) { |
---|
| 1045 | if (modelPtr_->getStatus(i)==ClpSimplex::atLowerBound |
---|
| 1046 | &&upper[i]>lower[i]&&dj[i]<-1.0e-5) |
---|
| 1047 | nBad++; |
---|
| 1048 | } |
---|
| 1049 | // If necessary clean up with primal (and save some statistics) |
---|
| 1050 | if (nBad) { |
---|
| 1051 | timesBad_++; |
---|
| 1052 | modelPtr_->primal(1); |
---|
| 1053 | iterationsBad_ += modelPtr_->numberIterations(); |
---|
| 1054 | } |
---|
| 1055 | |
---|
| 1056 | </pre></div><p> |
---|
| 1057 | The array <tt class="varname">node_</tt> is updated, as for the first few solves. To give some idea of the effect of this tactic, the problem fast0507 has 63,009 variables but the small problem never has more than 4,000 variables. In only about ten percent of solves was it necessary to resolve, and then the average number of iterations |
---|
| 1058 | on full problem was less than 20. |
---|
| 1059 | </p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="quadratic"></a>Quadratic MIP</h2></div></div><div></div></div><p> |
---|
| 1060 | To give another example - again only for illustrative purposes -- it is possible to do quadratic |
---|
| 1061 | MIP with CBC. In this case, we make <tt class="function">resolve</tt> the same as |
---|
| 1062 | <tt class="function">initialSolve</tt>. |
---|
| 1063 | The full code is in <tt class="filename">ClpQuadInterface.hpp</tt> and |
---|
| 1064 | <tt class="filename">ClpQuadInterface.cpp</tt> located in the CBC Samples directory, see |
---|
[557] | 1065 | <a href="#moreexamples" title="ChapterÂ 8.Â More Samples ">ChapterÂ 8, <i> |
---|
[555] | 1066 | More Samples |
---|
| 1067 | </i></a>). |
---|
[557] | 1068 | </p><div class="example"><a id="id3047932"></a><p class="title"><b>ExampleÂ 7.5.Â Solving a Quadratic MIP</b></p><pre class="programlisting"> |
---|
[555] | 1069 | |
---|
| 1070 | // save cutoff |
---|
| 1071 | double cutoff = modelPtr_->dualObjectiveLimit(); |
---|
| 1072 | modelPtr_->setDualObjectiveLimit(1.0e50); |
---|
| 1073 | modelPtr_->scaling(0); |
---|
| 1074 | modelPtr_->setLogLevel(0); |
---|
| 1075 | // solve with no objective to get feasible solution |
---|
| 1076 | setBasis(basis_,modelPtr_); |
---|
| 1077 | modelPtr_->dual(); |
---|
| 1078 | basis_ = getBasis(modelPtr_); |
---|
| 1079 | modelPtr_->setDualObjectiveLimit(cutoff); |
---|
| 1080 | if (modelPtr_->problemStatus()) |
---|
| 1081 | return; // problem was infeasible |
---|
| 1082 | // Now pass in quadratic objective |
---|
| 1083 | ClpObjective * saveObjective = modelPtr_->objectiveAsObject(); |
---|
| 1084 | modelPtr_->setObjectivePointer(quadraticObjective_); |
---|
[557] | 1085 | modelPtr_->primal(); // Th model has a quadratic objective, |
---|
| 1086 | // so this invokes quadratic primal. |
---|
[555] | 1087 | modelPtr_->setDualObjectiveLimit(cutoff); |
---|
| 1088 | if (modelPtr_->objectiveValue()>cutoff) |
---|
| 1089 | modelPtr_->setProblemStatus(1); |
---|
| 1090 | modelPtr_->setObjectivePointer(saveObjective); |
---|
| 1091 | |
---|
[557] | 1092 | </pre></div><p> |
---|
| 1093 | Rather than implementing all the method from scratch, we based the quadratic solver <tt class="classname">ClpQuadInteface</tt> on the linear programming solver <tt class="classname">OsiClpSolverInterface</tt>. This is a convenient approach to take when prototyping ideas. After the merit of an idea is proven, the user can decide is a more serious implementation is warranted. |
---|
| 1094 | </p></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="moreexamples"></a>ChapterÂ 8.Â |
---|
[555] | 1095 | More Samples |
---|
[557] | 1096 | </h2></div></div><div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><a href="#id3049424">CBC's Samples Directory</a></dt></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id3049424"></a>CBC's Samples Directory</h2></div></div><div></div></div><p> |
---|
[555] | 1097 | The CBC distribution includes a number of <tt class="filename">.cpp</tt> sample files. |
---|
| 1098 | Users are encouraged to use them as starting points for their own CBC projects. |
---|
| 1099 | The files can be found in the <tt class="filename">COIN/Cbc/Samples/</tt> directory. |
---|
| 1100 | For the latest information on compiling and running these samples, please see |
---|
| 1101 | the file <tt class="filename">COIN/Cbc/Samples/INSTALL</tt>. Most of them can be built |
---|
| 1102 | by </p><pre class="programlisting">make DRIVER=name</pre><p> which produces an executable <tt class="filename">testit</tt>. Below is a list of |
---|
| 1103 | some of the most useful sample files with a short description for each file. |
---|
[557] | 1104 | </p><div class="table"><a id="id3050381"></a><p class="title"><b>TableÂ 8.1.Â Basic Samples</b></p><table summary="Basic Samples" border="0"><colgroup><col /><col /></colgroup><thead><tr><th align="left" valign="bottom"> |
---|
[555] | 1105 | Source fileÂ Â Â Â Â Â Â |
---|
| 1106 | </th><th align="left" valign="bottom"> |
---|
| 1107 | Description |
---|
| 1108 | </th></tr></thead><tbody><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/minimum.cpp" target="_top"><tt class="filename">minimum.cpp</tt></a></td><td align="left" valign="top"> |
---|
| 1109 | This is a CBC "Hello, world" program. It reads a problem |
---|
| 1110 | in MPS file format, and solves the problem using simple branch-and-bound. |
---|
| 1111 | </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/sample2.cpp" target="_top"><tt class="filename">sample2.cpp</tt></a></td><td align="left" valign="top"> |
---|
| 1112 | This is designed to be a file that a user could modify to get a useful |
---|
| 1113 | driver program for his or her project. In particular, it demonstrates |
---|
| 1114 | the use of CGL's preprocess functionality. |
---|
| 1115 | It uses <tt class="function">CbcBranchUser.cpp</tt>, |
---|
| 1116 | <tt class="function">CbcCompareUser.cpp</tt> and |
---|
| 1117 | <tt class="function">CbcHeuristicUser.cpp</tt> |
---|
| 1118 | with corresponding <tt class="function">*.hpp</tt> files. |
---|
[557] | 1119 | </td></tr></tbody></table></div><div class="table"><a id="id3050556"></a><p class="title"><b>TableÂ 8.2.Â Advanced Samples</b></p><table summary="Advanced Samples" border="0"><colgroup><col /><col /></colgroup><thead><tr><th align="left" valign="bottom"> |
---|
[555] | 1120 | Source fileÂ Â Â Â Â Â Â |
---|
| 1121 | </th><th align="left" valign="bottom"> |
---|
| 1122 | Description |
---|
| 1123 | </th></tr></thead><tbody><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/crew.cpp" target="_top"><tt class="filename">crew.cpp</tt></a></td><td align="left" valign="top"> |
---|
| 1124 | This sample shows the use of advanced branching and a use of priorities. |
---|
| 1125 | It uses <tt class="function">CbcCompareUser.cpp</tt> |
---|
| 1126 | with corresponding <tt class="function">*.hpp</tt> files. |
---|
| 1127 | </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/longthin.cpp" target="_top"><tt class="filename">longthin.cpp</tt></a></td><td align="left" valign="top"> |
---|
| 1128 | This sample shows the advanced use of a solver. It also has coding for |
---|
| 1129 | a greedy heuristic. |
---|
| 1130 | The solver is given in <tt class="function">CbcSolver2.hpp</tt> and |
---|
| 1131 | <tt class="function">CbcSolver2.cpp</tt>. |
---|
| 1132 | The heuristic is given in <tt class="function">CbcHeuristicGreedy.hpp</tt> and |
---|
| 1133 | <tt class="function">CbcHeuristicGreedy.cpp</tt>. |
---|
| 1134 | It uses <tt class="function">CbcBranchUser.cpp</tt> and |
---|
| 1135 | <tt class="function">CbcCompareUser.cpp</tt> |
---|
| 1136 | with corresponding <tt class="function">*.hpp</tt> files. |
---|
| 1137 | </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/qmip.cpp" target="_top"><tt class="filename">qmip.cpp</tt></a></td><td align="left" valign="top"> |
---|
| 1138 | This solves a quadratic MIP. It is to show advanced use of a solver. |
---|
| 1139 | The solver is given in <tt class="function">ClpQuadInterface.hpp</tt> and |
---|
| 1140 | <tt class="function">ClpQuadInterface.cpp</tt>. |
---|
| 1141 | It uses <tt class="function">CbcBranchUser.cpp</tt> and |
---|
| 1142 | <tt class="function">CbcCompareUser.cpp</tt> |
---|
| 1143 | with corresponding <tt class="function">*.hpp</tt> files. |
---|
| 1144 | </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/sos.cpp" target="_top"><tt class="filename">sos.cpp</tt></a></td><td align="left" valign="top"> |
---|
| 1145 | This artificially creates a Special Ordered Set problem. |
---|
| 1146 | </td></tr><tr><td align="left" valign="top"><a href="http://www.coin-or.org/cgi-bin/cvsweb.cgi/COIN/Cbc/Samples/lotsize.cpp" target="_top"><tt class="filename">lotsize.cpp</tt></a></td><td align="left" valign="top"> |
---|
| 1147 | This artificially creates a Lot Sizing problem. |
---|
[557] | 1148 | </td></tr></tbody></table></div></div></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="messages"></a>ChapterÂ 9.Â |
---|
[555] | 1149 | Messages |
---|
| 1150 | </h2></div></div><div></div></div><p> |
---|
| 1151 | Messages and codes passed by CBC are listed in the |
---|
| 1152 | tables below. For a complete list, see <tt class="filename">COIN/Cbc/CbcMessages.cpp</tt>. The notation used is the same as for the <tt class="function">printf</tt> in the C programming language. |
---|
| 1153 | </p><div class="itemizedlist"><ul type="disc"><li> |
---|
| 1154 | <tt class="computeroutput">%s</tt> is a string |
---|
| 1155 | </li><li> |
---|
| 1156 | <tt class="computeroutput">%d</tt> is an integer |
---|
| 1157 | </li><li> |
---|
| 1158 | <tt class="computeroutput">%g</tt> or <tt class="computeroutput">%f</tt> |
---|
| 1159 | is a floating point value |
---|
| 1160 | </li></ul></div><p> |
---|
| 1161 | |
---|
| 1162 | </p><p>There are several log levels. Setting the log level to be <i class="parameter"><tt>i</tt></i> produces the log messages for level <i class="parameter"><tt>i</tt></i> and all levels less than <i class="parameter"><tt>i</tt></i>. |
---|
| 1163 | </p><div class="itemizedlist"><ul type="disc"><li> |
---|
[557] | 1164 | Log Level 0: Switches off all CBC messages, but one. |
---|
[555] | 1165 | </li><li> |
---|
[557] | 1166 | Log Level 1: The default. |
---|
[555] | 1167 | </li><li> |
---|
[557] | 1168 | Log Level 2: Substantial amount of information, e.g., message 15 is generated once per node. Can be useful when the evaluation at each node is slow. |
---|
[555] | 1169 | </li><li> |
---|
[557] | 1170 | Log Level 3: Tremendous amount of information, e.g., multiple messages per node. |
---|
| 1171 | </li></ul></div><div class="table"><a id="id3051858"></a><p class="title"><b>TableÂ 9.1.Â |
---|
| 1172 | CBC Messages Passed At Log Level 0 |
---|
| 1173 | </b></p><table summary=" CBC Messages Passed At Log Level 0 " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center"> |
---|
[555] | 1174 | Code |
---|
| 1175 | </th><th>Â </th><th align="left"> |
---|
| 1176 | Text and notes |
---|
| 1177 | </th><td class="auto-generated">Â </td></tr></thead><tbody><tr><td align="left"> |
---|
| 1178 | 3007 |
---|
| 1179 | </td><td>Â </td><td align="left"><tt class="computeroutput">No integer variables - nothing to do</tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1180 | |
---|
[557] | 1181 | </p></td><td class="auto-generated">Â </td></tr></tbody></table></div><div class="table"><a id="id3052003"></a><p class="title"><b>TableÂ 9.2.Â |
---|
| 1182 | CBC Messages Passed At or Above Log Level 1 |
---|
| 1183 | </b></p><table summary=" CBC Messages Passed At or Above Log Level 1 " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center"> |
---|
[555] | 1184 | Code |
---|
| 1185 | </th><th>Â </th><th align="left"> |
---|
| 1186 | Text and notes |
---|
| 1187 | </th><td class="auto-generated">Â </td></tr></thead><tbody><tr><td align="left"> |
---|
| 1188 | 1 |
---|
| 1189 | </td><td>Â </td><td align="left"><tt class="computeroutput">Search completed - best objective %g, took %d iterations and %d nodes |
---|
| 1190 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1191 | |
---|
| 1192 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1193 | 3 |
---|
| 1194 | </td><td>Â </td><td align="left"><tt class="computeroutput">Exiting on maximum nodes |
---|
| 1195 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1196 | |
---|
| 1197 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1198 | 4 |
---|
| 1199 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1200 | Integer solution of %g found after %d iterations and %d nodes |
---|
| 1201 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1202 | |
---|
| 1203 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1204 | 5 |
---|
| 1205 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1206 | Partial search - best objective %g (best possible %g), took %d iterations and %d nodes |
---|
| 1207 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1208 | |
---|
| 1209 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1210 | 6 |
---|
| 1211 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1212 | The LP relaxation is infeasible or too expensive |
---|
| 1213 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1214 | |
---|
| 1215 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1216 | 9 |
---|
| 1217 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1218 | Objective coefficients multiple of %g |
---|
| 1219 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1220 | |
---|
| 1221 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1222 | 10 |
---|
| 1223 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1224 | After %d nodes, %d on tree, %g best solution, best possible %g |
---|
| 1225 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1226 | |
---|
| 1227 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1228 | 11 |
---|
| 1229 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1230 | Exiting as integer gap of %g less than %g or %g%% |
---|
| 1231 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1232 | |
---|
| 1233 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1234 | 12 |
---|
| 1235 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1236 | Integer solution of %g found by heuristic after %d iterations and %d nodes |
---|
| 1237 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1238 | |
---|
| 1239 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1240 | 13 |
---|
| 1241 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1242 | At root node, %d cuts changed objective from %g to %g in %d passes |
---|
| 1243 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1244 | |
---|
| 1245 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1246 | 14 |
---|
| 1247 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1248 | Cut generator %d (%s) - %d row cuts (%d active), %d column cuts %? in %g seconds - new frequency is %d |
---|
| 1249 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1250 | |
---|
| 1251 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1252 | 16 |
---|
| 1253 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1254 | Integer solution of %g found by strong branching after %d iterations and %d nodes |
---|
| 1255 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1256 | |
---|
| 1257 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1258 | 17 |
---|
| 1259 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1260 | %d solved, %d variables fixed, %d tightened |
---|
| 1261 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1262 | |
---|
| 1263 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1264 | 18 |
---|
| 1265 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1266 | After tightenVubs, %d variables fixed, %d tightened |
---|
| 1267 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1268 | |
---|
| 1269 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1270 | 19 |
---|
| 1271 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1272 | Exiting on maximum solutions |
---|
| 1273 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1274 | |
---|
| 1275 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1276 | 20 |
---|
| 1277 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1278 | Exiting on maximum time |
---|
| 1279 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1280 | |
---|
| 1281 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1282 | 23 |
---|
| 1283 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1284 | Cutoff set to %g - equivalent to best solution of %g |
---|
| 1285 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1286 | |
---|
| 1287 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1288 | 24 |
---|
| 1289 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1290 | Integer solution of %g found by subtree after %d iterations and %d nodes |
---|
| 1291 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1292 | |
---|
| 1293 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1294 | 26 |
---|
| 1295 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1296 | Setting priorities for objects %d to %d inclusive (out of %d) |
---|
| 1297 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1298 | |
---|
| 1299 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1300 | 3008 |
---|
| 1301 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1302 | Strong branching is fixing too many variables, too expensively! |
---|
| 1303 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1304 | |
---|
[557] | 1305 | </p></td><td class="auto-generated">Â </td></tr></tbody></table></div><div class="table"><a id="id3053367"></a><p class="title"><b>TableÂ 9.3.Â |
---|
| 1306 | CBC Messages Passed At or Above Log Level 2 |
---|
| 1307 | </b></p><table summary=" CBC Messages Passed At or Above Log Level 2 " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center"> |
---|
[555] | 1308 | Code |
---|
| 1309 | </th><th>Â </th><th align="left"> |
---|
| 1310 | Text and notes |
---|
| 1311 | </th><td class="auto-generated">Â </td></tr></thead><tbody><tr><td align="left"> |
---|
| 1312 | 15 |
---|
| 1313 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1314 | Node %d Obj %g Unsat %d depth %d |
---|
| 1315 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1316 | |
---|
| 1317 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1318 | 21 |
---|
| 1319 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1320 | On closer inspection node is infeasible |
---|
| 1321 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1322 | |
---|
| 1323 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1324 | 22 |
---|
| 1325 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1326 | On closer inspection objective value of %g above cutoff of %g |
---|
| 1327 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1328 | |
---|
| 1329 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1330 | 23 |
---|
| 1331 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1332 | Allowing solution, even though largest row infeasibility is %g |
---|
| 1333 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1334 | |
---|
[557] | 1335 | </p></td><td class="auto-generated">Â </td></tr></tbody></table></div><div class="table"><a id="id3053768"></a><p class="title"><b>TableÂ 9.4.Â |
---|
| 1336 | CBC Messages Passed At or Above Log Level 3 |
---|
| 1337 | </b></p><table summary=" CBC Messages Passed At or Above Log Level 3 " border="0"><colgroup><col /><col /><col /><col /></colgroup><thead><tr><th align="center"> |
---|
[555] | 1338 | Code |
---|
| 1339 | </th><th>Â </th><th align="left"> |
---|
| 1340 | Text and notes |
---|
| 1341 | </th><td class="auto-generated">Â </td></tr></thead><tbody><tr><td align="left"> |
---|
| 1342 | 7 |
---|
| 1343 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1344 | Strong branching on %d (%d), down %g (%d) up %g (%d) value %g |
---|
| 1345 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1346 | |
---|
| 1347 | </p></td><td class="auto-generated">Â </td></tr><tr><td align="left"> |
---|
| 1348 | 25 |
---|
| 1349 | </td><td>Â </td><td align="left"><tt class="computeroutput"> |
---|
| 1350 | %d cleanup iterations before strong branching |
---|
| 1351 | </tt></td><td class="auto-generated">Â </td></tr><tr><td colspan="2">Â </td><td align="left"><p> |
---|
| 1352 | |
---|
[557] | 1353 | </p></td><td class="auto-generated">Â </td></tr></tbody></table></div></div><div class="appendix" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="id3055917"></a>AppendixÂ A.Â FAQ</h2></div></div><div></div></div><div class="qandaset"><table border="0" summary="Q and A Set"><col align="left" width="1%" /><tbody><tr class="question"><td align="left" valign="top"><a id="id3055281"></a><a id="id3055940"></a><b>Q:. </b></td><td align="left" valign="top"><p> |
---|
[555] | 1354 | What is <a href="http://www.coin-or.org/faqs.html#CBC" target="_top">CBC</a>? |
---|
| 1355 | </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p> |
---|
| 1356 | The <a href="http://www.coin-or.org/" target="_top">COIN-OR</a> Branch and Cut code |
---|
| 1357 | is designed to be a high quality mixed integer code provided under the terms of the |
---|
| 1358 | <a href="http://opensource.org/licenses/cpl.php" target="_top">Common Public License</a>. |
---|
| 1359 | CBC is written in C++, and is primarily intended to be used as a callable |
---|
| 1360 | library (though a rudimentary stand-alone executable exists). |
---|
| 1361 | The first documented release was .90.0 The current release is version .90.0. (JF 04/01/05) |
---|
[557] | 1362 | </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3055996"></a><a id="id3055999"></a><b>Q:. </b></td><td align="left" valign="top"><p> |
---|
[555] | 1363 | What are some of the features of CBC? |
---|
| 1364 | </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p> |
---|
| 1365 | CBC allows the use of any CGL cuts and the use of heuristics and |
---|
| 1366 | specialized branching methods. (JF 04/01/05) |
---|
[557] | 1367 | </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3056934"></a><a id="id3056937"></a><b>Q:. </b></td><td align="left" valign="top"><p> |
---|
[555] | 1368 | How do I obtain and install CBC? |
---|
| 1369 | </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p> |
---|
| 1370 | Please see the |
---|
| 1371 | <a href="http://www.coin-or.org/faqs.html" target="_top">COIN-OR FAQ</a> |
---|
| 1372 | for details on how to |
---|
| 1373 | <a href="http://www.coin-or.org/faqs.html#ObtainSrcCode" target="_top">obtain</a> |
---|
| 1374 | and |
---|
| 1375 | <a href="http://www.coin-or.org/faqs.html#BuildCode" target="_top">install</a> |
---|
| 1376 | COIN-OR modules. (JF 04/01/05) |
---|
[557] | 1377 | </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3056984"></a><a id="id3056987"></a><b>Q:. </b></td><td align="left" valign="top"><p> |
---|
[555] | 1378 | Is CBC reliable? |
---|
| 1379 | </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p> |
---|
| 1380 | CBC has been tested on many problems, |
---|
| 1381 | but more testing and improvement is needed before it can get to version 1.0. (JF 04/01/05) |
---|
[557] | 1382 | </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3057009"></a><a id="id3057012"></a><b>Q:. </b></td><td align="left" valign="top"><p> |
---|
[555] | 1383 | Is there any documentation for CBC? |
---|
| 1384 | </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p> |
---|
| 1385 | If you can see this you have the best there is:-) |
---|
| 1386 | Also available is a list of |
---|
| 1387 | <a href="http://www.coin-or.org/Doxygen/Cbc/" target="_top">CBC class descriptions</a> generated |
---|
| 1388 | by <a href="http://www.doxygen.org" target="_top">Doxygen</a>. (JF 04/01/05) |
---|
[557] | 1389 | </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3057051"></a><a id="id3057054"></a><b>Q:. </b></td><td align="left" valign="top"><p> |
---|
[555] | 1390 | Is CBC as fast as Cplex or Xpress? |
---|
| 1391 | </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p> |
---|
| 1392 | No. However its design is much more flexible so advanced users |
---|
| 1393 | will be able to tailor CBC to their needs. (JF 04/01/05) |
---|
[557] | 1394 | </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3057077"></a><a id="id3057080"></a><b>Q:. </b></td><td align="left" valign="top"><p> |
---|
[555] | 1395 | When will version 1.0 of CBC be available? |
---|
| 1396 | </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p> |
---|
| 1397 | It is expected that version 1.0 will be released in time for the 2005 |
---|
| 1398 | <a href="http://www.informs.org" target="_top">INFORMS</a> annual meeting. (JF 04/01/05) |
---|
[557] | 1399 | </p></td></tr><tr class="question"><td align="left" valign="top"><a id="id3057110"></a><a id="id3057113"></a><b>Q:. </b></td><td align="left" valign="top"><p> |
---|
[555] | 1400 | What can the community do to help? |
---|
| 1401 | </p></td></tr><tr class="answer"><td align="left" valign="top"><b>A:. </b></td><td align="left" valign="top"><p> |
---|
| 1402 | People from all around the world are already helping. There are |
---|
| 1403 | probably ten people who do not always post to the discussion mail list but are constantly |
---|
| 1404 | "improving" the code by demanding performance or bug fixes or enhancements. And there |
---|
| 1405 | are others posting questions to discussion groups. (JF 04/01/05) |
---|
| 1406 | </p><p> |
---|
| 1407 | A good start is to join the coin-discuss |
---|
| 1408 | <a href="http://www.coin-or.org/mail.html" target="_top">mailing list</a> where CBC is discussed. Some |
---|
| 1409 | other possibilities include: |
---|
| 1410 | </p><div class="itemizedlist"><ul type="disc"><li><p> |
---|
| 1411 | Comment on the design |
---|
| 1412 | </p></li><li><p> |
---|
| 1413 | Give feedback on the documentation and FAQs. |
---|
| 1414 | </p></li><li><p> |
---|
| 1415 | Break the code, or better yet -- mend it. |
---|
| 1416 | </p></li><li><p> |
---|
| 1417 | Tackle any of the "to-dos" listed in the Doxyen documentation and contribute back to COIN-OR. |
---|
| 1418 | </p></li></ul></div></td></tr></tbody></table></div></div><div class="appendix" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="doxygen"></a>AppendixÂ B.Â Doxygen</h2></div></div><div></div></div><p> |
---|
| 1419 | There is Doxygen content for CBC available online at |
---|
| 1420 | <a href="http://www.coin-or.org/Doxygen/Cbc/index.html" target="_top"> |
---|
| 1421 | http://www.coin-or.org/Doxygen/Cbc/index.html</a>. A local version of the |
---|
| 1422 | Doxygen content can be generated from the CBC distribution. To do so, in the |
---|
| 1423 | directory <tt class="filename">COIN/Cbc</tt>, enter <b class="userinput"><tt>make doc</tt></b>. |
---|
| 1424 | The Doxygen content will be created in the directory |
---|
| 1425 | <tt class="filename">COIN/Cbc/Doc/html</tt>. The same can be done for |
---|
| 1426 | the COIN core, from the <tt class="filename">COIN/Coin</tt> directory. |
---|
[557] | 1427 | </p></div><div class="appendix" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="id3055667"></a>AppendixÂ C.Â Revision History</h2></div></div><div></div></div><div class="revhistory"><table border="0" width="100%" summary="Revision history"><tr><th align="left" valign="top" colspan="3"><b>Revision History</b></th></tr><tr><td align="left">Revision 0.21</td><td align="left">May 10, 2005</td><td align="left">RLH</td></tr><tr><td align="left" colspan="3">Fixed typos caught by Cole Smith, editor of the INFORMS Tutorial Book, and added place holders for needs-to-be-written sections, e.g., Using CGL with CBC.</td></tr><tr><td align="left">Revision 0.2</td><td align="left">May 2, 2005</td><td align="left">RLH</td></tr><tr><td align="left" colspan="3">Book chapter for CBC Tutorial at INFORMS 2005 annual meeting. Reorganized the content. Added CBC Messages. Changed the font type to distinguish functions/variables/classnames/code from text.</td></tr><tr><td align="left">Revision 0.1</td><td align="left">April 1, 2005</td><td align="left">JF</td></tr><tr><td align="left" colspan="3">First draft. The CBC documentation uses the DocBook CLP documentation created by David de la Nuez.</td></tr></table></div></div></div></body></html> |
---|