/home/coin/SVN-release/OS-2.0.1/Couenne/src/problem/CouenneSolverInterface.cpp

Go to the documentation of this file.
00001 /* $Id$
00002  *
00003  * Name:    CouenneSolverInterface.cpp
00004  * Authors: Pietro Belotti, Carnegie Mellon University
00005  *          Andreas Waechter, IBM Corp.
00006  * Purpose: Implementation of the OsiSolverInterface::resolve () method 
00007  *
00008  * (C) Carnegie-Mellon University, 2006-09.
00009  * This file is licensed under the Common Public License (CPL)
00010  */
00011 
00012 #include "OsiClpSolverInterface.hpp"
00013 #include "CouenneProblem.hpp"
00014 #include "CouenneSolverInterface.hpp"
00015 #include "CglTreeInfo.hpp"
00016 
00018 CouenneSolverInterface::CouenneSolverInterface (CouenneCutGenerator *cg /*= NULL*/):
00019 
00020   OsiClpSolverInterface(),
00021   cutgen_ (cg),
00022   knowInfeasible_(false),
00023   knowOptimal_(false),
00024   knowDualInfeasible_(false),
00025   doingResolve_ (true) {
00026 
00027   // prevents from running OsiClpSolverInterface::tightenBounds()
00028   if (cutgen_ && !(cutgen_ -> enableLpImpliedBounds ()))
00029     specialOptions_ = specialOptions_ | 262144; 
00030 }
00031 
00033 CouenneSolverInterface::CouenneSolverInterface (const CouenneSolverInterface &src):
00034 
00035   OsiSolverInterface    (src),
00036   OsiClpSolverInterface (src),
00037   cutgen_               (src.cutgen_),
00038   knowInfeasible_       (src.knowInfeasible_),
00039   knowOptimal_          (src.knowOptimal_),
00040   knowDualInfeasible_   (src.knowDualInfeasible_),
00041   doingResolve_         (src.doingResolve_) {}
00042 
00044 CouenneSolverInterface::~CouenneSolverInterface () {
00045   //  if (cutgen_)
00046   //    delete cutgen_;
00047 }
00048 
00049 
00051 void CouenneSolverInterface::initialSolve () {
00052   /*printf ("------------------------------------- INITIAL SOLVE\n");
00053   for (int i=0; i<getNumCols(); i++)
00054     printf ("%4d. %20.5g [%20.5g %20.5g]\n", 
00055             i, getColSolution () [i],
00056             getColLower () [i],
00057             getColUpper () [i]);
00058 
00059             cutgen_ -> Problem () -> print ();*/
00060 
00061   knowInfeasible_     = 
00062   knowOptimal_        = 
00063   knowDualInfeasible_ = false;
00064 
00065   OsiClpSolverInterface::initialSolve ();
00066   //writeLp ("initialLP");
00067 
00068   if (getObjValue () <= - Couenne_large_bound)
00069     knowDualInfeasible_ = true;
00070 
00071   // some originals may be unused due to their zero multiplicity (that
00072   // happens when they are duplicates), restore their value
00073   if (cutgen_ -> Problem () -> nUnusedOriginals () > 0) {
00074     CouNumber *x = new CouNumber [getNumCols ()];
00075     CoinCopyN (getColSolution (), getNumCols (), x);
00076     cutgen_ -> Problem () -> restoreUnusedOriginals (x);
00077     setColSolution (x);
00078     delete [] x;
00079   }
00080 
00081   /*
00082     printf ("------------------------------------- INITSOLV\n");
00083   for (int i=0; i<cutgen_ -> Problem () -> nOrigVars (); i++) 
00084     //if (cutgen_ -> Problem () -> Var (i) -> Multiplicity () <= 0) 
00085       {
00086       printf ("%4d. %20.5g [%20.5g %20.5g]   ", 
00087               i, getColSolution () [i],
00088               getColLower () [i],
00089               getColUpper () [i]);
00090       cutgen_ -> Problem () -> Var (i) -> print ();
00091       printf ("\n");
00092     }
00093   */
00094 }
00095 
00096 bool CouenneSolverInterface::isProvenPrimalInfeasible() const {
00097   return knowInfeasible_ || OsiClpSolverInterface::isProvenPrimalInfeasible();
00098 }
00099 
00100 bool CouenneSolverInterface::isProvenOptimal() const {
00101   return knowOptimal_ || OsiClpSolverInterface::isProvenOptimal();
00102 }
00103 
00104 bool CouenneSolverInterface::isProvenDualInfeasible() const {
00105   return knowDualInfeasible_ || OsiClpSolverInterface::isProvenDualInfeasible();
00106 }
00107 
00109 void sparse2dense (int, t_chg_bounds *, int *&, int &);
00110 
00111 
00113 void CouenneSolverInterface::resolve () {
00114   /*printf ("------------------------------------- RESOLVE\n");
00115   for (int i=0; i<getNumCols(); i++) 
00116     printf ("%4d. %20.5g [%20.5g %20.5g]\n", 
00117             i, getColSolution () [i],
00118             getColLower () [i],
00119             getColUpper () [i]);*/
00120 
00121   // CUT THIS! Some about-to-be-resolved problems have variables with
00122   // lower +inf. That is, between CbcModel::initialSolve() and
00123   // CbcModel::resolve(). I couldn't spot where in Couenne this
00124   // happens.
00125 
00127   /*const double 
00128     *lb = getColLower (),
00129     *ub = getColUpper ();
00130 
00131   for (int i=getNumCols(); i--;) {
00132     if (lb [i] >  COUENNE_INFINITY)
00133       setColLower (i, cutgen_ -> Problem () -> Lb (i));
00134     //setColLower (i, -COIN_DBL_MAX);//cutgen_ -> Problem () -> Lb (i));
00135     if (ub [i] < -COUENNE_INFINITY)
00136       setColUpper (i, cutgen_ -> Problem () -> Ub (i));
00137     //setColUpper (i,  COIN_DBL_MAX);//cutgen_ -> Problem () -> Ub (i));
00138     }*/
00140 
00141   static int count = -1;
00142   char filename [30];
00143 
00144   // save problem to be loaded later
00145   if (cutgen_ && (cutgen_ -> check_lp ())) {
00146     count++;
00147     sprintf (filename, "resolve_%d", count);
00148     writeMps (filename);
00149   }
00150 
00151   knowInfeasible_     = 
00152   knowOptimal_        = 
00153   knowDualInfeasible_ = false;
00154 
00155   const CoinWarmStart *ws = NULL;
00156 
00157   if (cutgen_ && (cutgen_ -> check_lp ()))
00158     ws = getWarmStart ();
00159 
00160   //deleteScaleFactors ();
00161 
00162   // re-solve problem
00163   OsiClpSolverInterface::resolve ();
00164 
00165   if (getObjValue () <= - Couenne_large_bound)
00166     knowDualInfeasible_ = true;
00167 
00168   CouNumber objval = getObjValue (),
00169     curCutoff = cutgen_ -> Problem () -> getCutOff ();
00170 
00171   // check if resolve found new integer solution
00172   if (doingResolve () &&                 // this is not called from strong branching
00173       isProvenOptimal () &&
00174       (objval < curCutoff - COUENNE_EPS) &&
00175       (cutgen_ -> Problem () -> checkNLP (getColSolution (), objval, true)) &&
00176       (objval < curCutoff - COUENNE_EPS) && // check again as it may have changed
00177       (objval > -COUENNE_INFINITY/2)) {    // check if it makes sense
00178 
00179     // also save the solution so that cbcModel::setBestSolution saves it too
00180 
00181     //printf ("new cutoff from CSI: %g\n", objval);
00182     cutgen_ -> Problem () -> setCutOff (objval);
00183   }
00184 
00185   // some originals may be unused due to their zero multiplicity (that
00186   // happens when they are duplicates), restore their value
00187   if (cutgen_ -> Problem () -> nUnusedOriginals () > 0) {
00188     CouNumber *x = new CouNumber [getNumCols ()];
00189     CoinCopyN (getColSolution (), getNumCols (), x);
00190     cutgen_ -> Problem () -> restoreUnusedOriginals (x);
00191     setColSolution (x);
00192     delete [] x;
00193   }
00194 
00195   //cutgen_ -> Problem () -> restoreUnusedOriginals (this);
00196 
00197   // check LP independently
00198   if (cutgen_ && (cutgen_ -> check_lp ())) {
00199 
00200     OsiSolverInterface
00201       *nsi = new OsiClpSolverInterface,
00202       *csi = clone ();
00203 
00204     sprintf (filename, "resolve_%d.mps", count);
00205     nsi -> readMps (filename);
00206 
00207     nsi -> messageHandler () -> setLogLevel (0);
00208     nsi -> setWarmStart (ws);
00209 
00210     nsi -> initialSolve ();
00211 
00212     if ((nsi -> isProvenOptimal () && isProvenOptimal ()) ||
00213         !(nsi -> isProvenOptimal ()) && !isProvenOptimal ()) {
00214 
00215       if (nsi -> isProvenOptimal () &&
00216           (fabs (nsi -> getObjValue () - getObjValue ()) / 
00217            (1. + fabs (nsi -> getObjValue ()) + fabs (getObjValue ())) > 1e-2))
00218 
00219         printf ("Warning: discrepancy between saved %g and current %g [%g], file %s\n", 
00220                 nsi -> getObjValue (),  getObjValue (),
00221                 nsi -> getObjValue () - getObjValue (),
00222                 filename);
00223     }
00224 
00225     csi -> messageHandler () -> setLogLevel (0);
00226     csi -> setWarmStart (ws);
00227 
00228     csi -> initialSolve ();
00229 
00230     if ((csi -> isProvenOptimal () && isProvenOptimal ()) ||
00231         !(csi -> isProvenOptimal ()) && !isProvenOptimal ()) {
00232 
00233       if (csi -> isProvenOptimal () &&
00234           (fabs (csi -> getObjValue () - getObjValue ()) / 
00235            (1. + fabs (csi -> getObjValue ()) + fabs (getObjValue ())) > 1e-2))
00236 
00237         printf ("Warning: discrepancy between cloned %g and current %g [%g]\n", 
00238                 csi -> getObjValue (),  getObjValue (),
00239                 csi -> getObjValue () - getObjValue ());
00240     }
00241 
00242     delete nsi;
00243     delete csi;
00244     
00245     delete ws;
00246 
00247     //else printf ("Warning: discrepancy between statuses %s -- %s feasible\n", 
00248     //filename, isProvenOptimal () ? "current" : "saved");
00249   }
00250 }
00251 
00252 
00254 void CouenneSolverInterface::markHotStart () {
00255   //printf(">>>> markHotStart\n");
00256   // Using OsiClpSolverInterface doesn't work yet...
00257   OsiSolverInterface::markHotStart ();
00258 }
00259 
00260 
00262 void CouenneSolverInterface::unmarkHotStart() {
00263   //printf("<<<< unmarkHotStart\n");
00264   OsiSolverInterface::unmarkHotStart();
00265 }
00266 
00267 
00268 
00270 void CouenneSolverInterface::solveFromHotStart() {
00271 
00272   //OsiClpSolverInterface::solveFromHotStart ();
00273 
00274   //#if 0
00275   knowInfeasible_     = 
00276   knowOptimal_        = 
00277   knowDualInfeasible_ = false;
00278 
00279   /*
00280   const int ncols = cutgen_ -> Problem () -> nVars ();
00281 
00282   cutgen_ -> Problem () -> domain () -> push
00283     (cutgen_ -> Problem () -> nVars (),
00284      getColSolution (),
00285      getColLower    (),
00286      getColUpper    ());
00287 
00288   // This vector contains variables whose bounds have changed due to
00289   // branching, reduced cost fixing, or bound tightening below. To be
00290   // used with malloc/realloc/free
00291 
00292   t_chg_bounds *chg_bds = new t_chg_bounds [ncols];
00293 
00294   OsiCuts cs;
00295 
00296   Bonmin::BabInfo *babInfo = dynamic_cast <Bonmin::BabInfo *> (getAuxiliaryInfo ());
00297 
00298   if (cutgen_ -> Problem () -> doFBBT () && 
00299       (!(cutgen_ -> Problem () -> boundTightening (chg_bds, babInfo)))) {
00300 
00301 #ifdef DEBUG
00302     printf ("#### BT says infeasible before re-solve\n");
00303 #endif
00304     knowInfeasible_ = true;
00305     cutgen_ -> Problem () -> domain () -> pop ();
00306     return;
00307   }
00308 
00309   int *changed = NULL, nchanged;
00310   sparse2dense (ncols, chg_bds, changed, nchanged);
00311 
00312   // change tightened bounds through OsiCuts
00313   if (nchanged)
00314     cutgen_ -> genColCuts (*this, cs, nchanged, changed);
00315 
00316   const int nRowsBeforeRowCuts = getNumRows();
00317   //printf("NumRows before getRowCuts = %d\n", getNumRows());
00318   cutgen_ -> genRowCuts (*this, cs, nchanged, changed, //CglTreeInfo(),
00319                          chg_bds, false);
00320 
00321   // Now go through the list of cuts and apply the column cuts
00322   // directly as changes on bounds
00323   while(cs.sizeColCuts()) {
00324     const OsiColCut& ccut = cs.colCut(0);
00325     const CoinPackedVector& lbs = ccut.lbs();
00326     int nele = lbs.getNumElements();
00327     const int* idxs = lbs.getIndices();
00328     const double* eles = lbs.getElements();
00329     const double* bnds = getColLower();
00330     for (int i=0; i<nele; i++) {
00331       if (bnds[*idxs] < *eles) {
00332         //printf ("setcolLower %d %g\n", *idxs, *eles);
00333         setColLower(*idxs,*eles);
00334       }
00335       idxs++;
00336       eles++;
00337     }
00338     const CoinPackedVector& ubs = ccut.ubs();
00339     nele = ubs.getNumElements();
00340     idxs = ubs.getIndices();
00341     eles = ubs.getElements();
00342     bnds = getColUpper();
00343     for (int i=0; i<nele; i++) {
00344       if (bnds[*idxs] > *eles) {
00345         //printf ("setcolUpper %d %g\n", *idxs, *eles);
00346         setColUpper(*idxs,*eles);
00347       }
00348       idxs++;
00349       eles++;
00350     }
00351     cs.eraseColCut(0); 
00352   }
00353 
00354   applyCuts (cs);
00355 
00356   const int nRowsAfterRowCuts = getNumRows();
00357   //printf("NumRows after applyCuts = %d\n", getNumRows());
00358   */
00359 
00360   resolve();
00361 
00362   if (getObjValue () <= - Couenne_large_bound)
00363     knowDualInfeasible_ = true;
00364 
00365   // some originals may be unused due to their zero multiplicity (that
00366   // happens when they are duplicates), restore their value
00367   if (cutgen_ -> Problem () -> nUnusedOriginals () > 0) {
00368     CouNumber *x = new CouNumber [getNumCols ()];
00369     CoinCopyN (getColSolution (), getNumCols (), x);
00370     cutgen_ -> Problem () -> restoreUnusedOriginals (x);
00371     setColSolution (x);
00372     delete [] x;
00373   }
00374 
00375   if (isProvenPrimalInfeasible ()) knowInfeasible_     = true;
00376   if (isProvenOptimal          ()) knowOptimal_        = true;
00377   if (isProvenDualInfeasible   ()) knowDualInfeasible_ = true;
00378 
00379   //printf("obj value = %e\n",getObjValue());
00380 
00381   // now undo the row cuts
00382   /*
00383   int nrowsdel = nRowsAfterRowCuts-nRowsBeforeRowCuts;
00384   int* rowsdel = new int[nrowsdel];
00385   for(int i=0; i<nrowsdel; i++) {
00386     rowsdel[i] = nRowsBeforeRowCuts+i;
00387   }
00388   deleteRows(nrowsdel, rowsdel);
00389   delete [] rowsdel;
00390   //printf("NumRows after deleting = %d\n", getNumRows());
00391 
00392   cutgen_ -> Problem () -> domain () -> pop ();
00393   */
00394   //#endif
00395 }

Generated on Thu Oct 8 03:02:57 2009 by  doxygen 1.4.7