Changeset 545

Ignore:
Timestamp:
May 22, 2007 12:51:04 AM (12 years ago)
Message:

Location:
branches/Couenne/Couenne
Files:
11 edited

Unmodified
Removed
• branches/Couenne/Couenne/TODO

 r539 - Bilinear cuts - trisection - extended formulation - variable lhs/rhs of bounds containing expression defining aux vars - OBBT - cut currValue_ from expressions - documentation
• branches/Couenne/Couenne/src/Makefile.am

 r537 expression/operators/exprMinMax.cpp \ expression/operators/exprGroup.cpp \ expression/operators/exprQuad.cpp \ expression/operators/impliedBounds-exprSum.cpp \ expression/operators/impliedBounds-exprDiv.cpp \ convex/boundTightening.cpp \ convex/genColCuts.cpp \ convex/genRowCuts.cpp \ convex/obbt.cpp \ problem/problem.cpp \ problem/problemIO.cpp \ expression/operators/exprSub.h \ expression/operators/exprGroup.h \ expression/operators/exprQuad.h \ expression/exprConst.h \ expression/exprIVar.h \

• branches/Couenne/Couenne/src/convex/CouenneCutGenerator.h

 r534 bool = false) const;  /// is it a global cut? No, by default /// add general linear envelope to convex function, given its /// Add general linear envelope to convex function, given its /// variables' indices, the (univariate) function and its first /// derivative bool = false) const; /// add half-plane through (x1,y1) and (x2,y2) -- resp. 4th, 5th, /// Add half-plane through (x1,y1) and (x2,y2) -- resp. 4th, 5th, /// 6th, and 7th argument int addSegment (OsiCuts &, int, int, virtual bool doLocalSearch () const {return 0;} /// method to set the Bab pointer /// Method to set the Bab pointer void setBabPtr (Bonmin::Bab *p) {BabPtr_ = p;} /// get statistics /// Get statistics void getStats (int &nrc, int &ntc, double &st) { nrc = nrootcuts_; } /// allow to get and set the infeasNode_ flag (used only in generateCuts()) /// Allow to get and set the infeasNode_ flag (used only in generateCuts()) bool &infeasNode () const {return infeasNode_;} /// generate OsiRowCuts for current convexification void genRowCuts (const OsiSolverInterface &, OsiCuts &cs, int, int *) const; /// generate OsiColCuts for improved (implied and propagated) bounds bool boundTightening (const OsiSolverInterface &, OsiCuts &, char *, Bonmin::BabInfo * = NULL) const; /// Optimality Based Bound Tightening int obbt (const OsiSolverInterface &, OsiCuts &, char *, Bonmin::BabInfo *) const; };
• branches/Couenne/Couenne/src/convex/generateCuts.cpp

 r540 #include "BonAuxInfos.hpp" // fictitious bound for initial unbounded lp relaxations #define LARGE_BOUND 9.999e12 // translate changed bound sparse array into a dense one void sparse2dense (int ncols, char *chg_bds, int *&changed, int &nchanged) { // convert sparse chg_bds in something handier changed  = (int *) malloc (ncols * sizeof (int)); nchanged = 0; for (register int i=ncols, j=0; i--; j++) if (*chg_bds++) { *changed++ = j; nchanged++; } changed = (int *) realloc (changed - nchanged, nchanged * sizeof (int)); } /// a convexifier cut generator OsiCuts &cs, const CglTreeInfo info) const { //  int nInitCuts = cs.sizeRowCuts (); /*printf (":::::::::::::::::::::::: level = %d, pass = %d, intree=%d\n Bounds:\n", info.level, info.pass, info.inTree);*/ //  for (int i=0; i < si. getNumCols(); i++) //      printf (" %3d [%.3e,%.3e]\n", i, si. getColLower () [i], //      si. getColUpper () [i]); Bonmin::BabInfo * babInfo = dynamic_cast (si.getAuxiliaryInfo ()); babInfo -> setFeasibleNode (); double now = CoinCpuTime (); if (firstcall_) { printf ("Couenne:"); fflush (stdout); } int ncols = problem_ -> nVars () + problem_ -> nAuxs (); double now   = CoinCpuTime (); int    ncols = problem_ -> nVars () + problem_ -> nAuxs (); // This vector contains variables whose bounds have changed due to } int *changed, nchanged; int *changed = NULL, nchanged; //////////////////////// Bound tightening /////////////////////////////////////////// //  for (int i=0; i nAuxs () + problem_ -> nVars (); i++ ) //    printf ("%d: [%.4f %.4f]\n", i, problem_ -> Lb (i), problem_ -> Ub (i)); if (! boundTightening (si, cs, chg_bds, babInfo)) { //    printf ("INFEASIBLE\n"); //    for (int i=0; i nAuxs () + problem_ -> nVars (); i++ ) //      printf ("%d: [%.4f %.4f]\n", i, problem_ -> Lb (i), problem_ -> Ub (i)); if ((info.pass == 0)  // do bound tightening only at first pass of cutting plane && (! boundTightening (si, cs, chg_bds, babInfo))) goto end_genCuts; } //  for (int i=0; i nAuxs () + problem_ -> nVars (); i++ ) //    printf ("%d: [%.4f %.4f]\n", i, problem_ -> Lb (i), problem_ -> Ub (i)); //////////////////////// GENERATE CONVEXIFICATION CUTS ////////////////////////////// // convert sparse chg_bds in something handier changed  = (int *) malloc (ncols * sizeof (int)); nchanged = 0; for (register int i=ncols, j=0; i--; j++) if (*chg_bds++) { *changed++ = j; nchanged++; } delete [] (chg_bds -= ncols); changed = (int *) realloc (changed - nchanged, nchanged * sizeof (int)); // For each auxiliary variable, create cut (or set of cuts) violated // by current point and add it to cs if (firstcall_) for (int i=0, j = problem_ -> nAuxs (); j--; i++) { if (problem_ -> Aux (i) -> Multiplicity () > 0) problem_ -> Aux (i) -> generateCuts (si, cs, this); } else { // chg_bds contains the indices of the variables whose bounds // have changes (a -1 follows the last element) for (int i=0, j = problem_ -> nAuxs (); j--; i++) { // TODO: check if list contains all and only aux's to cut /*expression * image = problem_ -> Aux (i) -> Image (); if (   (image -> Linearity () > LINEAR)          // if linear, no need to cut twice && (image -> dependsOn (changed, nchanged))  // if expression does not depend on )*/                                            // changed variables, do not cut if (problem_ -> Aux (i) -> Multiplicity () > 0) problem_ -> Aux (i) -> generateCuts (si, cs, this); } } sparse2dense (ncols, chg_bds, changed, nchanged); ////////////////////// genRowCuts (si, cs, nchanged, changed); ////////////////////// if (firstcall_) { } #define COU_OBBT_CUTOFF_LEVEL 3 // change tightened bounds through OsiCuts if (nchanged) genColCuts (si, cs, nchanged, changed); #ifdef USE_OBBT if ((info.pass == 0) && !firstcall_ && (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 #define THRES_NBD_CHANGED 1 int nImprov = obbt (si, cs, chg_bds, babInfo); if (nImprov < 0) goto end_genCuts; if (nImprov >= THRES_NBD_CHANGED) { //      if (! (boundTightening (si, cs, chg_bds, babInfo))) //        goto end_genCuts; /// OBBT has given good results, add convexification with /// improved bounds sparse2dense (ncols, chg_bds, changed, nchanged); genColCuts (si, cs, nchanged, changed); genRowCuts (si, cs, nchanged, changed); } } #endif delete [] chg_bds; // clean up free (changed); if (firstcall_) { if (cs.sizeRowCuts ()) printf (" %d initial cuts", cs.sizeRowCuts ()); printf ("\n"); } if ((firstcall_) && cs.sizeRowCuts ()) printf ("Couenne: %d initial cuts\n", cs.sizeRowCuts ()); end_genCuts:
• branches/Couenne/Couenne/src/expression/CouenneTypes.h

 r534 /*COU_EXPRIVAR, */ COU_EXPROP,     /***** n-ary operators *******************/ COU_EXPRSUB,  COU_EXPRSUM, COU_EXPRGROUP, COU_EXPRSUB,  COU_EXPRSUM, COU_EXPRGROUP, COU_EXPRQUAD, COU_EXPRMIN,  COU_EXPRMUL, COU_EXPRPOW, COU_EXPRMAX, COU_EXPRDIV, /*COU_EXPRBDIV,  COU_EXPRBMUL,*/
• branches/Couenne/Couenne/src/expression/expression.h

 r543 static CouNumber Lbound   (int i) {return lbounds_   [i];} static CouNumber Ubound   (int i) {return ubounds_   [i];} static CouNumber Variable (int i) {return variables_ [i];} // allow to set it static CouNumber Variable (int i) {return variables_ [i];} /// return arrays static CouNumber *Lbounds   () {return lbounds_;} static CouNumber *Ubounds   () {return ubounds_;} static CouNumber *Variables () {return variables_;} /// Constructor, destructor
• branches/Couenne/Couenne/src/expression/operators/exprGroup.h

 r543 inline CouNumber exprGroup::operator () () { register CouNumber  ret = c0_ + exprSum::operator () (), *coe = coeff_; register CouNumber ret  = c0_ + exprSum::operator () (), *coe  = coeff_, *vars = expression::Variables (); for (register int *ind = index_; *ind >= 0;) ret += *coe++ * expression::Variable (*ind++); ret += *coe++ * vars [*ind++]; return (currValue_ = ret);