source: branches/Couenne/Couenne/src/branch/CouenneObject.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: 6.2 KB
Line 
1/*
2 * Name:    CouenneObject.cpp
3 * Authors: Pierre Bonami, IBM Corp.
4 *          Pietro Belotti, Carnegie Mellon University
5 * Purpose: Base object for variables (to be used in branching)
6 *
7 * (C) Pietro Belotti. This file is licensed under the Common Public License (CPL)
8 */
9
10#include <CouenneObject.hpp>
11#include <exprGroup.h>
12#include <CouenneBranchingObject.hpp>
13
14#define WEI_INF   1.
15#define WEI_RANK  0.
16#define WEI_MULT  0.
17
18
19/// return difference between current value
20double CouenneObject::infeasibility (const OsiBranchingInformation *info, int &) const {
21
22  // infeasibility is always null for linear expressions
23  if (reference_ -> Image () -> Linearity () <= LINEAR)
24    return 0.;
25
26  expression::update (const_cast <CouNumber *> (info -> solution_),
27                      const_cast <CouNumber *> (info -> lower_),
28                      const_cast <CouNumber *> (info -> upper_));
29
30  expression *fixvar = reference_ -> Image () -> getFixVar ();
31  int index = fixvar -> Index ();
32
33  if (index < 0)
34    return 0.;
35
36  // if branched-upon variable has a narrow interval, it is not worth
37  // to branch on it
38
39  const double & expr = (*(reference_ -> Image ())) (), 
40               & var  = (*reference_) ();
41    //expression::Variable (reference_ -> Index ());
42
43  if (0) {
44
45    printf ("Inf: = |%.6e - %.6e| = %.6e  ",  ////[%.2f,%.2f]
46            var, expr, 
47            //      expression::Lbound (reference_ -> Index ()),
48            //      expression::Ubound (reference_ -> Index ()),
49            fabs (var - expr));
50    reference_             -> print (std::cout); std::cout << " = ";
51    reference_ -> Image () -> print (std::cout); printf ("\n");
52  }
53
54  CouNumber delta = fabs (var - expr);
55
56  CouNumber l  = info -> lower_ [index],
57            u  = info -> upper_ [index];
58
59  if (0)
60    if ((delta > COUENNE_EPS) &&
61        ((fabs (u-l) < COUENNE_EPS) ||
62        ((mymin (fabs (l), fabs (u)) > COUENNE_EPS) && 
63         (fabs (u-l) / mymax (fabs (l), fabs (u)) < COUENNE_EPS)))) {
64      //      ((mymin (fabs (lr), fabs (ur)) > COUENNE_EPS) &&
65      //       (fabs (ur-lr) / mymax (fabs (lr), fabs (ur)) < COUENNE_EPS)))
66
67      printf (". Inf: = |%.4f - %.4f| = %.4e. w [%.3f,%.3f], x [%.3f,%.3f] = %.4e ",  ////[%.2f,%.2f]
68              var, expr, fabs (var - expr), 
69              info -> lower_ [reference_ -> Index ()],
70              info -> upper_ [reference_ -> Index ()],
71              l, u, u-l);
72      reference_             -> print (std::cout); std::cout << " = ";
73      reference_ -> Image () -> print (std::cout);
74      printf ("\n");
75    }
76
77  //printf (" delta=%.9f,l=%.9f,u=%.9f ", delta, l, u);
78
79  /// avoid branching on (relatively) small deltas
80  if (delta < COUENNE_EPS)
81    /*||
82      (fabs (u-l) < COUENNE_EPS) ||
83      ((mymin (fabs (l), fabs (u)) > COUENNE_EPS) &&
84      (fabs (u-l) / mymax (fabs (l), fabs (u)) < COUENNE_EPS)))*/
85    //      ((mymin (fabs (lr), fabs (ur)) > COUENNE_EPS) &&
86    //       (fabs (ur-lr) / mymax (fabs (lr), fabs (ur)) < COUENNE_EPS)))
87    delta = 0.;
88
89  else // make delta a function of the variable's rank and multiplicity
90    delta =   WEI_INF  * (1. - exp (-delta))
91            + WEI_RANK / (1. + fixvar -> rank ())
92            + WEI_MULT * (1. - 1. / fixvar -> Multiplicity ());
93
94  return delta;
95}
96
97
98/// fix integer coordinates of current integer feasible solution
99double CouenneObject::feasibleRegion (OsiSolverInterface *solver, 
100                                      const OsiBranchingInformation *info) const {
101  int index = reference_ -> Index ();
102
103  // should never happen...
104  if (index < 0) {
105    printf ("Warning, CouenneObject::feasibleRegion: reference_'s index negative\n");
106    return 0;
107  }
108
109  double val = info -> solution_ [index];
110
111  // fix that variable to its current value
112
113  solver -> setColLower (index, val);
114  solver -> setColUpper (index, val);
115
116  expression * expr = reference_ -> Image ();
117
118  // fix all variables upon which this auxiliary depends
119
120  if (expr -> Argument ()){ // unary function
121
122    index = expr -> Argument () -> Index ();
123
124    if (index > -1) {
125
126      val = info -> solution_ [index];
127
128      solver -> setColLower (index, val);
129      solver -> setColUpper (index, val);
130    }
131  }
132  else // n-ary function
133    if (expr -> ArgList ()) {
134
135      expression ** args = expr -> ArgList ();
136      int nargs = expr -> nArgs ();
137
138      for (register int i = 0 ; i < nargs ; i++) {
139
140        index = args [i] -> Index();
141
142        if (index > -1) {
143
144          val = info -> solution_ [index];
145          solver -> setColLower (index, val);
146          solver -> setColUpper (index, val);
147        }
148      }
149    }
150
151  // last case: exprGroup, the linear terms are not handled
152
153  if (expr -> code () == COU_EXPRGROUP) {
154
155    exprGroup *e = dynamic_cast <exprGroup *> (expr);
156    int *indices = e -> getIndices (), index;
157
158    for (; *indices >= 0; indices++) {
159     
160      val = info -> solution_ [*indices];
161
162      solver -> setColLower (*indices, val);
163      solver -> setColUpper (*indices, val);
164    }
165  }
166
167  return 0.;
168}
169
170
171/// apply the branching rule
172OsiBranchingObject* CouenneObject::createBranch (OsiSolverInterface *si, 
173                                                 const OsiBranchingInformation *info, 
174                                                 int) const {
175  if (0) {
176    printf ("CO::createBranch: ");
177    reference_ -> print (std::cout);
178    printf (" = ");
179    reference_ -> Image () -> print (std::cout);
180    printf (" --> branch on ");
181    reference_ -> Image () -> getFixVar () -> print (std::cout);
182    printf ("\n");
183  }
184
185  // constructor uses actual values of variables and bounds, update them
186  expression::update (const_cast <CouNumber *> (info -> solution_),
187                      const_cast <CouNumber *> (info -> lower_),
188                      const_cast <CouNumber *> (info -> upper_));
189
190  expression *depvar = reference_ -> Image () -> getFixVar ();
191  int index;
192
193  if (depvar && (index = depvar -> Index ())>= 0) {
194
195    int ref_ind = reference_ -> Index ();
196
197    CouNumber x  = info -> solution_ [index],
198              l  = info -> lower_    [index],
199              u  = info -> upper_    [index],
200              xr = info -> solution_ [ref_ind],
201              lr = info -> lower_    [ref_ind],
202              ur = info -> upper_    [ref_ind];
203
204    if ((fabs (x-l) > COUENNE_EPS) &&
205        (fabs (u-x) > COUENNE_EPS) &&
206        (fabs (u-l) > COUENNE_EPS)
207        || (fabs (xr-lr) < COUENNE_EPS)
208        || (fabs (ur-xr) < COUENNE_EPS)
209        || (fabs (ur-lr) < COUENNE_EPS))
210      return new CouenneBranchingObject (depvar);
211  }
212
213  return new CouenneBranchingObject (reference_);
214}
Note: See TracBrowser for help on using the repository browser.