# Changeset 557

Ignore:
Timestamp:
May 31, 2007 12:31:39 PM (12 years ago)
Message:

use a more elaborate structure to check changed bounds. Check bounds of other variables after applying OBBT for one. Remove exit from exprSub::impliedBound. Return changed bounds in exprPow. Added explicit handling of whichWay in CouenneObject?. Added branching rule for expr{Inv,Log} and exprMul (infinite bounds).

Location:
branches/Couenne/Couenne
Files:
45 edited

Unmodified
Removed
• ## branches/Couenne/Couenne/TODO

 r552 - add cuts at subsequent calls at changed bounds also - avoid very large coefficients - Bilinear cuts
• ## branches/Couenne/Couenne/src/branch/CouenneBranchingObject.cpp

 r556 alpha = CouenneBranchingObject::Alpha (); //  printf ("///////////brpt = %g, x = %Lf, l,u = [%Lf,%Lf]\n", brpoint, x, l, u); if (fabs (brpoint) < COUENNE_INFINITY) x = brpoint; else                             value_ = 0; else value_ = x; /*  if ((x > l + COUENNE_NEAR_BOUND) && (x < u - COUENNE_NEAR_BOUND))      // x is not at the boundary value_ = x; else // current point is at one of the bounds if ((l > - COUENNE_INFINITY) && (u <   COUENNE_INFINITY)) // finite bounds, apply midpoint rule value_ = alpha * x + (1. - alpha) * (l + u) / 2.; else // infinite (one direction) bound interval, x is at the boundary // push it inwards // TODO: look for a proper displacement if (fabs (x-l) < COUENNE_EPS) value_ = l + (1+fabs (l)) / 2.; else                          value_ = u - (1+fabs (u)) / 2.;   */ if (0) { } //if (0) printf (" [%.6e,%.6e]", l, u); //  if (way) solver -> setColLower (index_, reference_ -> isInteger () ? ceil  (value_) : value_); //  else     solver -> setColUpper (index_, reference_ -> isInteger () ? floor (value_) : value_); if (!way) solver -> setColUpper (index_, integer_ ? floor (value_) : value_); // down branch else      solver -> setColLower (index_, integer_ ? ceil  (value_) : value_); // up   branch
• ## branches/Couenne/Couenne/src/branch/CouenneChooseVariable.cpp

 r556 CouenneChooseVariable::CouenneChooseVariable (const CouenneChooseVariable &source): OsiChooseVariable (source), problem_ (source.Problem ()) {} problem_ (source.problem_) {} /// Assignment operator CouenneChooseVariable & CouenneChooseVariable::operator= (const CouenneChooseVariable& rhs) {problem_ = rhs.Problem(); return *this;} {problem_ = rhs.problem_; return *this;} /// Clone
• ## branches/Couenne/Couenne/src/branch/CouenneObject.cpp

 r556 // whichWay should be set to which branch first (for two-way branching?) // if selectBranch not called, choose one at random whichWay_ = whichWay = TWO_RAND; // infeasibility is always null for linear expressions brVarInd_, brPts_, whichWay); // result: who, where, and how to branch whichWay_ = whichWay; if (brVarInd_ >= 0) delta = improv; if (0) { printf ("Inf |%+.4e - %+.4e| = %+.4e  %+.4e ",  ////[%.2f,%.2f] printf ("Inf |%+.4e - %+.4e| = %+.4e  %+.4e way %d, ind %d",  ////[%.2f,%.2f] var, expr, //      expression::Lbound (reference_ -> Index ()), //      expression::Ubound (reference_ -> Index ()), fabs (var - expr), delta); fabs (var - expr), delta, whichWay, brVarInd_); reference_             -> print (std::cout); std::cout << " = "; // way has suggestion from CouenneObject::infeasibility() // Well, not exactly... it seems bool isint = reference_ -> isInteger (); way = whichWay_; if (brVarInd_ >= 0) // if applied latest selectBranching case THREE_RIGHT: case THREE_RAND: //printf ("3 WAY Branch x%d at %g--%g [%d] (%d)\n", brVarInd_, *brPts_, brPts_ [1], way, isint); //printf ("3Way Branch x%d @ %g ][ %g [%d] (%d)\n", brVarInd_, *brPts_, brPts_ [1], way, isint); return new CouenneThreeWayBranchObj (brVarInd_, brPts_ [0], brPts_ [1], way, isint); default: printf ("CouenneObject::createBranch(): way has no sense\n"); printf ("CouenneObject::createBranch(): way=%d has no sense\n", way); exit (-1); }
• ## branches/Couenne/Couenne/src/branch/CouenneObject.hpp

 r537 enum {TWO_LEFT,                 TWO_RIGHT,   TWO_RAND, THREE_LEFT, THREE_CENTER, THREE_RIGHT, THREE_RAND}; THREE_LEFT, THREE_CENTER, THREE_RIGHT, THREE_RAND, BRANCH_NONE}; reference_ (ref), brVarInd_  (-1), brPts_     (NULL) {} brPts_     (NULL), whichWay_  (BRANCH_NONE) {} /// Destructor /// ThreeWayBranching. Ends with a -COIN_DBL_MAX (not considered...) mutable CouNumber *brPts_; /// how to branch. This should be done automatically from /// ::infeasibility() and ::createBranch(), but for some reason /// obj->whichWay() in the last 20 lines of CbcNode.cpp returns 0, /// therefore we set our own whichWay_ within this object and use it /// between the two methods. mutable int whichWay_; };
• ## branches/Couenne/Couenne/src/branch/CouenneThreeWayBranchObj.cpp

 r556 //        1 if ">= b"  node int way;//, ind = reference_ -> Index (); int way; switch (branchIndex_) { } } /*printf (" --> [%.6e,%.6e]\n", l, u); printf ("### Branch: x%d %c= %.12f\n", reference_ -> Index (), way ? '>' : '<', value_); for (int i=0; i < solver -> getNumCols(); i++) printf (" %3d [%.3e,%.3e]\n", i, solver -> getColLower () [i], solver -> getColUpper () [i]);*/ branchIndex_++;
• ## branches/Couenne/Couenne/src/branch/operators/branchExprAbs.cpp

 r556 way = TWO_RAND; // don't really care which subtree to visit first // exact distance from current point to the two subsequent // exact distance between current point and the two subsequent // convexifications return mymin (project (1., -1., 0., x0, y0, 0., COUENNE_INFINITY,  0, NULL, NULL),
• ## branches/Couenne/Couenne/src/branch/operators/branchExprDiv.cpp

 r556 #include #define BR_NEXT_ZERO 1e-3 #define BR_MULT      1e-3 /// set up branching object by evaluating many branching points for
• ## branches/Couenne/Couenne/src/branch/operators/branchExprExp.cpp

 r537 double * &brpts, int &way) { ind = -1; return 0.; // two cases: inside or outside the belly. // branch. // // Outside: it suffices to project the current point on the line to // get the maxi-min displacement. // Outside: it suffices to project the current point on the line // (i.e. to get the closest point on the line) to get the maxi-min // displacement. // // As happens for all monotonous functions, after chosing *brpts it // is equivalent to choose w's or x's index as ind, as the implied // bounds will do the rest. // As for all monotonous functions, after choosing *brpts it is // equivalent to choose w's or x's index as ind, as the implied- and // propagated bounds will do the rest. ind = argument_ -> Index (); int wi = w -> Index (); ind    = argument_ -> Index (); int wi = w         -> Index (); if ((ind < 0) || (wi < 0)) {printf ("Couenne, w=f(x): negative index\n"); exit (-1);} if ((ind < 0) || (wi < 0)) {printf ("Couenne, w=exp(x): negative index\n"); exit (-1);} brpts = (double *) realloc (brpts, sizeof (double)); CouNumber y0 = info -> solution_ [wi], x0 = info -> solution_ [ind], l  = info -> lower_    [ind], u  = info -> upper_    [ind]; CouNumber x0 = info -> solution_ [ind], y0 = info -> solution_ [wi]; if (y0 < exp (x0)) { if (y0 < exp (x0)) { // A) Outside // Outside brpts = (double *) realloc (brpts, sizeof (double)); *brpts = powNewton (x0, y0, exp, exp, exp); if      (*brpts < l) *brpts = (u <   COUENNE_INFINITY) ? ((l+u)/2) : l + 1; else if (*brpts > u) *brpts = (l > - COUENNE_INFINITY) ? ((l+u)/2) : u - 1; way = TWO_RAND; CouNumber dy = y0 - exp (*brpts); return sqrt (x0*x0 + dy*dy); } else { // B) Inside } else { CouNumber l = info -> lower_ [ind], u = info -> upper_ [ind]; // two cases: // Inside. Two cases: if ((l < -COUENNE_INFINITY) && (u >  COUENNE_INFINITY)) { // B1) bounds are infinite // 1) both bounds are infinite --> three way branching brpts = (double *) realloc (brpts, 2*sizeof (double)); way = THREE_CENTER; *brpts = x0; brpts [1] = log (y0); brpts = (double *) realloc (brpts, 2 * sizeof (double)); way = THREE_CENTER; // focus on central convexification first brpts [0] = x0;       // draw vertical   from (x0,y0) south to curve y=exp(x) brpts [1] = log (y0); //      horizontal              east CouNumber a = y0 - exp (x0), // sides of a triangle with (x0,y0) } else { // 2) at least one of them is finite --> two way branching brpts = (double *) realloc (brpts, sizeof (double)); // B2) at least one of them is finite if (l < -COUENNE_INFINITY) { *brpts = x0; if (*brpts > u - COUENNE_NEAR_BOUND) *brpts = u-1; way = TWO_RIGHT; return y0 - exp (x0); *brpts = log (y0); if (*brpts < l + COUENNE_NEAR_BOUND) *brpts = l+1; way = TWO_LEFT; return x0 - log (y0); *brpts = powNewton (x0, y0, exp, exp, exp); if ((*brpts > u - COUENNE_NEAR_BOUND) || (*brpts < l + COUENNE_NEAR_BOUND)) *brpts = (l+u) / 2; way = TWO_RAND;
• ## branches/Couenne/Couenne/src/branch/operators/branchExprInv.cpp

 r537 * Name:    branchExprInv.cpp * Author:  Pietro Belotti * Purpose: return branch gain and branch object for 1/x * Purpose: return branch selection for 1/x * * (C) Pietro Belotti. This file is licensed under the Common Public License (CPL) #include #include #include #include #include /// set up branching object by evaluating many branching points for /// each expression's arguments CouNumber exprInv::selectBranch (expression *w, const OsiBranchingInformation *info, double * &brpts, int &way) { ind = -1; return 0.; /*ind = argument_ -> Index (); // two cases: inside or outside the bellies. // // Inside: the distance depends on the projection of the current // point onto the would-be upper envelopes, which forces us to look // at it numerically. If both bounds are infinite, create a ThreeWay // branch. // // Outside: it suffices to project the current point on the line // (i.e. to get the closest point on the line) to get the maxi-min // displacement. // // As for all monotonous functions, after choosing *brpts it is // equivalent to choose w's or x's index as ind, as the implied- and // propagated bounds will do the rest. if (ind < 0) { printf ("argument of exprAbs has negative index\n"); exit (-1); ind    = argument_ -> Index (); int wi = w         -> Index (); if ((ind < 0) || (wi < 0)) {printf ("Couenne, w=exp(x): negative index\n"); exit (-1);} CouNumber y0 = info -> solution_ [wi], x0 = info -> solution_ [ind], l  = info -> lower_    [ind], u  = info -> upper_    [ind]; // two cases: // // 1) bounds include 0: three way branch to exclude 0 (refer to branchExprDiv.cpp) // 2) otherwise         two   way branch if ((l < 0) && (u > 0)) { brpts = (double *) realloc (brpts, 2 * sizeof (CouNumber)); way = THREE_RIGHT; brpts [0] = (l >= - BR_NEXT_ZERO - COUENNE_EPS) ? (l * BR_MULT) : - BR_NEXT_ZERO; brpts [1] = (u <=   BR_NEXT_ZERO + COUENNE_EPS) ? (u * BR_MULT) :   BR_NEXT_ZERO; return ((fabs (x0) < COUENNE_EPS) ? 1. : (1 / x0 - info -> solution_ [wi])); } brpts = (double *) malloc (sizeof (double)); *brpts = 0.; way = TWO_LEFT; // case 2: look if inside or outside of belly (refer to branchExprExp.cpp) return mymin (project (1., -1., 0., x0, y0, 0., COUENNE_INFINITY,  0, NULL, NULL), project (1., +1., 0., x0, y0, -COUENNE_INFINITY, 0., 0, NULL, NULL));*/ } /* /// distance covered by current point if branching rule applied to this expression double exprInv::BranchGain (expression *w, const OsiBranchingInformation *info) { if (x0*y0 < 1) { // outside bellies int xi = argument_ -> Index (), wi = w         -> Index (); brpts = (double *) realloc (brpts, sizeof (double)); if (xi < 0 || wi < 0) { printf ("negative indices inbranchExprAbs\n"); exit (-1); *brpts = powNewton (x0, y0, inv, oppInvSqr, inv_dblprime); if      (*brpts < l) *brpts = (u <   COUENNE_INFINITY) ? ((l+u)/2) : l + 1; else if (*brpts > u) *brpts = (l > - COUENNE_INFINITY) ? ((l+u)/2) : u - 1; way = (u < 0) ? TWO_RIGHT : TWO_LEFT; // explore finite interval first CouNumber dy = y0 - 1. / *brpts; x0 -= *brpts; return sqrt (x0*x0 + dy*dy); } CouNumber x0 = expression::Variable (xi), y0 = expression::Variable (wi); // Inside. Two cases: if ((l <   COUENNE_EPS) && (u >   COUENNE_INFINITY) || (u > - COUENNE_EPS) && (l < - COUENNE_INFINITY)) { return 0; // 1) bounds are infinite both horizontally and vertically //    (i.e. [-inf,0] or [0,inf]) --> three way branching //  return mymin (project (1, -1, 0, x0, y0, 0, COUENNE_INFINITY,  0, NULL, NULL), //            project (1, +1, 0, x0, y0, -COUENNE_INFINITY, 0, 0, NULL, NULL)); brpts = (double *) realloc (brpts, 2 * sizeof (double)); way = THREE_CENTER; // focus on central convexification first brpts [0] = x0;        // draw vertical   from (x0,y0) south (north) to curve y=1/x brpts [1] = 1. / (y0); //      horizontal              west  (east) CouNumber a = y0 - 1 / x0, // sides of a triangle with (x0,y0) b = x0 - 1 / y0, // as one of the vertices c = a * cos (atan (a/b)); return mymin (a, mymin (b, c)); } // 2) at least one of them is finite --> two way branching brpts = (double *) realloc (brpts, sizeof (double)); if (l < - COUENNE_INFINITY) { // and u away from -0 *brpts = x0; if (*brpts > u - COUENNE_NEAR_BOUND) *brpts = u-1; way = TWO_RIGHT; return y0 - 1. / x0; } if (u > COUENNE_INFINITY) { // and l away from +0 *brpts = x0; if (*brpts < l + COUENNE_NEAR_BOUND) *brpts = l+1; way = TWO_LEFT; return y0 - 1. / x0; } // last case: nice finite interval and limited curve *brpts = powNewton (x0, y0, inv, oppInvSqr, inv_dblprime); if ((*brpts > u - COUENNE_NEAR_BOUND) || (*brpts < l + COUENNE_NEAR_BOUND)) *brpts = (l+u) / 2; way = TWO_RAND; CouNumber dx = x0 - *brpts, dy = y0 - 1. / *brpts; return sqrt (dx*dx + dy*dy); } /// branching object best suited for this expression OsiBranchingObject *exprInv::BranchObject (expression *w, const OsiBranchingInformation *) { //  return new CouenneBranchingObject (Argument (), 0); return NULL; } */
• ## branches/Couenne/Couenne/src/branch/operators/branchExprLog.cpp

 r537 #include #include #include #include double * &brpts, int &way) { ind = -1; return 0.; /*  ind = argument_ -> Index (); // quite similar to exprExp::selectBranch() (see branchExprExp.cpp) if (ind < 0) { printf ("argument of exprAbs has negative index\n"); exit (-1); // two cases: inside or outside the belly. // // Inside: the distance depends on the projection of the current // point onto the would-be upper envelopes, which forces us to look // at it numerically. If both bounds are infinite, create a ThreeWay // branch. // // Outside: it suffices to project the current point on the line // (i.e. to get the closest point on the line) to get the maxi-min // displacement. // // As for all monotonous functions, after choosing *brpts it is // equivalent to choose w's or x's index as ind, as the implied- and // propagated bounds will do the rest. ind    = argument_ -> Index (); int wi = w         -> Index (); if ((ind < 0) || (wi < 0)) {printf ("Couenne, w=log(x): negative index\n"); exit (-1);} CouNumber y0 = info -> solution_ [wi], x0 = info -> solution_ [ind], l  = info -> lower_    [ind], u  = info -> upper_    [ind]; if (y0 > log (x0)) { if (x0 == 0) x0 = 1e-30; // Outside brpts = (double *) realloc (brpts, sizeof (double)); *brpts = powNewton (x0, y0, log, inv, oppInvSqr); if      (*brpts < l) *brpts = (u < COUENNE_INFINITY) ? ((l+u)/2) : (10*l + 1); else if (*brpts > u) *brpts = (l+u) / 2; way = TWO_LEFT; CouNumber dy = y0 - log (*brpts); x0 -= *brpts; return sqrt (x0*x0 + dy*dy); } // Inside. Two cases: if ((l < COUENNE_EPS * COUENNE_EPS) && (u > COUENNE_INFINITY)) { // 1) curve is unlimited in both senses --> three way branching brpts = (double *) realloc (brpts, 2 * sizeof (double)); way = THREE_CENTER; // focus on central convexification first brpts [0] = exp (y0); // draw horizontal from (x0,y0) south to curve y=log(x) brpts [1] = x0;       //      vertical                east CouNumber a = x0 - exp (y0), // sides of a triangle with (x0,y0) b = y0 - log (x0), // as one of the vertices c = a * cos (atan (a/b)); return mymin (a, mymin (b, c)); } // 2) at least one of them is finite --> two way branching brpts = (double *) realloc (brpts, sizeof (double)); if (l < COUENNE_EPS * COUENNE_EPS) { *brpts = exp (y0); if ((*brpts > u - COUENNE_NEAR_BOUND) || (*brpts < l + COUENNE_NEAR_BOUND)) *brpts = (l+u) / 2; way = TWO_RIGHT; return mymin (x0 - exp (y0), y0 - log (x0)); } if (u > COUENNE_INFINITY) { brpts = (double *) malloc (sizeof (double)); *brpts = 0.; way = TWO_LEFT; *brpts = x0; if (*brpts < l + COUENNE_NEAR_BOUND) *brpts = l+1; way = TWO_LEFT; return y0 - log (x0); return mymin (project (1., -1., 0., x0, y0, 0., COUENNE_INFINITY,  0, NULL, NULL), project (1., +1., 0., x0, y0, -COUENNE_INFINITY, 0., 0, NULL, NULL));*/ } // both are finite *brpts = powNewton (x0, y0, log, inv, oppInvSqr); if ((*brpts > u - COUENNE_NEAR_BOUND) || (*brpts < l + COUENNE_NEAR_BOUND)) *brpts = (l+u) / 2; way = TWO_RAND; CouNumber dx = x0 - *brpts, dy = y0 - log (*brpts); return sqrt (dx*dx + dy*dy); } /* /// distance covered by current point if branching rule applied to this expression double exprLog::BranchGain (expression *w, const OsiBranchingInformation *info) { int xi = argument_ -> Index (), wi = w         -> Index (); if (xi < 0 || wi < 0) { printf ("negative indices inbranchExprAbs\n"); exit (-1); } CouNumber x0 = expression::Variable (xi), y0 = expression::Variable (wi); return 0; //  return mymin (project (1, -1, 0, x0, y0, 0, COUENNE_INFINITY,  0, NULL, NULL), //            project (1, +1, 0, x0, y0, -COUENNE_INFINITY, 0, 0, NULL, NULL)); } /// branching object best suited for this expression OsiBranchingObject *exprLog::BranchObject (expression *w, const OsiBranchingInformation *) { // branching once on 0 is sufficient for expressions w=|x| //  return new CouenneBranchingObject (Argument (), 0); return NULL; } */
• ## branches/Couenne/Couenne/src/branch/operators/branchExprMul.cpp

 r537 * Name:    branchExprMul.cpp * Author:  Pietro Belotti * Purpose: return branch gain and branch object for multiplications * Purpose: return branch data for multiplications * * (C) Pietro Belotti. This file is licensed under the Common Public License (CPL) #define LARGE_BOUND 9.9e12 #define BOUND_WING 100 /// set up branching object by evaluating many branching points for /// each expression's arguments double * &brpts, int &way) { int xi = arglist_ [0] -> Index (), yi = arglist_ [1] -> Index (); if ((xi < 0) || (yi < 0)) { printf ("arguments of exprMul have negative index\n"); exit (-1); } CouNumber x0 = expression::Variable (xi),   y0 = expression::Variable (yi), xl = expression::Lbound   (xi),   yl = expression::Lbound   (yi), xu = expression::Ubound   (xi),   yu = expression::Ubound   (yi); // First, try to avoid infinite bounds for multiplications, which // make them pretty hard to deal with if ((xl < - COUENNE_INFINITY) && (xu >   COUENNE_INFINITY)) { // first ind = xi; // branch around current point. If it is also at a crazy value, // reset it close to zero. brpts = (double *) malloc (2 * sizeof (double)); CouNumber curr = x0; if (fabs (curr) >= LARGE_BOUND) curr = 0; brpts [0] = curr - BOUND_WING; brpts [1] = curr + BOUND_WING; way = THREE_CENTER; return COUENNE_INFINITY; } if ((yl < - COUENNE_INFINITY) && (yu >   COUENNE_INFINITY)) { // and second factor ind = yi; // branch around current point. If it is also at a crazy value, // reset it close to zero. brpts = (double *) malloc (2 * sizeof (double)); CouNumber curr = y0; if (fabs (curr) >= LARGE_BOUND) curr = 0; brpts [0] = curr - BOUND_WING; brpts [1] = curr + BOUND_WING; way = THREE_CENTER; return COUENNE_INFINITY; } // there is at least one finite corner of the bounding box ind = -1; return 0.; //  ind = argument_ -> Index (); /*if (ind < 0) { printf ("argument of exprAbs has negative index\n"); exit (-1); } brpts = (double *) malloc (sizeof (double)); *brpts = 0.; way = TWO_LEFT; return mymin (project (1., -1., 0., x0, y0, 0., COUENNE_INFINITY,  0, NULL, NULL), project (1., +1., 0., x0, y0, -COUENNE_INFINITY, 0., 0, NULL, NULL));*/ } /* /// distance covered by current point if branching rule applied to this expression double exprMul::BranchGain (expression *w, const OsiBranchingInformation *info) { int xi = arglist_ [0] -> Index (), yi = arglist_ [1] -> Index (), wi = w            -> Index (); CouNumber x0 = expression::Variable (xi), y0 = expression::Variable (yi), w0 = expression::Variable (wi); return 0; //  return mymin (project (1, -1, 0, x0, y0, 0, COUENNE_INFINITY,  0, NULL, NULL), //            project (1, +1, 0, x0, y0, -COUENNE_INFINITY, 0, 0, NULL, NULL)); } /// branching object best suited for this expression OsiBranchingObject *exprMul::BranchObject (expression *w, const OsiBranchingInformation *) { // branching once on 0 is sufficient for expressions w=|x| //  return new CouenneBranchingObject (Argument (), 0); return NULL; } */
• ## branches/Couenne/Couenne/src/convex/CouenneCutGenerator.h

 r556 /// tighten bounds using propagation, implied bounds and reduced costs bool boundTightening (const OsiSolverInterface &, OsiCuts &, char *, Bonmin::BabInfo * = NULL) const; t_chg_bounds *, Bonmin::BabInfo * = NULL) const; /// Optimality Based Bound Tightening int obbt (const OsiSolverInterface &, OsiCuts &, char *, Bonmin::BabInfo *) const; int obbt (OsiSolverInterface *, OsiCuts &, t_chg_bounds *, Bonmin::BabInfo *) const; };
• ## branches/Couenne/Couenne/src/convex/boundTightening.cpp

 r553 bool CouenneCutGenerator::boundTightening (const OsiSolverInterface &si, OsiCuts &cs, char *chg_bds, t_chg_bounds *chg_bds, Bonmin::BabInfo * babInfo) const { //      printf ("updating upper %g <-- %g\n", primal0, primal); problem_ -> Ub (objInd) = UB; chg_bds [objInd] = 1; chg_bds [objInd]. upper = CHANGED; } (LB   > dual0 + COUENNE_EPS)) { // update dual bound problem_ -> Lb (objInd) = LB; chg_bds [objInd] = 1; chg_bds [objInd]. lower = CHANGED; } // can improve bound on variable w_i problem_ -> Ub (i) = x + (UB-LB) / rc; chg_bds [i] = 1; chg_bds [i].upper = CHANGED; } } // expression structure is not a tree. // TODO: limit should depend on number of constraints, that is, // bound transmission should be documented and the cycle should stop // as soon as no new constraint subgraph has benefited from bound // transmission. return true; }
• ## branches/Couenne/Couenne/src/convex/generateCuts.cpp

 r556 // translate changed bound sparse array into a dense one void sparse2dense (int ncols, char *chg_bds, int *&changed, int &nchanged) { void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged) { // convert sparse chg_bds in something handier nchanged = 0; for (register int i=ncols, j=0; i--; j++) if (*chg_bds++) { for (register int i=ncols, j=0; i--; j++, chg_bds++) if (chg_bds -> lower || chg_bds -> upper) { *changed++ = j; nchanged++; // used with malloc/realloc/free char *chg_bds = new char [ncols]; t_chg_bounds *chg_bds = new t_chg_bounds [ncols]; // fill it with zeros for (register int i = ncols; i--;) *chg_bds++ = 0; for (register int i = ncols; i--; chg_bds++) chg_bds -> lower = chg_bds -> upper = UNCHANGED; chg_bds -= ncols; const double * nowUpper = si.getColUpper(); for (register int i=0; i < ncols; i++) if (beforeLower && (nowLower [i] >= beforeLower [i] + COUENNE_EPS) || beforeUpper && (nowUpper [i] <= beforeUpper [i] - COUENNE_EPS)) chg_bds [i] = 1; for (register int i=0; i < ncols; i++) { if (beforeLower && (nowLower [i] >= beforeLower [i] + COUENNE_EPS)) chg_bds [i].lower = CHANGED; if (beforeUpper && (nowUpper [i] <= beforeUpper [i] - COUENNE_EPS)) chg_bds [i].upper = CHANGED; } } else printf ("WARNING: could not access parent's bounds\n"); if ((!firstcall_ || (info.pass > 0)) && (CoinDrand48 () < (double) COU_OBBT_CUTOFF_LEVEL / (info.level + 1))) { // apply OBBT at all levels up to the COU_OBBT_CUTOFF_LEVEL-th, // and then with probability inversely proportional to the level OsiSolverInterface *csi = si.clone (true); dynamic_cast (csi) -> setupForRepeatedUse (); int nImprov, nIter = 0; bool repeat = true; while (repeat && (nIter++ < MAX_OBBT_ITER) && ((nImprov = obbt (si, cs, chg_bds, babInfo)) > 0)) ((nImprov = obbt (csi, cs, chg_bds, babInfo)) > 0)) if (nImprov >= THRES_NBD_CHANGED) { sparse2dense (ncols, chg_bds, changed, nchanged); genColCuts (si, cs, nchanged, changed); genColCuts (*csi, cs, nchanged, changed); int nCurCuts = cs.sizeRowCuts (); genRowCuts (si, cs, nchanged, changed);// !!! genRowCuts (*csi, cs, nchanged, changed);// !!! repeat = nCurCuts < cs.sizeRowCuts (); // reapply only if new cuts available } delete csi; if (nImprov < 0)
• ## branches/Couenne/Couenne/src/convex/obbt.cpp

 r556 #define OBBT_EPS 1e-3 #define MAX_OBBT_LP_ITERATION 100 /// reoptimize and change bound of a variable if needed bool isint) {            /// is this variable integer csi -> setObjSense (sense); csi -> setDblParam (OsiDualObjectiveLimit, (sense == 1) ? COUENNE_INFINITY : -COUENNE_INFINITY); csi -> setObjSense (sense); csi -> setDblParam (OsiPrimalObjectiveLimit, bound); csi -> resolve (); /// Optimality based bound tightening int CouenneCutGenerator::obbt (const OsiSolverInterface &si, OsiCuts &cs, char *chg_bds, Bonmin::BabInfo * babInfo) const { int nImprov = 0, ncols   = si.getNumCols (), objind  = problem_ -> Obj (0) -> Body () -> Index (); /// visit all variables (in one sense) and apply OBBT to each int obbt_stage (const CouenneCutGenerator *cg, OsiSolverInterface *csi, OsiCuts &cs, t_chg_bounds *chg_bds, Bonmin::BabInfo * babInfo, int sense) { CouenneProblem *p = cg -> Problem (); int ncols   = csi -> getNumCols (), objind  = p -> Obj (0) -> Body () -> Index (), nImprov = 0; double *objcoe = (double *) malloc (ncols * sizeof (double)); objcoe -= ncols; // create clone of current solver interface // TODO: clone only at pass 0 and delete at the end OsiSolverInterface *csi = si.clone (true); // apply all (row+column) cuts to formulation csi -> applyCuts (cs); // for all (original+auxiliary) variables x_i, //////////////////////////////////////////////////// for (int i=0; inVars(); i++) if (i != objind) { // do not improve objective's bounds if ((i != objind) && ((sense > 0) && !(chg_bds [i].lower & EXACT) || (sense < 0) && !(chg_bds [i].upper & EXACT))) { // do not improve objective's bounds int nOrig = problem_ -> nVars (); bool chg  = false, isInt  = (i < nOrig) ? (problem_ -> Var (i)       -> isInteger ()) : (problem_ -> Aux (i-nOrig) -> isInteger ()); int nOrig  = p -> nVars (); bool isInt = (i < nOrig) ? (p -> Var (i)       -> isInteger ()) : (p -> Aux (i-nOrig) -> isInteger ()); objcoe [i] = 1; csi -> setObjective (objcoe); // minimize... CouNumber &bound = (sense == 1) ? (p -> Lb (i)) : (p -> Ub (i)); if (updateBound (csi, 1, problem_ -> Lb (i), isInt)) { csi -> setColLower (i, problem_ -> Lb (i)); chg = true; } // ...and then maximize x_i on csi. // m{in,ax}imize xi on csi if (updateBound (csi, -1, problem_ -> Ub (i), isInt)) { csi -> setColUpper  (i, problem_ -> Ub (i)); chg = true; } if (updateBound (csi, sense, bound, isInt)) { if (chg) { const double *sol = csi -> getColSolution (); if (!(boundTightening (si, cs, chg_bds, babInfo))) { delete csi; if (sense==1) {csi -> setColLower (i, bound); chg_bds [i].lower |= CHANGED | EXACT;} else          {csi -> setColUpper (i, bound); chg_bds [i].upper |= CHANGED | EXACT;} // check value and bounds of other variables for (int j=0; j Lb (j) + COUENNE_EPS) chg_bds [j].lower |= EXACT; if (sol [j] >= p -> Ub (j) - COUENNE_EPS) chg_bds [j].upper |= EXACT; } // re-check considering reduced costs (more expensive) CouNumber *redcost = NULL; // first, compute reduced cost when c = c - e_i, where e_i is // a vector with all zero except a one in position i. This // serves as a base to compute modified reduced cost below. if (0) for (int j=0; j Lb (j) + COUENNE_EPS) chg_bds [j].lower |= EXACT; if (sol [j] >= p -> Ub (j) - COUENNE_EPS) chg_bds [j].upper |= EXACT; } // re-apply bound tightening if (!(cg -> boundTightening (*csi, cs, chg_bds, babInfo))) return -1; // tell caller this is infeasible } chg_bds [i] = 1; nImprov++; } } delete csi; return nImprov; } /// Optimality based bound tightening int CouenneCutGenerator::obbt (OsiSolverInterface *csi, OsiCuts &cs, t_chg_bounds *chg_bds, Bonmin::BabInfo * babInfo) const { int nImprov; csi -> setIntParam (OsiMaxNumIteration, MAX_OBBT_LP_ITERATION); // apply all (row+column) cuts to formulation csi -> applyCuts (cs); nImprov =  obbt_stage (this, csi, cs, chg_bds, babInfo,  1); // minimization nImprov += obbt_stage (this, csi, cs, chg_bds, babInfo, -1); // maximization return nImprov; }
• ## branches/Couenne/Couenne/src/expression/CouenneTypes.h

 r545 enum convexity {NONCONVEX, CONVEX, CONCAVE, AFFINE}; /** (un)changed bounds */ #define UNCHANGED 0 #define CHANGED   1 #define EXACT     2 typedef struct chg_bounds { char lower; char upper; } t_chg_bounds; typedef double CouNumber; typedef CouNumber (*unary_function) (CouNumber);
• ## branches/Couenne/Couenne/src/expression/exprCopy.h

 r543 /// implied bound processing bool impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) bool impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) {return copy_ -> impliedBound (wind, l, u, chg);} };
• ## branches/Couenne/Couenne/src/expression/exprVar.cpp

 r476 /// implied bound processing. Expression w = x, upon change in lower /// or upper bound of w, whose index is wind bool exprVar::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprVar::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { bool res = updateBound (-1, l + varIndex_, l [wind]); res      = updateBound (+1, u + varIndex_, u [wind]) || res; bool res; if (res) chg [varIndex_] = 1; if (updateBound (-1, l + varIndex_, l [wind])) {res = true; chg [varIndex_].lower = CHANGED;} if (updateBound (+1, u + varIndex_, u [wind])) {res = true; chg [varIndex_].upper = CHANGED;} return res;
• ## branches/Couenne/Couenne/src/expression/exprVar.h

 r543 /// implied bound processing virtual bool impliedBound (int, CouNumber *, CouNumber *, char *); virtual bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// rank of an original variable is always one
• ## branches/Couenne/Couenne/src/expression/expression.h

 r556 /// bound. The method returns the best bound improvement obtained on /// all variables of the expression. virtual bool impliedBound (int, CouNumber *, CouNumber *, char *) virtual bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *) {return false;}
• ## branches/Couenne/Couenne/src/expression/operators/exprAbs.cpp

 r543 /// printing //void exprAbs::print (std::ostream& out) const { //  exprUnary::print (out, "abs", PRE); /* out << "|"; argument_ -> print (out); out << "|"; */ //} /// implied bound processing for expression w = |x|, upon change in /// lower- and/or upper bound of w, whose index is wind bool exprAbs::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprAbs::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { int index = argument_ -> Index (); if (wl > 0) { if (*xl > 0) tighter = updateBound (-1, xl,  wl); if (*xu < 0) tighter = updateBound (+1, xu, -wl) || tighter; if      (*xl > 0) {if (updateBound (-1, xl,  wl)) {tighter = true; chg [index].lower = CHANGED;}} else if (*xu < 0) {if (updateBound (+1, xu, -wl)) {tighter = true; chg [index].upper = CHANGED;}} } // w <= u (if u < 0 the problem is infeasible) tighter = updateBound (-1, xl, -wu) || tighter; tighter = updateBound (+1, xu,  wu) || tighter; if (tighter) chg [index] = 1; if (updateBound (-1, xl, -wu)) {tighter = true; chg [index].lower = CHANGED;} if (updateBound (+1, xu,  wu)) {tighter = true; chg [index].upper = CHANGED;} return tighter;
• ## branches/Couenne/Couenne/src/expression/operators/exprAbs.h

 r543 /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// set up branching object by evaluating many branching points for
• ## branches/Couenne/Couenne/src/expression/operators/exprCos.h

 r551 {return "cos";} /// print position //  virtual const std::string printPos () //    {return PRE;} /// print "cos" and argument //  void print (std::ostream&) const; /// obtain derivative of expression expression *differentiate (int index); /// convex envelope for sine/cosine //void addHexagon (const CouenneCutGenerator *, // pointer to the caller cut generator //               OsiCuts &,      // cut set to be enriched //               unary_function, // sine or cosine //               exprAux *,      // auxiliary variable //               expression *);  // argument of cos/sin (should be a variable) #endif
• ## branches/Couenne/Couenne/src/expression/operators/exprDiv.h

 r543 #include #include #define BR_NEXT_ZERO 1e-3 #define BR_MULT      1e-3 /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// set up branching object by evaluating many branching points for
• ## branches/Couenne/Couenne/src/expression/operators/exprExp.cpp

 r543 /* * Name:    exprExp.C * Name:    exprExp.cpp * Author:  Pietro Belotti * Purpose: definition of the exponential /// implied bound processing for expression w = exp(x), upon change in /// lower- and/or upper bound of w, whose index is wind bool exprExp::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprExp::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { bool res = false; bool resU, resL = resU = false; int ind = argument_ -> Index (); if ((b = l [wind]) >= COUENNE_EPS) // lower bound res = updateBound (-1, l + ind, log (b)); resL = updateBound (-1, l + ind, log (b)); if ((b = u [wind]) >= COUENNE_EPS) // upper bound res = updateBound ( 1, u + ind, log (b)) || res; resU = updateBound ( 1, u + ind, log (b)); else if (b < - COUENNE_EPS) { // make it infeasible res = updateBound ( 1, u + ind, -1) || res; res = updateBound (-1, l + ind,  1) || res; resU = updateBound ( 1, u + ind, -1) || resU; resL = updateBound (-1, l + ind,  1) || resL; } if (res) chg [ind] = 1; if (resL) chg [ind].lower = CHANGED; if (resU) chg [ind].upper = CHANGED; return res; return (resL || resU); }
• ## branches/Couenne/Couenne/src/expression/operators/exprExp.h

 r543 /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// set up branching object by evaluating many branching points for
• ## branches/Couenne/Couenne/src/expression/operators/exprInv.cpp

 r545 /// general function (see below) bool invPowImplBounds (int, int, CouNumber *, CouNumber *, CouNumber); /// general function to tighten implied bounds of a function w = x^k, /// k negative, integer or inverse integer, and odd void invPowImplBounds (int wind, int index, CouNumber *l, CouNumber *u, CouNumber k, bool &resL, bool &resU) { CouNumber wl = l [wind], wu = u [wind]; // 0 <= l <= w <= u if (wl >= 0.) { if (wu > COUENNE_EPS) { if (wu < COUENNE_INFINITY - 1) resL = updateBound (-1, l + index, pow (wu, k)); else                           resL = updateBound (-1, l + index, 0.); } if (wl > COUENNE_EPS)            resU = updateBound (+1, u + index, pow (wl, k)); } // l <= w <= u <= 0 if (wu <= -0.) { if (wl < - COUENNE_EPS) { if (wl > - COUENNE_INFINITY + 1) resU = updateBound (+1, u + index, pow (wl, k)) || resU; else                             resU = updateBound (+1, u + index, 0.)          || resU; } if (wu < - COUENNE_EPS)            resL = updateBound (-1, l + index, pow (wu, k)) || resL; } } /// lower- and/or upper bound of w, whose index is wind bool exprInv::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprInv::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { // Expression w = 1/x: we can only improve the bounds if int index = argument_ -> Index (); bool res = invPowImplBounds (wind, index, l, u, -1.); bool resL, resU = resL = false; if (res) chg [index] = 1; invPowImplBounds (wind, index, l, u, -1., resL, resU); return res; if (resL) chg [index].lower = CHANGED; if (resU) chg [index].upper = CHANGED; return (resL || resU); } /// general function to tighten implied bounds of a function w = x^k, /// k negative, integer or inverse integer, and odd bool invPowImplBounds (int wind, int index, CouNumber *l, CouNumber *u, CouNumber k) { CouNumber wl = l [wind], wu = u [wind]; bool res = false; // 0 <= l <= w <= u if (wl >= 0.) { if (wu > COUENNE_EPS) { if (wu < COUENNE_INFINITY - 1) res = updateBound (-1, l + index, pow (wu, k)); else                           res = updateBound (-1, l + index, 0.); } if (wl > COUENNE_EPS)            res = updateBound (+1, u + index, pow (wl, k)) || res; } // l <= w <= u <= 0 if (wu <= -0.) { if (wl < - COUENNE_EPS) { if (wl > - COUENNE_INFINITY + 1) res = updateBound (+1, u + index, pow (wl, k)) || res; else                             res = updateBound (+1, u + index, 0.)          || res; } if (wu < - COUENNE_EPS)            res = updateBound (-1, l + index, pow (wu, k)) || res; } return res; }
• ## branches/Couenne/Couenne/src/expression/operators/exprInv.h

 r543 /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// set up branching object by evaluating many branching points for
• ## branches/Couenne/Couenne/src/expression/operators/exprLog.cpp

 r543 /// printing //void exprLog::print (std::ostream& out) const //{exprUnary::print (out, "log", PRE);} /// implied bound processing for expression w = log(x), upon change in /// lower- and/or upper bound of w, whose index is wind bool exprLog::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprLog::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { int ind = argument_ -> Index (); bool res; bool res = updateBound (-1, l + ind, exp (l [wind])); res      = updateBound ( 1, u + ind, exp (u [wind])) || res; if (res) { /*printf ("w_%d [%g,%g] -------> x_%d in [%g,%g] ", wind, l [wind], u [wind], ind,  l [ind],  u [ind]);*/ chg [ind] = 1; } if (updateBound (-1, l + ind, exp (l [wind]))) {res = true; chg [ind].lower = CHANGED;} if (updateBound ( 1, u + ind, exp (u [wind]))) {res = true; chg [ind].upper = CHANGED;} return res;
• ## branches/Couenne/Couenne/src/expression/operators/exprLog.h

 r543 OsiCuts &cs, const CouenneCutGenerator *cg); /// /// code for comparisons virtual enum expr_type code () {return COU_EXPRINV;} /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// set up branching object by evaluating many branching points for
• ## branches/Couenne/Couenne/src/expression/operators/exprMul.h

 r543 /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// set up branching object by evaluating many branching points for
• ## branches/Couenne/Couenne/src/expression/operators/exprOpp.cpp

 r543 // printing //void exprOpp::print (std::ostream& out) const //{exprUnary::print (out, "-", PRE);} /// implied bound processing for expression w = -x, upon change in /// lower- and/or upper bound of w, whose index is wind bool exprOpp::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprOpp::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { int ind = argument_ -> Index (); bool res; bool res = updateBound (-1, l + ind, - u [wind]); res      = updateBound ( 1, u + ind, - l [wind]) || res; if (res) chg [ind] = 1; if (updateBound (-1, l + ind, - u [wind])) {res = true; chg [ind].lower = CHANGED;} if (updateBound ( 1, u + ind, - l [wind])) {res = true; chg [ind].upper = CHANGED;} return res;
• ## branches/Couenne/Couenne/src/expression/operators/exprOpp.h

 r543 OsiCuts &cs, const CouenneCutGenerator *cg); /// /// code for comparisons virtual enum expr_type code () {return COU_EXPROPP;} /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); };
• ## branches/Couenne/Couenne/src/expression/operators/exprPow.cpp

 r543 /// inverse integer, and odd bool invPowImplBounds (int, int, CouNumber *, CouNumber *, CouNumber); void invPowImplBounds (int, int, CouNumber *, CouNumber *, CouNumber, bool &, bool &); /// lower- and/or upper bound of w, whose index is wind bool exprPow::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool res = false; bool exprPow::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { bool resL, resU = resL = false; if (arglist_ [0] -> Type () <= CONST)   // base is constant or zero, nothing to do if (k > 0.) { // simple, just follow bounds if (wl > - COUENNE_INFINITY) res    = updateBound (-1, l + index, pow (wl, 1./k)); else res = updateBound (-1, l + index, - COUENNE_INFINITY); if (wu < COUENNE_INFINITY) res    = updateBound (+1, u + index, pow (wu, 1./k)) || res; else res = updateBound (+1, u + index, COUENNE_INFINITY); resL = (wl > - COUENNE_INFINITY) ? updateBound (-1, l + index, pow (wl, 1./k)) : updateBound (-1, l + index, - COUENNE_INFINITY); resU = (wu < COUENNE_INFINITY) ? updateBound (+1, u + index, pow (wu, 1./k)) : updateBound (+1, u + index, COUENNE_INFINITY); } else // slightly more complicated, resort to same method as in exprInv res = invPowImplBounds (wind, index, l, u, 1./k); invPowImplBounds (wind, index, l, u, 1./k, resL, resU); } else if (fabs (bound) < COUENNE_INFINITY) { res = updateBound (-1, l + index, - pow (bound, 1./k)); res = updateBound (+1, u + index,   pow (bound, 1./k)) || res; resL = updateBound (-1, l + index, - pow (bound, 1./k)); resU = updateBound (+1, u + index,   pow (bound, 1./k)); } else { res = updateBound (-1, l + index, - COUENNE_INFINITY); res = updateBound (+1, u + index,   COUENNE_INFINITY) || res; resL = updateBound (-1, l + index, - COUENNE_INFINITY); resU = updateBound (+1, u + index,   COUENNE_INFINITY); } } ub = wl; } if (lb > COUENNE_EPS) res = updateBound (-1, l + index, pow (lb, 1./k)); if (lb > COUENNE_EPS) resL = updateBound (-1, l + index, pow (lb, 1./k)); if (fabs (ub) < COUENNE_INFINITY) { if (ub > COUENNE_EPS) res = updateBound (+1, u + index, pow (ub, 1./k)) || res; } else                  res = updateBound (+1, u + index, COUENNE_INFINITY) || res; } return res; } if (ub > COUENNE_EPS) resU = updateBound (+1, u + index, pow (ub, 1./k)); } else                  resU = updateBound (+1, u + index, COUENNE_INFINITY); } if (resL) chg [index].lower = CHANGED; if (resU) chg [index].upper = CHANGED; return (resL || resU); }
• ## branches/Couenne/Couenne/src/expression/operators/exprPow.h

 r543 /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// set up branching object by evaluating many branching points for
• ## branches/Couenne/Couenne/src/expression/operators/exprSub.cpp

 r543 /// lower- and/or upper bound of w, whose index is wind bool exprSub::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprSub::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { // caution, xi or yi might be -1 bool res = false; return false; /// !!! REMOVED A return false; // w >= l if ((xi >= 0) && (res = updateBound (-1, l + xi, yl + wl)))        chg [xi] = 1; if ((yi >= 0) && (res = updateBound (+1, u + yi, xu - wl) || res)) chg [yi] = 1; if ((xi >= 0) && (updateBound (-1, l + xi, yl + wl))) {res = true; chg [xi].lower = CHANGED;} if ((yi >= 0) && (updateBound (+1, u + yi, xu - wl))) {res = true; chg [yi].upper = CHANGED;} // w <= u if ((xi >= 0) && (res = updateBound (+1, u + xi, yu + wu) || res)) chg [xi] = 1; if ((yi >= 0) && (res = updateBound (-1, l + yi, xl - wu) || res)) chg [yi] = 1; if ((xi >= 0) && (updateBound (+1, u + xi, yu + wu))) {res = true; chg [xi].upper = CHANGED;} if ((yi >= 0) && (updateBound (-1, l + yi, xl - wu))) {res = true; chg [yi].lower = CHANGED;} return res;
• ## branches/Couenne/Couenne/src/expression/operators/exprSub.h

 r543 /// implied bound processing bool impliedBound (int, CouNumber *, CouNumber *, char *); bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); };
• ## branches/Couenne/Couenne/src/expression/operators/exprSum.h

 r543 /// implied bound processing virtual bool impliedBound (int, CouNumber *, CouNumber *, char *); virtual bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *); /// compute best variable to branch on (nonsense here, as there is
• ## branches/Couenne/Couenne/src/expression/operators/impliedBounds-exprDiv.cpp

 r524 /// lower- and/or upper bound of w, whose index is wind bool exprDiv::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprDiv::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { bool resx, resy = resx = false; if (c > COUENNE_EPS) { resx = updateBound (-1, l + ind, l [wind] * c); resx = updateBound ( 1, u + ind, u [wind] * c) || resx; if (updateBound (-1, l + ind, l [wind] * c)) {resx = true; chg [ind].lower = CHANGED;} if (updateBound ( 1, u + ind, u [wind] * c)) {resx = true; chg [ind].upper = CHANGED;} } else if (c < - COUENNE_EPS) { resx = updateBound (-1, l + ind, u [wind] * c); resx = updateBound ( 1, u + ind, l [wind] * c) || resx; if (updateBound (-1, l + ind, u [wind] * c)) {resx = true; chg [ind].lower = CHANGED;} if (updateBound ( 1, u + ind, l [wind] * c)) {resx = true; chg [ind].upper = CHANGED;} } if (resx) chg [ind] = 1; } else { int xi = arglist_ [0] -> Index (), yi = arglist_ [1] -> Index (); CouNumber x0; // deal with all other cases // may improve). int xi = arglist_ [0] -> Index (), yi = arglist_ [1] -> Index (); CouNumber x0; CouNumber *xl = l + xi, *yl = l + yi, wl = l [wind], *xu = u + xi, *yu = u + yi, wu = u [wind]; } bool resxL, resxU, resyL, resyU = resxL = resxU = resyL = false; // general case // point C: (xl,yl) resy = (*yl<0) && (*yl > *xl/wl) && updateBound (-1, yl, 0) || resy;// resyL = (*yl<0) && (*yl > *xl/wl) && updateBound (-1, yl, 0) || resyL; // if ((*yl>0) && (*yl < *xl/wl)) { // point C violates x/y >= wl, down resx = updateBound (-1, xl, *yu*wl) || resx;// resy = updateBound (-1, yl, *xu/wl) || resy;// resxL = updateBound (-1, xl, *yu*wl) || resxL; // resyL = updateBound (-1, yl, *xu/wl) || resyL; // } if ((*yu<0) && (*yu > *xu/wl)) { // point B violates x/y >= wl, down resx = updateBound (+1, xu, *yl*wl) || resx; resy = updateBound (+1, yu, *xl/wl) || resy; } resy = (*yu>0) && (*yu < *xu/wl) && updateBound (+1, yu, 0) || resy; resxU = updateBound (+1, xu, *yl*wl) || resxU; resyU = updateBound (+1, yu, *xl/wl) || resyU; } resyU = (*yu>0) && (*yu < *xu/wl) && updateBound (+1, yu, 0) || resyU; } else if (wl >   COUENNE_EPS) { // w >= wl, wl positive // resy = (*yl<0) && (*yl < *xl/wl) && updateBound (-1, yl, mymin (*xl/wl, 0)) || resy; resx = (*yl>0) && (*yl > *xl/wl) && updateBound (-1, xl, *yl*wl)            || resx; // resx = (*yu<0) && (*yu < *xu/wl) && updateBound (+1, xu, *yu*wl)            || resx; resy = (*yu>0) && (*yu > *xu/wl) && updateBound (+1, yu, mymax (*xu/wl, 0)) || resy; resyL = (*yl<0) && (*yl < *xl/wl) && updateBound (-1, yl, mymin (*xl/wl, 0)) || resyL; resxL = (*yl>0) && (*yl > *xl/wl) && updateBound (-1, xl, *yl*wl)            || resxL; // resxU = (*yu<0) && (*yu < *xu/wl) && updateBound (+1, xu, *yu*wl)            || resxU; resyU = (*yu>0) && (*yu > *xu/wl) && updateBound (+1, yu, mymax (*xu/wl, 0)) || resyU; } // resy = (*yl<0) && (*yl > *xu/wu) && updateBound (-1, yl, 0)      || resy; resyL = (*yl<0) && (*yl > *xu/wu) && updateBound (-1, yl, 0)      || resyL; if ((*yl>0) && (*yl < *xu/wu)) { resx = updateBound (+1, xu, *yu*wu) || resx; resy = updateBound (-1, yl, *xl/wu) || resy; resxU = updateBound (+1, xu, *yu*wu) || resxU; resyL = updateBound (-1, yl, *xl/wu) || resyL; } if ((*yu<0) && (*yu > *xl/wu)) { resx = updateBound (-1, xl, *yl*wu) || resx; resy = updateBound (+1, yu, *xu/wu) || resy; } resy = (*yu>0) && (*yu < *xl/wu) && updateBound (+1, yu, 0)      || resy; resxL = updateBound (-1, xl, *yl*wu) || resxL; resyU = updateBound (+1, yu, *xu/wu) || resyU; } resyU = (*yu>0) && (*yu < *xl/wu) && updateBound (+1, yu, 0)      || resyU; } else if (wu < - COUENNE_EPS) { // w <= wu, wu negative // resy = (*yl<0) && (*yl < *xu/wu) && updateBound (-1, yl, mymin (*xu/wu,0))  || resy;// resx = (*yu<0) && (*yu < *xl/wu) && updateBound (-1, xl, *yu*wu)            || resx; // resx = (*yl>0) && (*yl > *xu/wu) && updateBound (+1, xu, *yl*wu)            || resx; resy = (*yu>0) && (*yu > *xl/wu) && updateBound (+1, yu, mymax (*xl/wu,0))  || resy; } if (resx) chg [xi] = 1; if (resy) chg [yi] = 1; resyL = (*yl<0) && (*yl < *xu/wu) && updateBound (-1, yl, mymin (*xu/wu,0))  || resyL;// resxL = (*yu<0) && (*yu < *xl/wu) && updateBound (-1, xl, *yu*wu)            || resxL; // resxU = (*yl>0) && (*yl > *xu/wu) && updateBound (+1, xu, *yl*wu)            || resxU; resyU = (*yu>0) && (*yu > *xl/wu) && updateBound (+1, yu, mymax (*xl/wu,0))  || resyU; } if (resxL) chg [xi].lower = CHANGED; if (resxU) chg [xi].upper = CHANGED; if (resyL) chg [yi].lower = CHANGED; if (resyU) chg [yi].upper = CHANGED; /*if (resx || resy) wind, wl, wu, xi, *xl, *xu, yi, *yl, *yu); else printf ("                                                 \r");*/ resx = resxL || resxU; resy = resyL || resyU; }
• ## branches/Couenne/Couenne/src/expression/operators/impliedBounds-exprMul.cpp

 r525 /// lower- and/or upper bound of w, whose index is wind bool exprMul::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprMul::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { bool res = false; bool resL, resU = resL = false; int ind; res = (l [wind] > - COUENNE_INFINITY) && updateBound (-1, l + ind, l [wind] / c); res = (u [wind] <   COUENNE_INFINITY) && updateBound ( 1, u + ind, u [wind] / c) || res; resL = (l [wind] > - COUENNE_INFINITY) && updateBound (-1, l + ind, l [wind] / c); resU = (u [wind] <   COUENNE_INFINITY) && updateBound ( 1, u + ind, u [wind] / c); } else if (c < - COUENNE_EPS) { //      return false; //      printf ("w_%d [%g,%g] = %g x_%d [%g,%g]\n", //              wind, l [wind], u [wind], c, ind, l [ind], u [ind]); res = (u [wind] <   COUENNE_INFINITY) && updateBound (-1, l + ind, u [wind] / c); res = (l [wind] > - COUENNE_INFINITY) && updateBound ( 1, u + ind, l [wind] / c) || res; resL = (u [wind] <   COUENNE_INFINITY) && updateBound (-1, l + ind, u [wind] / c); resU = (l [wind] > - COUENNE_INFINITY) && updateBound ( 1, u + ind, l [wind] / c); } if (res) { chg [ind] = 1; if (resL) chg [ind].lower = CHANGED; if (resU) chg [ind].upper = CHANGED; /*printf ("w_%d [%g,%g] -------> x_%d in [%g,%g] ", wind, l [wind], u [wind], ind,  l [ind],  u [ind]);*/ } } else { // w's lower bound bool resx = false, resy = false; bool resxL, resxU, resyL, resyU = resxL = resxU = resyL = false; if (wl >= 0.) { if (*xu * *yu < wl) { resx = (*xu * *yl < wl) && updateBound (+1, xu, wl / *yl) || resx; resy = (*xl * *yu < wl) && updateBound (+1, yu, wl / *xl) || resy; resxU = (*xu * *yl < wl) && updateBound (+1, xu, wl / *yl); resyU = (*xl * *yu < wl) && updateBound (+1, yu, wl / *xl); } if (*xl * *yl < wl) { resx = (*xl * *yu < wl) && updateBound (-1, xl, wl / *yu) || resx; resy = (*xu * *yl < wl) && updateBound (-1, yl, wl / *xu) || resy; resxL = (*xl * *yu < wl) && updateBound (-1, xl, wl / *yu); resyL = (*xu * *yl < wl) && updateBound (-1, yl, wl / *xu); } } else { // upper left resx = (*xl * *yl < wl) && (*yl > 0.) && updateBound (-1, xl, wl / *yl) || resx; // point C resy = (*xu * *yu < wl) && (*yu > 0.) && updateBound (+1, yu, wl / *xu) || resy; // point B resxL = (*xl * *yl < wl) && (*yl > 0.) && updateBound (-1, xl, wl / *yl); // point C resyU = (*xu * *yu < wl) && (*yu > 0.) && updateBound (+1, yu, wl / *xu); // point B // lower right resy = (*xl * *yl < wl) && (*yl < 0.) && updateBound (-1, yl, wl / *xl) || resy; // point C resx = (*xu * *yu < wl) && (*yu < 0.) && updateBound (+1, xu, wl / *yu) || resx; // point B resyL = (*xl * *yl < wl) && (*yl < 0.) && updateBound (-1, yl, wl / *xl); // point C resxU = (*xu * *yu < wl) && (*yu < 0.) && updateBound (+1, xu, wl / *yu); // point B } // upper right resx = (*xu * *yl > wu) && (*yl > 0.) && updateBound (+1, xu, wu / *yl) || resx; // point D resy = (*xl * *yu > wu) && (*yu > 0.) && updateBound (+1, yu, wu / *xl) || resy; // point A resxU = (*xu * *yl > wu) && (*yl > 0.) && updateBound (+1, xu, wu / *yl) || resxU; // point D resyU = (*xl * *yu > wu) && (*yu > 0.) && updateBound (+1, yu, wu / *xl) || resyU; // point A // lower left resx = (*xl * *yu > wu) && (*yu < 0.) && updateBound (-1, xl, wu / *yu) || resx; // point A resy = (*xu * *yl > wu) && (*yl < 0.) && updateBound (-1, yl, wu / *xu) || resy; // point D resxL = (*xl * *yu > wu) && (*yu < 0.) && updateBound (-1, xl, wu / *yu) || resxL; // point A resyL = (*xu * *yl > wu) && (*yl < 0.) && updateBound (-1, yl, wu / *xu) || resyL; // point D } else { if (*xu * *yl > wu) { resx = (*xu * *yu > wu) && updateBound (+1, xu, wu / *yu) || resx; resy = (*xl * *yl > wu) && updateBound (-1, yl, wu / *xl) || resy; resxU = (*xu * *yu > wu) && updateBound (+1, xu, wu / *yu) || resxU; resyL = (*xl * *yl > wu) && updateBound (-1, yl, wu / *xl) || resyL; } if (*xl * *yu > wu) { resx = (*xl * *yl > wu) && updateBound (-1, xl, wu / *yl) || resx; resy = (*xu * *yu > wu) && updateBound (+1, yu, wu / *xu) || resy; resxL = (*xl * *yl > wu) && updateBound (-1, xl, wu / *yl) || resxL; resyU = (*xu * *yu > wu) && updateBound (+1, yu, wu / *xu) || resyU; } } else printf ("                                                 \r");*/ if (resx) chg [xi] = 1; if (resy) chg [yi] = 1; if (resxL) chg [xi].lower = CHANGED; if (resxU) chg [xi].upper = CHANGED; if (resyL) chg [yi].lower = CHANGED; if (resyU) chg [yi].upper = CHANGED; res = resx || resy; resL = resxL || resyL; resU = resxU || resyU; } return res; return (resL || resU); }
• ## branches/Couenne/Couenne/src/expression/operators/impliedBounds-exprSum.cpp

 r525 #define MALLOC_STEP 1000 bool exprSum::impliedBound (int wind, CouNumber *l, CouNumber *u, char *chg) { bool exprSum::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg) { /** int ind = I1 [i]; if (tighter = updateBound (+1, u + ind, (wu - lower) / C1 [i] + lc [ind]) || tighter) chg [ind] = 1; chg [ind].upper = CHANGED; } int ind = I2 [i]; if (tighter = updateBound (-1, l + ind, (wu - lower) / C2 [i] + uc [ind]) || tighter) chg [ind] = 1; chg [ind].lower = CHANGED; } } else int ind = I1 [infLo1]; if (tighter = updateBound (+1, u + ind, (wu - lower) / C1 [infLo1]) || tighter) chg [ind] = 1; chg [ind].upper = CHANGED; } else int ind = I2 [infUp2]; if (tighter = updateBound (-1, l + ind, (wu - lower) / C2 [infUp2]) || tighter) chg [ind] = 1; chg [ind].lower = CHANGED; } int ind = I1 [i]; if (tighter = updateBound (-1, l + ind, (wl - upper) / C1 [i] + uc [ind]) || tighter) chg [ind] = 1; chg [ind].lower = CHANGED; } int ind = I2 [i]; if (tighter = updateBound (+1, u + ind, (wl - upper) / C2 [i] + lc [ind]) || tighter) chg [ind] = 1; chg [ind].upper = CHANGED; } } else int ind = I1 [infUp1]; if (tighter = updateBound (-1, l + ind, (wl - upper) / C1 [infUp1]) || tighter) chg [ind] = 1; chg [ind].lower = CHANGED; } else int ind = I2 [infLo2]; if (tighter = updateBound (+1, u + ind, (wl - upper) / C2 [infLo2]) || tighter) chg [ind] = 1; chg [ind].upper = CHANGED; }
• ## branches/Couenne/Couenne/src/problem/CouenneProblem.h

 r545 /// bound tightening int tightenBounds (char *) const; int tightenBounds (t_chg_bounds *) const; /// search for implied bounds int impliedBounds (char *) const; int impliedBounds (t_chg_bounds *) const; };
• ## branches/Couenne/Couenne/src/problem/impliedBounds.cpp

 r556 /// Bound tightening for auxiliary variables int CouenneProblem::impliedBounds (char *chg_bds) const { int CouenneProblem::impliedBounds (t_chg_bounds *chg_bds) const { int nchg = 0, //< number of bounds changed for propagation
• ## branches/Couenne/Couenne/src/problem/tightenBounds.cpp

 r553 /// Bound propagation for auxiliary variables int CouenneProblem::tightenBounds (char *chg_bds) const { int CouenneProblem::tightenBounds (t_chg_bounds *chg_bds) const { int nchg = 0; //< number of bounds changed for propagation } bool chg = false; //      bool chg = false; // check if lower bound got higher lb_ [i+j] = ll; chg = true; chg_bds [i+j].lower = CHANGED; nchg++; } ub_ [i+j] = uu; chg = true; } if (chg && chg_bds && !(chg_bds [i+j])) { chg_bds [i+j].upper = CHANGED; nchg++; chg_bds [i+j] = 1; }
Note: See TracChangeset for help on using the changeset viewer.