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