source: branches/Couenne/Couenne/src/branch/CouenneBranchingObject.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.7 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
13/// make branching point $\alpha$ away from current point:
14/// bp = alpha * current + (1-alpha) * midpoint
15
16CouNumber CouenneBranchingObject::alpha_ = 0.5;
17
18
19/** \brief Constructor. Get a variable as an argument and set value_
20           through a call to operator () of that exprAux.
21*/
22
23CouenneBranchingObject::CouenneBranchingObject (expression *var): 
24
25  reference_ (var) {
26
27  // set the branching value at the current point
28  //  value_ = expression::Variable (reference_ -> Index ());
29
30  int index = reference_ -> Index ();
31
32  long double
33    x = expression::Variable (index),   // current solution
34    l = expression::Lbound   (index),   //         lower bound
35    u = expression::Ubound   (index),   //         upper
36    alpha = CouenneBranchingObject::Alpha ();
37
38  if      (x<l) x = l;
39  else if (x>u) x = u;
40
41  if ((x > l + COUENNE_EPS) && 
42      (x < u - COUENNE_EPS))      // x is not at the boundary
43    value_ = x;
44
45  else // current point is at one of the bounds
46    if ((l > - COUENNE_INFINITY + 1) &&
47        (u <   COUENNE_INFINITY - 1))
48      // finite bounds, apply midpoint rule
49      value_ = alpha * x + (1. - alpha) * (l + u) / 2.;
50
51    else
52      // infinite (one direction) bound interval, x is at the boundary
53      // push it inwards
54      // TODO: look for a proper displacement
55      if (fabs (x-l) < COUENNE_EPS) value_ = l + (1+fabs (l)) / 2.; 
56      else                          value_ = u - (1+fabs (u)) / 2.; 
57
58  if (0) {
59    printf ("Branch::constructor: ");
60    reference_ -> print (std::cout);
61    printf (" on %.6e (%.6e) [%.6e,%.6e]\n", 
62            value_, 
63            expression::Variable (reference_ -> Index ()),
64            expression::Lbound   (reference_ -> Index ()),
65            expression::Ubound   (reference_ -> Index ()));
66  }
67}
68
69/** \brief Execute the actions required to branch, as specified by the
70           current state of the branching object, and advance the
71           object's state.
72           Returns change in guessed objective on next branch
73*/
74
75double CouenneBranchingObject::branch (OsiSolverInterface * solver) {
76
77  // way = 0 if "<=" node,
78  //       1 if ">=" node
79
80  int way = (!branchIndex_) ? firstBranch_ : !firstBranch_,
81      ind = reference_ -> Index ();
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  if (0) printf (" [%.6e,%.6e]", l, u);
94
95  // ">=" if way=1, "<=" if way=0 set lower or upper bound (round if this variable is integer)
96  if (way) solver -> setColLower (ind, reference_ -> isInteger () ? ceil  (value_) : value_);
97  else     solver -> setColUpper (ind, reference_ -> isInteger () ? floor (value_) : value_);
98
99  // TODO: apply bound tightening
100
101  if (0) {
102
103    printf (" --> [%.6e,%.6e]\n", l, u);
104    printf ("### Branch: x%d %c= %.12f\n", 
105            reference_ -> Index (), way ? '>' : '<', value_);
106
107    /*for (int i=0; i < solver -> getNumCols(); i++)
108      printf (" %3d [%.3e,%.3e]\n", i, solver -> getColLower () [i],
109      solver -> getColUpper () [i]);*/
110  }
111
112  branchIndex_++;
113  return 0.; // estimated change in objective function
114}
Note: See TracBrowser for help on using the repository browser.