/home/coin/SVN-release/OS-2.2.0/Couenne/src/bound_tightening/obbt.cpp

Go to the documentation of this file.
00001 /* $Id: obbt.cpp 218 2009-07-08 17:13:18Z pbelotti $
00002  *
00003  * Name:    obbt.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: Optimality-Based Bound Tightening
00006  *
00007  * (C) Carnegie-Mellon University, 2006. 
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CoinHelperFunctions.hpp"
00012 #include "CglCutGenerator.hpp"
00013 #include "CouenneCutGenerator.hpp"
00014 #include "CouenneProblem.hpp"
00015 #include "OsiClpSolverInterface.hpp"
00016 
00017 #define OBBT_EPS 1e-3
00018 #define MAX_OBBT_LP_ITERATION 100
00019 
00020 // minimum #bound changed in obbt to generate further cuts
00021 #define THRES_NBD_CHANGED 1
00022 
00023 // maximum number of obbt iterations
00024 #define MAX_OBBT_ITER 1
00025 
00026 // defined in generateCuts.cpp
00027 void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged);
00028 
00029 
00030 // OBBT for one sense (max/min) and one class of variables (orig/aux)
00031 int CouenneProblem::call_iter (OsiSolverInterface *csi, 
00032                                t_chg_bounds *chg_bds, 
00033                                const CoinWarmStart *warmstart, 
00034                                Bonmin::BabInfo *babInfo,
00035                                double *objcoe,
00036                                enum nodeType type,
00037                                int sense) const {
00038 
00039   int ncols   = csi -> getNumCols (),
00040       nimprov = 0;
00041 
00042   for (int ii=0; ii<ncols; ii++) {
00043 
00044     if (CoinCpuTime () > maxCpuTime_)
00045       break;
00046 
00047     int i = evalOrder (ii);
00048 
00049     if ((Var (i) -> Type () == type) &&
00050         (Var (i) -> Multiplicity () > 0)) {
00051 
00052       int ni = obbt_iter (csi, chg_bds, warmstart, babInfo, objcoe, sense, i);
00053 
00054       if (ni < 0) return ni;
00055       nimprov += ni;
00056     }
00057   }
00058 
00059   return nimprov;
00060 }
00061 
00062 
00064 
00065 int CouenneProblem::obbtInner (OsiSolverInterface *csi,
00066                                OsiCuts &cs,
00067                                t_chg_bounds *chg_bds,
00068                                Bonmin::BabInfo * babInfo) const {
00069 
00070   // set large bounds to infinity (as per suggestion by JJF)
00071 
00072   int ncols = csi -> getNumCols ();
00073   const double *lb = csi -> getColLower (),
00074                *ub = csi -> getColUpper ();
00075 
00076   double inf = csi -> getInfinity ();
00077 
00078   for (int i=ncols; i--;) {
00079     if (lb [i] < - COUENNE_INFINITY) csi -> setColLower (i, -inf);
00080     if (ub [i] >   COUENNE_INFINITY) csi -> setColUpper (i,  inf);
00081   }
00082 
00083   //  csi -> setHintParam (OsiDoDualInResolve, false);
00084 
00085   // setup cloned interface for later use
00086   csi -> setObjSense (1); // minimization
00087   csi -> setIntParam (OsiMaxNumIteration, MAX_OBBT_LP_ITERATION);
00088   csi -> applyCuts (cs);   // apply all (row+column) cuts to formulation
00089   csi -> initialSolve ();
00090 
00091   const CoinWarmStart *warmstart = csi -> getWarmStart ();
00092 
00093   // improve each bound
00094 
00095   double *objcoe = (double *) malloc (ncols * sizeof (double));
00096 
00097   // set obj function coefficients to zero
00098   for (int i=ncols; i--;)
00099     *objcoe++ = 0.;
00100   objcoe -= ncols;
00101 
00102   csi -> setObjective (objcoe);
00103   csi -> setObjSense (1);        // minimization
00104 
00105   int nimprov = 0;
00106  
00107   const int Infeasible = 1;
00108 
00109   try {
00110 
00111     int ni;
00112 
00113     if ((ni = call_iter (csi, chg_bds, warmstart, babInfo, objcoe, VAR,  1)) < 0) throw Infeasible;
00114     nimprov += ni;
00115 
00116     if ((ni = call_iter (csi, chg_bds, warmstart, babInfo, objcoe, VAR, -1)) < 0) throw Infeasible;
00117     nimprov += ni;
00118 
00119     if ((ni = call_iter (csi, chg_bds, warmstart, babInfo, objcoe, AUX,  1)) < 0) throw Infeasible;
00120     nimprov += ni;
00121 
00122     if ((ni = call_iter (csi, chg_bds, warmstart, babInfo, objcoe, AUX, -1)) < 0) throw Infeasible;
00123     nimprov += ni;
00124   }
00125 
00126   catch (int exception) {
00127 
00128     if (exception == Infeasible)
00129       nimprov = -1;
00130   }
00131 
00132   free (objcoe);
00133   delete warmstart;
00134 
00135   return (nimprov);
00136 }
00137 
00138 
00139 // Optimality based bound tightening -- main loop
00140 int CouenneProblem::obbt (const CouenneCutGenerator *cg,
00141                           const OsiSolverInterface &si,
00142                           OsiCuts &cs,
00143                           const CglTreeInfo &info,
00144                           Bonmin::BabInfo * babInfo,
00145                           t_chg_bounds *chg_bds) {
00146 
00147   // Do OBBT if:
00148 
00149   if (doOBBT_ &&                        // flag is checked, AND
00150       ((logObbtLev_ != 0) ||               // (parameter is nonzero OR
00151        (info.level == 0)) &&               //  we are at root node), AND
00152       (info.pass == 0) &&               // at first round of cuts, AND 
00153       ((logObbtLev_ < 0) ||               // (logObbtLev = -1, OR
00154        (info.level <= logObbtLev_) ||     //  depth is lower than COU_OBBT_CUTOFF_LEVEL, OR
00155                                           //  probability inversely proportional to the level)
00156        (CoinDrand48 () < pow (2., (double) logObbtLev_ - (info.level + 1))))) {
00157 
00158     jnlst_ -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING, "----- OBBT\n");
00159 
00160     // TODO: why check info.pass==0? Why not more than one pass? It
00161     // should be anyway checked that info.level be >= 0 as <0 means
00162     // first call at root node
00163 
00164     OsiSolverInterface *csi = si.clone (true);
00165     //dynamic_cast <CouenneSolverInterface<T> *> 
00166 
00167     OsiClpSolverInterface *clpcsi = dynamic_cast <OsiClpSolverInterface *> (csi);
00168 
00169     if (clpcsi)
00170       clpcsi -> setupForRepeatedUse ();
00171     //csi -> doingResolve () = false;
00172 
00173     //csi -> setHintParam (OsiDoDualInResolve, false);
00174 
00175     int nImprov, nIter = 0;
00176 
00177     bool notImproved = false;
00178 
00179     while (!notImproved && 
00180            (nIter++ < MAX_OBBT_ITER) &&
00181            ((nImprov = obbtInner (csi, cs, chg_bds, babInfo)) > 0) &&
00182            (CoinCpuTime () < maxCpuTime_)) {
00183 
00184       int nchanged, *changed = NULL;
00185 
00187       sparse2dense (nVars (), chg_bds, changed, nchanged);
00188       cg -> genColCuts (*csi, cs, nchanged, changed);
00189 
00190       if ((nIter < MAX_OBBT_ITER) && 
00191           (nImprov >= THRES_NBD_CHANGED)) {
00192 
00193         // only generate new row cuts if improvents are enough
00194         int nCurCuts = cs.sizeRowCuts ();
00195         cg -> genRowCuts (*csi, cs, nchanged, changed, chg_bds);
00196 
00197         if (nCurCuts == cs.sizeRowCuts ())
00198           notImproved = true; // repeat only if new cuts available
00199 
00200       } else notImproved = true;
00201 
00202       if (changed) 
00203         free (changed);
00204     }
00205 
00206     //csi -> doingResolve () = true;
00207 
00208     delete csi;
00209 
00210     if (nImprov < 0) {
00211       jnlst_->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING, "  Couenne: infeasible node after OBBT\n");
00212       return -1;
00213     }
00214   }
00215 
00216   return 0;
00217 }

Generated on Thu Aug 5 03:02:56 2010 by  doxygen 1.4.7