source: stable/0.3/Couenne/src/branch/CouenneVarObject.cpp @ 569

Last change on this file since 569 was 569, checked in by pbelotti, 9 years ago

restored COUENNE_EPS to 1e-7 -- solves endless branching in nvs19 due to integer infeasibility set to 9e-8 (acceptable for Cbc so should be for Couenne too).

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