source: branches/Couenne/Couenne/src/branch/CouenneThreeWayBranchObj.cpp @ 534

Last change on this file since 534 was 534, checked in by pbelotti, 13 years ago

moved include files to make them doxygenable. Introduced three-way branching, with fixed intervals for now. Added check for small bound interval within all generateCuts()

File size: 3.3 KB
Line 
1/*
2 * Name:    CouenneThreeWayBranchObj.cpp
3 * Authors: Pietro Belotti, Carnegie Mellon University
4 * Purpose: Branching object for auxiliary variables
5 *
6 * (C) Pietro Belotti. This file is licensed under the Common Public License (CPL)
7 */
8
9#include <CouenneBranchingObject.hpp>
10#include <CouenneThreeWayBranchObj.hpp>
11
12
13/** \brief Constructor. Get a variable as an argument and set value_
14           through a call to operator () of that exprAux.
15*/
16
17CouenneThreeWayBranchObj::CouenneThreeWayBranchObj (expression *var, 
18                                                    CouNumber x, 
19                                                    CouNumber l, 
20                                                    CouNumber u): 
21  reference_      (var) {
22
23  value_          = x;
24  numberBranches_ = 3;
25
26  // Depending on where x, l, and u are, divide bound interval into
27  // three and set lcrop_ and rcrop_ accordingly.
28
29  // if l and u are unbounded, crop around x using COUENNE_CROP
30
31  if ((x-l > COUENNE_LARGE_INTERVAL) && 
32      (u-x > COUENNE_LARGE_INTERVAL)) {
33    lcrop_ = x - COUENNE_CROP;
34    rcrop_ = x + COUENNE_CROP;
35    first_ = 1;
36  }
37  else
38    if ((x-l > COUENNE_LARGE_INTERVAL) && 
39        (u-x < COUENNE_NEAR_BOUND)) {
40      lcrop_ = x - COUENNE_CROP;
41      rcrop_ = x - COUENNE_LCROP;
42      first_ = 2;
43    }
44    else
45      if ((x-l < COUENNE_NEAR_BOUND) && 
46          (u-x > COUENNE_LARGE_INTERVAL)) {
47        lcrop_ = x + COUENNE_CROP;
48        rcrop_ = x + COUENNE_LCROP;
49        first_ = 0;
50      }
51}
52
53
54/** \brief Execute the actions required to branch, as specified by the
55           current state of the branching object, and advance the
56           object's state.
57           Returns change in guessed objective on next branch
58*/
59
60double CouenneThreeWayBranchObj::branch (OsiSolverInterface * solver) {
61
62  //       -1 if "<= a"  node
63  // way =  0 if "[a,b]" node
64  //        1 if ">= b"  node
65
66  int way, ind = reference_ -> Index ();
67
68  switch (branchIndex_) {
69  case 0: 
70    way = first_;   // if first offspring, let first_ decide who's first
71    break;
72  case 1:
73    way = (first_ == 0) ? 1 : 0;
74    break;
75  case 2:
76    way = (first_ == 2) ? 1 : 2;
77    break;
78  default: 
79    printf ("Warning, branchIndex_ has a strange value (%d)\n", branchIndex_);
80  }
81
82  way --; // from {0,1,2} to {-1,0,1}
83
84  // set lower or upper bound (round if this variable is integer)
85
86  bool intvar = reference_ -> isInteger ();
87
88  switch (way) {
89
90  case -1: // left interval
91    //    printf ("Left branch: x%d <= %.3f\n", ind, lcrop_);
92    solver -> setColUpper (ind, intvar ? floor (lcrop_) : lcrop_);
93    break;
94  case  0: // central interval
95    //    printf ("Central branch: %.3f <= x%d <= %.3f\n", lcrop_, ind, rcrop_);
96    solver -> setColLower (ind, intvar ? ceil  (lcrop_) : lcrop_);
97    solver -> setColUpper (ind, intvar ? floor (rcrop_) : rcrop_);
98    break;
99  case  1: // right interval
100    //    printf ("Right branch: x%d >= %.3f\n", ind, rcrop_);
101    solver -> setColLower (ind, intvar ? ceil  (rcrop_) : rcrop_);
102    break;
103  default:
104    printf ("Couenne: branching on nonsense way %d\n", way);
105  }
106
107  // TODO: apply bound tightening
108
109  /*
110  if (0) {
111
112  printf (" --> [%.6e,%.6e]\n", l, u);
113  printf ("### Branch: x%d %c= %.12f\n",
114  reference_ -> Index (), way ? '>' : '<', value_);
115
116  for (int i=0; i < solver -> getNumCols(); i++)
117  printf (" %3d [%.3e,%.3e]\n", i, solver -> getColLower () [i],
118  solver -> getColUpper () [i]);
119  }*/
120
121  branchIndex_++;
122
123  return 0.; // estimated change in objective function
124}
Note: See TracBrowser for help on using the repository browser.