source: html/ch05s03.html @ 2246

Last change on this file since 2246 was 561, checked in by ladanyi, 12 years ago

Cbc static pages moved

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.2 KB
Line 
1<?xml version="1.0" encoding="ISO-8859-1" standalone="no"?>
2<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Follow-On Branching</title><meta name="generator" content="DocBook XSL Stylesheets V1.61.2"/><link rel="home" href="index.html" title="CBC User Guide"/><link rel="up" href="ch05.html" title="Chapter 5. &#10;  Branching&#10; "/><link rel="previous" href="ch05s02.html" title="Pseudo Cost Branching"/><link rel="next" href="ch06.html" title="Chapter 6. Cutting planes"/></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Follow-On Branching</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch05s02.html">Prev</a> </td><th width="60%" align="center">Chapter 5. 
3  Branching
4 </th><td width="20%" align="right"> <a accesskey="n" href="ch06.html">Next</a></td></tr></table><hr/></div><div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="followOn"/>Follow-On Branching</h2></div></div><div/></div><p>
5In 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.
6From DFW there may be several flights the crew could take next - suppose one flight is
7the 9:30 flight from DFW to LAX airport.  A binary branch is that the crew arriving
8at DFW either take the 9:30 flight to LAX or they don't.  This "follow-on" branching does not
9fix individual variables. Instead this branching divides all the variables with entries in the JFK-DFW
10constraint into two groups - those with entries in the DFW-LAX constraint and those without
11entries.
12</p><p>
13   The full sample code for follow-on brancing is in <tt class="filename">crew.cpp</tt>
14  located in the CBC Samples directory, see
15  <a href="ch08.html" title="Chapter 8. &#10;More Samples&#10;">Chapter 8, <i>
16More Samples
17</i></a>).  In this case, the simple integer
18variables 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.
19
20</p><div class="example"><a id="id3000566"/><p class="title"><b>Example 5.2. <tt class="classname">CbcFollowOn</tt></b></p><pre class="programlisting">
21   
22  int iColumn;
23  int numberColumns = solver3-&gt;getNumCols();
24  /* We are going to add a single follow-on object but we
25     want to give low priority to existing integers
26     As the default priority is 1000 we don't actually need to give
27     integer priorities but it is here to show how.
28  */
29  // Normal integer priorities
30  int * priority = new int [numberColumns];
31  int numberIntegers=0;
32  for (iColumn=0;iColumn&lt;numberColumns;iColumn++) {
33    if (solver3-&gt;isInteger(iColumn)) {
34      priority[numberIntegers++]= 100; // low priority
35    }
36  }
37  /* Second parameter is set to true for objects,
38     and false for integers. This indicates integers */
39  model.passInPriorities(priority,false);
40  delete [] priority;
41  /* Add in objects before we can give them a priority.
42     In this case just one object
43     - but it shows the general method
44  */
45  CbcObject ** objects = new CbcObject * [1];
46  objects[0]=new CbcFollowOn(&amp;model);
47  model.addObjects(1,objects);
48  delete objects[0];
49  delete [] objects;
50  // High priority
51  int followPriority=1;
52  model.passInPriorities(&amp;followPriority,true);
53     
54  </pre></div></div><div class="navfooter"><hr/><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch05s02.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch05.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch06.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Pseudo Cost Branching </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 6. Cutting planes</td></tr></table></div></body></html>
Note: See TracBrowser for help on using the repository browser.