Changeset 548

Ignore:
Timestamp:
May 24, 2007 1:14:05 AM (12 years ago)
Message:

fixed problem in new convexification cuts for expr{Sin,Cos}. Applying obbt more than once, but obbt disabled due to a bad result in ex2_1_7

Location:
branches/Couenne/Couenne
Files:
11 edited

Unmodified
Removed
• branches/Couenne/Couenne/TODO

 r547 - avoid very large coefficients - Bilinear cuts - trisection - recognition of quadratic forms - q.f. partitioning into PD + nonconvex - (reverse Polish notation)-based evaluation for efficiency
• branches/Couenne/Couenne/src/convex/CouenneCutGenerator.cpp

 r543 now = CoinCpuTime (); //problem_ -> print (std::cout); //printf ("======================================\n"); //  problem_ -> print (std::cout); //  printf ("======================================\n"); problem_ -> standardize (); septime_ = now; //problem_ -> print (std::cout); //  printf ("======================================\n"); problem_ -> writeMod ("extended-aw.mod", true); problem_ -> writeMod ("extended-pb.mod", false); //  problem_ -> print (std::cout); //problem_ -> writeMod ("extended-aw.mod", true); //problem_ -> writeMod ("extended-pb.mod", false); }
• branches/Couenne/Couenne/src/convex/boundTightening.cpp

 r539 #include #include "BonAuxInfos.hpp" // max # bound tightening iterations #define MAX_BT_ITER 10 } //////////////////////// Bound tightening /////////////////////////////////// //////////////////////// Bound propagation and implied bounds //////////////////// int   ntightened = 0, } #define MAX_BT_ITER 10 } while (ntightened || nbwtightened && (niter++ < MAX_BT_ITER)); // need to check if EITHER procedures gave results, as expression // structure is not a tree any longer. } while (((ntightened > 0) || (nbwtightened > 0)) && (niter++ < MAX_BT_ITER)); // continue if EITHER procedures gave (positive) results, as // expression structure is not a tree. return true;
• branches/Couenne/Couenne/src/convex/generateCuts.cpp

 r547 #define LARGE_BOUND 9.999e12 // minimum #bound changed in obbt to generate further cuts #define THRES_NBD_CHANGED 1 // depth of the BB tree until which obbt is applied at all nodes #define COU_OBBT_CUTOFF_LEVEL 3 // maximum number of obbt iterations #define MAX_OBBT_ITER 4 // translate changed bound sparse array into a dense one 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);*/ int nInitCuts = cs.sizeRowCuts (); //  printf (":::::::::::::::::::::::: level = %d, pass = %d, intree=%d\n Bounds:\n", //  info.level, info.pass, info.inTree); Bonmin::BabInfo * babInfo = dynamic_cast (si.getAuxiliaryInfo ()); } #define COU_OBBT_CUTOFF_LEVEL 3 // change tightened bounds through OsiCuts if (nchanged) //#define USE_OBBT #ifdef USE_OBBT if ((info.pass == 0) && !firstcall_ && 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 #define THRES_NBD_CHANGED 1 int nImprov = obbt (si, cs, chg_bds, babInfo); int nImprov, nIter = 0; bool repeat = true; while (repeat && (nIter++ < MAX_OBBT_ITER) && ((nImprov = obbt (si, cs, chg_bds, babInfo)) > 0)) if (nImprov >= THRES_NBD_CHANGED) { /// OBBT has given good results, add convexification with /// improved bounds sparse2dense (ncols, chg_bds, changed, nchanged); genColCuts (si, cs, nchanged, changed); int nCurCuts = cs.sizeRowCuts (); //      genRowCuts (si, cs, nchanged, changed); repeat = nCurCuts < cs.sizeRowCuts (); // reapply only if new cuts available } 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 ntotalcuts_ = nrootcuts_ = cs.sizeRowCuts (); } else ntotalcuts_ += cs.sizeRowCuts (); else ntotalcuts_ += (cs.sizeRowCuts () - nInitCuts); septime_ += CoinCpuTime () - now; }
• branches/Couenne/Couenne/src/convex/obbt.cpp

 r547 #include #define OBBT_EPS 1e-3 /// reoptimize and change bound of a variable if needed bool updateBound (OsiSolverInterface *csi, /// interface to use as a solver int sense,               /// 1: minimize, -1: maximize CouNumber &bound) {      /// bound to be updated CouNumber &bound,        /// bound to be updated bool isint) {            /// is this variable integer double opt; csi -> setObjSense  (sense); // MINIMIZE csi -> setObjSense (sense); csi -> resolve (); if (csi -> isProvenOptimal () && ((sense > 0) && ((opt = csi -> getObjValue ()) > bound + COUENNE_EPS)) || ((sense < 0) && ((opt = csi -> getObjValue ()) < bound - COUENNE_EPS))) { if (csi -> isProvenOptimal ()) { bound = opt; double opt = csi -> getObjValue (); if      ((sense>0) && (opt > bound+OBBT_EPS)) bound = (isint ? ceil (opt) : (opt-OBBT_EPS)); else if ((sense<0) && (opt < bound-OBBT_EPS)) bound = (isint ? floor(opt) : (opt+OBBT_EPS)); else return false; return true; } else return false; } /// Optimality based bound tightening char *chg_bds, Bonmin::BabInfo * babInfo) const { int nImprov = 0, ncols   = si.getNumCols (), objind  = problem_ -> Obj (0) -> Body () -> Index (); int nImprov = 0, ncols = si.getNumCols (); double *objcoe = (double *) malloc (ncols * sizeof (double)); // for all (original+auxiliary) variables x_i, for (int i=0; i setObjective (objcoe); CouNumber opt; bool chg = false; int nOrig = problem_ -> nVars (); bool isInt = (i < nOrig) ? (problem_ -> Var (i)       -> isInteger ()) : (problem_ -> Aux (i-nOrig) -> isInteger ()); // minimize and then maximize x_i on si. objcoe [i] = 1; csi -> setObjective (objcoe); chg = updateBound (csi,  1, problem_ -> Lb (i)); chg = updateBound (csi, -1, problem_ -> Ub (i)) || chg; // minimize and then maximize x_i on si. if (chg) { CouNumber l0 = problem_ -> Lb (i); CouNumber u0 = problem_ -> Ub (i); if (!(boundTightening (si, cs, chg_bds, babInfo))) return -1; // return value to signal infeasibility if (updateBound (csi,  1, problem_ -> Lb (i), isInt)) { csi -> setColLower (i, problem_ -> Lb (i)); chg = true; } if (updateBound (csi, -1, problem_ -> Ub (i), isInt)) { csi -> setColUpper (i, problem_ -> Ub (i)); chg = true; } chg_bds [i] = 1; nImprov++; if (chg) { /* printf ("%d: [%g,%g] --> [%g,%g]\n", i, l0, u0, problem_ -> Lb (i), problem_ -> Ub (i)); */ if (!(boundTightening (si, cs, chg_bds, babInfo))) return -1; // tell caller this is infeasible chg_bds [i] = 1; nImprov++; } // restore null obj fun objcoe [i] = 0; } // restore null obj fun objcoe [i] = 0; } delete csi;
• branches/Couenne/Couenne/src/convex/operators/conv-exprPow.cpp

 r523 || (u < - COUENNE_EPS)) && (l > - powThres) &&    // and are finite (u <   powThres)) (u <   powThres) && (fabs (l+u) > COUENNE_EPS)) // bounds are not opposite cg -> addSegment (cs, w_ind, x_ind, l, safe_pow (l, k), u, safe_pow (u, k), -sign);
• branches/Couenne/Couenne/src/convex/operators/conv-exprSinCos.cpp

 r534 #include //#define NEW_TRIG #define NEW_TRIG /// convex cuts for sine or cosine rx0  = modulo (x0 + displacement, 2*M_PI), rx1  = rx0 + x1 - x0, base = x0 + displacement - rx0, base = x0 - rx0, sinrx0 = sin (rx0), zero; int up   = (modulo (rx0, 2*M_PI) < M_PI) ? +1 : -1, left = (x0 < x1)                     ? +1 : -1; //    up   = (modulo (rx0, 2*M_PI) < M_PI) ? +1 : -1, up   = (rx0 < M_PI) ? +1 : -1, left = (x0  < x1)   ? +1 : -1; // starting point of the current bay zero = (up>0) ? 0. : M_PI;
• branches/Couenne/Couenne/src/expression/operators/exprBCos.h

 r543 inline CouNumber exprLBCos::operator () () { register CouNumber l = (*(arglist_ [0])) (); register CouNumber u = (*(arglist_ [1])) (); register CouNumber l = (*(arglist_ [0])) (), u = (*(arglist_ [1])) (); if ((u - l > 2 * M_PI) ||      // 1) interval spans whole cycle (floor (l/2/M_PI - 0.5) < // 2) there is a 3/2 pi + 2k pi in between floor (u/2/M_PI - 0.5))) CouNumber pi2 = 2 * M_PI; if ((u - l > pi2) ||       // 1) interval spans whole cycle (floor (l/pi2 - 0.5) < // 2) there is a pi + 2k pi in between floor (u/pi2 - 0.5))) return -1; inline CouNumber exprUBCos::operator () () { register CouNumber l = (*(arglist_ [0])) (); register CouNumber u = (*(arglist_ [1])) (); register CouNumber l = (*(arglist_ [0])) (), u = (*(arglist_ [1])) (); if ((u - l > 2 * M_PI) || // 1) interval spans whole cycle (floor (l/2/M_PI) <   // 2) there is a 3/2 pi + 2k pi in between floor (u/2/M_PI))) CouNumber pi2 = 2 * M_PI; if ((u - l > pi2) || // 1) interval spans whole cycle (floor (l/pi2) < // 2) there is a 3/2 pi + 2k pi in between floor (u/pi2))) return 1;
• branches/Couenne/Couenne/src/expression/operators/exprBSin.h

 r543 inline CouNumber exprLBSin::operator () () { register CouNumber l = (*(arglist_ [0])) (); register CouNumber u = (*(arglist_ [1])) (); register CouNumber l = (*(arglist_ [0])) (), u = (*(arglist_ [1])) (); if ((u - l > 2 * M_PI) ||      // 1) interval spans whole cycle (floor (l/2/M_PI - 0.75) < // 2) there is a 3/2 pi + 2k pi in between floor (u/2/M_PI - 0.75))) return -1; CouNumber pi2 = 2 * M_PI; if ((u - l > pi2) ||        // 1) interval spans whole cycle (floor (l/pi2 - 0.75) < // 2) there is a 3/2 pi + 2k pi in between floor (u/pi2 - 0.75))) return -1.; return mymin (sin (l), sin (u)); inline CouNumber exprUBSin::operator () () { register CouNumber l = (*(arglist_ [0])) (); register CouNumber u = (*(arglist_ [1])) (); register CouNumber l = (*(arglist_ [0])) (), u = (*(arglist_ [1])) (); if ((u - l > 2 * M_PI) ||      // 1) interval spans whole cycle (floor (l/2/M_PI - 0.25) < // 2) there is a 3/2 pi + 2k pi in between floor (u/2/M_PI - 0.25))) return -1; CouNumber pi2 = 2 * M_PI; if ((u - l > pi2) ||        // 1) interval spans whole cycle (floor (l/pi2 - 0.25) < // 2) there is a pi/2 + 2k pi in between floor (u/pi2 - 0.25))) return 1.; return mymax (sin (l), sin (u));
• branches/Couenne/Couenne/src/expression/operators/exprCos.cpp

 r543 // compute bounds of sin x given bounds of x void exprCos::getBounds (expression *&lb, expression *&ub) { lb = new exprConst (-1); ub = new exprConst (1); return; //  lb = new exprConst (-1); //  ub = new exprConst (1); //  return; // TODO
• branches/Couenne/Couenne/src/expression/operators/exprSin.cpp

 r543 void exprSin::getBounds (expression *&lb, expression *&ub) { lb = new exprConst (-1); ub = new exprConst (1); return; //  lb = new exprConst (-1); //  ub = new exprConst (1); //  return; // TODO: lb = new exprLBSin (xl, xu); ub = new exprLBSin (new exprClone (xl), new exprClone (xu)); ub = new exprUBSin (new exprClone (xl), new exprClone (xu)); }
Note: See TracChangeset for help on using the changeset viewer.