source: branches/Couenne/Couenne/src/branch/CouenneBranchingObject.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: 4.6 KB
Line 
1/*
2 * Name:    CouenneBranchingObject.cpp
3 * Authors: Pierre Bonami, IBM Corp.
4 *          Pietro Belotti, Carnegie Mellon University
5 * Purpose: Branching object for auxiliary variables
6 *
7 * (C) Pietro Belotti. This file is licensed under the Common Public License (CPL)
8 */
9
10#include <CouenneBranchingObject.hpp>
11
12/// make branching point $\alpha$ away from current point:
13/// bp = alpha * current + (1-alpha) * midpoint
14
15CouNumber CouenneBranchingObject::alpha_ = 0.25;
16
17
18/** \brief Constructor. Get a variable as an argument and set value_
19           through a call to operator () of that exprAux.
20*/
21
22CouenneBranchingObject::CouenneBranchingObject (expression *var): 
23
24  reference_ (var) {
25
26  // set the branching value at the current point
27  //  value_ = expression::Variable (reference_ -> Index ());
28
29  int index = reference_ -> Index ();
30
31  if (index < 0)
32    printf ("Couenne: Warning, CouenneBranchingObject has negative reference's index\n");
33
34  long double
35    x = expression::Variable (index),   // current solution
36    l = expression::Lbound   (index),   //         lower bound
37    u = expression::Ubound   (index),   //         upper
38    alpha = CouenneBranchingObject::Alpha ();
39
40  if      (x<l) x = l;
41  else if (x>u) x = u;
42
43  // This two-way branching rule is only applied when both lower and
44  // upper bound are finite. Otherwise, a CouenneThreeWayBranchObj is
45  // used (see CouenneThreeWayBranchObj.hpp).
46  //
47  // The rule is as follows:
48  //
49  // - if x is well inside the interval (both bounds are infinite or
50  // there is a difference of at least COU_NEAR_BOUND), set
51  // value_ to x;
52  //
53  // - otherwise, try to get far from bounds by setting value_ to a
54  // convex combination of current and midpoint
55  //
56  // TODO: consider branching value that maximizes distance from
57  // current point (how?)
58
59  if (fabs (u-l) < COUENNE_EPS)
60    printf ("Warning, interval is really tiny\n");
61
62  if ((x-l < COUENNE_NEAR_BOUND) ||
63      (u-x < COUENNE_NEAR_BOUND))
64    value_ = alpha * x + (1. - alpha) * (l + u) / 2.;
65  else value_ = x;
66
67  /*
68  if ((x > l + COUENNE_NEAR_BOUND) &&
69      (x < u - COUENNE_NEAR_BOUND))      // x is not at the boundary
70    value_ = x;
71  else // current point is at one of the bounds
72    if ((l > - COUENNE_INFINITY) &&
73        (u <   COUENNE_INFINITY))
74      // finite bounds, apply midpoint rule
75      value_ = alpha * x + (1. - alpha) * (l + u) / 2.;
76
77    else
78      // infinite (one direction) bound interval, x is at the boundary
79      // push it inwards
80      // TODO: look for a proper displacement
81      if (fabs (x-l) < COUENNE_EPS) value_ = l + (1+fabs (l)) / 2.;
82      else                          value_ = u - (1+fabs (u)) / 2.;
83  */
84
85  if (0) {
86    printf ("Branch::constructor: ");
87    reference_ -> print (std::cout);
88    printf (" on %.6e (%.6e) [%.6e,%.6e]\n", 
89            value_, 
90            expression::Variable (reference_ -> Index ()),
91            expression::Lbound   (reference_ -> Index ()),
92            expression::Ubound   (reference_ -> Index ()));
93  }
94}
95
96
97/** \brief Execute the actions required to branch, as specified by the
98           current state of the branching object, and advance the
99           object's state.
100           Returns change in guessed objective on next branch
101*/
102
103double CouenneBranchingObject::branch (OsiSolverInterface * solver) {
104
105  // way = 0 if "<=" node,
106  //       1 if ">=" node
107
108  int way = (!branchIndex_) ? firstBranch_ : !firstBranch_,
109      ind = reference_ -> Index ();
110
111  CouNumber l = solver -> getColLower () [ind],
112            u = solver -> getColUpper () [ind];
113
114  if (way) {
115    if      (value_ < l)             printf ("Nonsense up-branch: [ %f ,(%f)] -> %f\n", l,u,value_);
116    else if (value_ < l+COUENNE_EPS) printf ("## WEAK  up-branch: [ %f ,(%f)] -> %f\n", l,u,value_);
117  } else {
118    if      (value_ > u)             printf ("Nonsense dn-branch: [(%f), %f ] -> %f\n", l,u,value_);
119    else if (value_ > u+COUENNE_EPS) printf ("## WEAK  dn-branch: [(%f), %f ] -> %f\n", l,u,value_);
120  }
121
122  if (0) printf (" [%.6e,%.6e]", l, u);
123
124  // ">=" if way=1, "<=" if way=0 set lower or upper bound (round if this variable is integer)
125  if (way) solver -> setColLower (ind, reference_ -> isInteger () ? ceil  (value_) : value_);
126  else     solver -> setColUpper (ind, reference_ -> isInteger () ? floor (value_) : value_);
127
128  // TODO: apply bound tightening
129
130  if (0) {
131
132    printf (" --> [%.6e,%.6e]\n", l, u);
133    printf ("### Branch: x%d %c= %.12f\n", 
134            reference_ -> Index (), way ? '>' : '<', value_);
135
136    /*for (int i=0; i < solver -> getNumCols(); i++)
137      printf (" %3d [%.3e,%.3e]\n", i, solver -> getColLower () [i],
138      solver -> getColUpper () [i]);*/
139  }
140
141  branchIndex_++;
142  return 0.; // estimated change in objective function
143}
Note: See TracBrowser for help on using the repository browser.