source: trunk/Couenne/src/branch/CouenneVarObject.cpp @ 71

Last change on this file since 71 was 71, checked in by pbelotti, 11 years ago

added common exprs to output. Fixed printing segfault.

File size: 8.3 KB
Line 
1/*
2 * Name:    CouenneVarObject.cpp
3 * Authors: Pietro Belotti, Carnegie Mellon University
4 * Purpose: Base object for variables (to be used in branching)
5 *
6 * (C) Carnegie-Mellon University, 2008.
7 * This file is licensed under the Common Public License (CPL)
8 */
9
10#include "CoinHelperFunctions.hpp"
11
12#include "CouenneProblem.hpp"
13#include "CouenneVarObject.hpp"
14#include "CouenneBranchingObject.hpp"
15#include "CouenneComplObject.hpp"
16
17/// Constructor with information for branching point selection strategy
18CouenneVarObject::CouenneVarObject (CouenneProblem *p,
19                                    exprVar *ref, 
20                                    Bonmin::BabSetupBase *base, 
21                                    JnlstPtr jnlst):
22
23  // Do not set variable (expression).
24  // This way, no expression-dependent strategy is chosen
25  CouenneObject (p, ref, base, jnlst) {
26
27  if (jnlst_ -> ProduceOutput (J_SUMMARY, J_BRANCHING)) {
28    printf ("created Variable Object: "); 
29    reference_ -> print (); 
30    printf (" with %s strategy [clamp=%g, alpha=%g]\n", 
31            (strategy_ == LP_CLAMPED)   ? "lp-clamped" : 
32            (strategy_ == LP_CENTRAL)   ? "lp-central" : 
33            (strategy_ == BALANCED)     ? "balanced"   : 
34            (strategy_ == MIN_AREA)     ? "min-area"   : 
35            (strategy_ == MID_INTERVAL) ? "mid-point"  : 
36            (strategy_ == NO_BRANCH)    ? "no-branching (null infeasibility)" : 
37                                          "no strategy",
38            lp_clamp_, alpha_);
39  }
40}
41
42
43/// apply the branching rule
44OsiBranchingObject *CouenneVarObject::createBranch (OsiSolverInterface *si, 
45                                                    const OsiBranchingInformation *info, 
46                                                    int way) const {
47
48  // The infeasibility on an (independent) variable x_i is given by
49  // something more elaborate than |w-f(x)|, that is, a function of
50  // all infeasibilities of all expressions which depend on x_i.
51
52  problem_ -> domain () -> push
53    (problem_ -> nVars (),
54     info -> solution_,
55     info -> lower_,
56     info -> upper_); // have to alloc+copy
57
58  int bestWay;
59  const CouenneObject *criticalObject = NULL; // should create the branchingObject
60
61  CouNumber bestPt = computeBranchingPoint (info, bestWay, criticalObject);
62
63  ///////////////////////////////////////////
64
65  jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, ":::: creating branching on x_%d @%g [%g,%g]\n", 
66          reference_ -> Index (), 
67          info -> solution_ [reference_ -> Index ()],
68          info -> lower_    [reference_ -> Index ()],
69          info -> upper_    [reference_ -> Index ()]);
70
71  OsiBranchingObject *brObj = criticalObject ? 
72    criticalObject -> createBranch (si, info, way) :
73    new CouenneBranchingObject (si, this, jnlst_, reference_, way, bestPt, doFBBT_, doConvCuts_);
74
75  problem_ -> domain () -> pop ();
76
77  return brObj;
78}
79
80
81/// compute branching point (used in createBranch ())
82CouNumber CouenneVarObject::computeBranchingPoint(const OsiBranchingInformation *info,
83                                                  int& bestWay,
84                                                  const CouenneObject *&criticalObject) const {
85  criticalObject = NULL;
86
87  if (jnlst_ -> ProduceOutput (J_DETAILED, J_BRANCHING)) {
88    printf ( "---------- computeBRPT for "); 
89    reference_ -> print (); 
90    printf (" [%g,%g]\n", 
91            info -> lower_ [reference_ -> Index ()],
92            info -> upper_ [reference_ -> Index ()]);
93  }
94
95  expression *brVar = NULL; // branching variable
96
97  CouNumber
98    brdistDn = 0.,
99    brdistUp = 0.,
100    bestPt   = 0.,
101   *brPts    = NULL, // branching point(s)
102   *brDist   = NULL, // distances from LP point to each new convexification
103    maxdist = - COIN_DBL_MAX;
104
105  bool chosen = false;
106
107  bestWay = TWO_LEFT;
108  int whichWay = TWO_LEFT,
109    index = reference_ -> Index ();
110
111  std::set <int> deplist = problem_ -> Dependence () [index];
112
113  for (std::set <int>::iterator i = deplist.begin (); i != deplist.end (); ++i) {
114
115    CouenneObject *obj = problem_ -> Objects () [*i];
116
117    CouNumber improv = 0.;
118
119    assert (obj -> Reference ());
120
121    if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) {
122      printf ("  ** "); 
123      obj -> Reference ()             -> print (); 
124      if (reference_ -> Image ()) {printf (" := "); obj -> Reference () -> Image () -> print ();}
125      printf ("\n");
126    }
127
128    if (obj -> Reference ()) {
129      if (obj -> Reference () -> Image ())
130        improv = obj -> Reference () -> Image ()
131          -> selectBranch (obj, info,                      // input parameters
132                           brVar, brPts, brDist, whichWay); // result: who, where, distances, direction
133      else {
134        brVar = obj -> Reference ();
135        brPts  = (double *) realloc (brPts, sizeof (double)); 
136        brDist = (double *) realloc (brDist, 2 * sizeof (double)); 
137
138        double point = info -> solution_ [obj -> Reference () -> Index ()];
139
140        *brPts = point;
141        improv = 0.;
142
143        if (point > floor (point)) {improv =                  brDist [0] = point - floor (point);}
144        if (point < ceil  (point)) {improv = CoinMin (improv, brDist [1] = ceil (point) - point);}
145
146        point -= floor (point);
147        whichWay = (point < 0.45) ? TWO_LEFT : (point > 0.55) ? TWO_RIGHT : TWO_RAND;
148      }
149    }
150
151    if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) {
152      printf ("  --> "); 
153      if (brVar) {
154        brVar -> print (); 
155        if (brPts) 
156          printf (" at %g, improv %g <%g>, indices = %d,%d\n", 
157                  *brPts, improv, maxdist, index, brVar -> Index ());
158      }
159    }
160
161    if (brVar &&
162        (brVar -> Index () == index) &&    // it's us!
163        (fabs (improv) > maxdist) &&       // this branching seems to induce a higher improvement
164        (fabs (*brPts) < COU_MAX_COEFF)) { // and branching pt is limited
165
166      criticalObject = problem_ -> Objects () [*i]; // set this object as the branch creator
167
168      brdistDn = brDist [0];
169      brdistUp = brDist [1];
170      chosen = true;
171      bestPt = *brPts;
172      maxdist = improv;
173      bestWay = whichWay;
174    }
175  }
176
177  // no hits on this VarObject's variable, that is, this variable was
178  // never chosen
179
180  if (!chosen) {
181
182    bestPt = info -> solution_ [index];
183    brVar  = reference_;
184
185    CouNumber
186      l     = info -> lower_ [index], 
187      u     = info -> upper_ [index],
188      width = lp_clamp_ * (u-l);
189
190    switch (strategy_) {
191
192    case CouenneObject::LP_CLAMPED:
193      bestPt = CoinMax (l + width, CoinMin (bestPt, u - width));
194      break;
195    case CouenneObject::LP_CENTRAL: 
196      if ((bestPt < l + width) || (bestPt > u - width))
197        bestPt = (l+u)/2;
198      break;
199    case CouenneObject::MID_INTERVAL: 
200    default: 
201      // all other cases (balanced, min-area)
202      bestPt = midInterval (bestPt, l, u);
203
204      if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) {
205        if (CoinMin (fabs (bestPt - l), fabs (bestPt - u)) < 1e-3) {
206          printf ("computed failsafe %g [%g,%g] for ", bestPt, l,u);
207          reference_ -> print (); printf ("\n");
208        }
209      }
210      break;
211    }
212
213    brPts  = (double *) realloc (brPts, sizeof (double));
214    *brPts = bestPt;
215
216      if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) {
217        printf ("  ::: failsafe:  %g [%g,%g] for ", 
218                bestPt, info -> lower_ [index], info -> upper_ [index]); 
219        reference_ -> print ();
220        printf ("\n");
221      }
222
223  } else {
224
225      if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) {
226        if (CoinMin (fabs (bestPt - info -> lower_ [index]), 
227                     fabs (bestPt - info -> upper_ [index])) < 1e-3) {
228          printf ("  computed %g [%g,%g] for ", 
229                  bestPt, info -> lower_ [index], info -> upper_ [index]); 
230          reference_ -> print ();
231          printf ("\n");
232        }
233      }
234  }
235
236  if (pseudoMultType_ == PROJECTDIST) {
237
238    if (chosen) {
239      downEstimate_ = brdistDn;
240      upEstimate_   = brdistUp;
241    } 
242    else downEstimate_ = upEstimate_ = 1.;
243  }
244
245  if (brPts)  free (brPts);
246  if (brDist) free (brDist);
247
248  return bestPt;
249}
250
251
252#define TOL 0.
253
254/// fix nonlinear coordinates of current integer-nonlinear feasible solution
255double CouenneVarObject::feasibleRegion (OsiSolverInterface *solver, 
256                                         const OsiBranchingInformation *info) const {
257  int index = reference_ -> Index ();
258
259  assert (index >= 0);
260
261  double val = info -> solution_ [index];
262
263  // fix that variable to its current value
264  solver -> setColLower (index, val-TOL);
265  solver -> setColUpper (index, val+TOL);
266
267  return 0.;
268}
269
270
271/// are we on the bad or good side of the expression?
272bool CouenneVarObject::isCuttable () const {
273
274  const std::set <int>                &deplist = problem_ -> Dependence () [reference_ -> Index ()];
275  const std::vector <CouenneObject *> &objects = problem_ -> Objects ();
276
277  for (std::set <int>::const_iterator depvar = deplist. begin ();
278       depvar != deplist. end (); ++depvar)
279    if (!(objects [*depvar] -> isCuttable ()))
280      return false;
281
282  return (!(reference_ -> isInteger ()));
283}
284
Note: See TracBrowser for help on using the repository browser.