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

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

added reduced cost fixing. Separated bound tightening from generateCuts. Started three-way branching, not used yet.

File size: 3.9 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 <CouenneThreeWayBranchObj.hpp>
10
11
12//CouNumber CouenneThreeWayBranchObj::lcrop_ = 0.8;
13//CouNumber CouenneThreeWayBranchObj::rcrop_ = 0.8;
14
15
16/** \brief Constructor. Get a variable as an argument and set value_
17           through a call to operator () of that exprAux.
18*/
19
20CouenneThreeWayBranchObj::CouenneThreeWayBranchObj (expression *var): 
21
22  reference_ (var) {
23
24  // set the branching value at the current point
25  //  value_ = expression::Variable (reference_ -> Index ());
26
27  int index = reference_ -> Index ();
28
29  long double
30    x = expression::Variable (index),   // current solution
31    l = expression::Lbound   (index),   //         lower bound
32    u = expression::Ubound   (index),   //         upper
33    alpha = 0;//CouenneBranchingObject::Alpha ();
34
35  if      (x<l) x = l;
36  else if (x>u) x = u;
37
38  if ((x > l + COUENNE_EPS) && 
39      (x < u - COUENNE_EPS))      // x is not at the boundary
40    value_ = x;
41
42  else // current point is at one of the bounds
43    if ((l > - COUENNE_INFINITY + 1) &&
44        (u <   COUENNE_INFINITY - 1))
45      // finite bounds, apply midpoint rule
46      value_ = alpha * x + (1. - alpha) * (l + u) / 2.;
47
48    else
49      // infinite (one direction) bound interval, x is at the boundary
50      // push it inwards
51      // TODO: look for a proper displacement
52      if (fabs (x-l) < COUENNE_EPS) value_ = l + (1+fabs (l)) / 2.; 
53      else                          value_ = u - (1+fabs (u)) / 2.; 
54
55  if (0) {
56    printf ("Branch::constructor: ");
57    reference_ -> print (std::cout);
58    printf (" on %.6e (%.6e) [%.6e,%.6e]\n", 
59            value_, 
60            expression::Variable (reference_ -> Index ()),
61            expression::Lbound   (reference_ -> Index ()),
62            expression::Ubound   (reference_ -> Index ()));
63  }
64}
65
66
67/** \brief Execute the actions required to branch, as specified by the
68           current state of the branching object, and advance the
69           object's state.
70           Returns change in guessed objective on next branch
71*/
72
73double CouenneThreeWayBranchObj::branch (OsiSolverInterface * solver) {
74
75  //       -1 if "<= a"  node
76  // way =  0 if "[a,b]" node
77  //        1 if ">= b"  node
78
79  int way = branchIndex_ - 1,
80      ind = reference_ -> Index ();
81
82  /*CouNumber l = solver -> getColLower () [ind],
83            u = solver -> getColUpper () [ind];
84
85  if (way) {
86    if      (value_ < l)             printf ("Nonsense up-branch: [ %f ,(%f)] -> [%f\n", l,u,value_);
87    else if (value_ < l+COUENNE_EPS) printf ("## WEAK  up-branch: [ %f ,(%f)] -> [%f\n", l,u,value_);
88  } else {
89    if      (value_ > u)             printf ("Nonsense dn-branch: [(%f), %f ] -> %f]\n", l,u,value_);
90    else if (value_ > u+COUENNE_EPS) printf ("## WEAK  dn-branch: [(%f), %f ] -> %f]\n", l,u,value_);
91  }
92  */
93
94  // set lower or upper bound (round if this variable is integer)
95
96  bool intvar = reference_ -> isInteger ();
97
98  switch (way) {
99
100  case -1: // left interval
101    solver -> setColUpper (ind, intvar ? floor (lcrop_) : lcrop_);
102    break;
103  case  0: // central interval
104    solver -> setColLower (ind, intvar ? ceil  (lcrop_) : lcrop_);
105    solver -> setColUpper (ind, intvar ? floor (rcrop_) : rcrop_);
106    break;
107  case  1: // right interval
108    solver -> setColLower (ind, intvar ? ceil  (rcrop_) : rcrop_);
109    break;
110  default:
111    printf ("Couenne: branching on nonsense way %d\n", way);
112  }
113
114  // TODO: apply bound tightening
115
116  /*
117  if (0) {
118
119  printf (" --> [%.6e,%.6e]\n", l, u);
120  printf ("### Branch: x%d %c= %.12f\n",
121  reference_ -> Index (), way ? '>' : '<', value_);
122
123  for (int i=0; i < solver -> getNumCols(); i++)
124  printf (" %3d [%.3e,%.3e]\n", i, solver -> getColLower () [i],
125  solver -> getColUpper () [i]);
126  }*/
127
128  branchIndex_++;
129
130  return 0.; // estimated change in objective function
131}
Note: See TracBrowser for help on using the repository browser.