00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "CoinHelperFunctions.hpp"
00012 #include "CglCutGenerator.hpp"
00013 #include "CouenneCutGenerator.hpp"
00014 #include "CouenneProblem.hpp"
00015 #include "CouenneSolverInterface.hpp"
00016
00017 #define OBBT_EPS 1e-3
00018 #define MAX_OBBT_LP_ITERATION 100
00019
00020
00021 #define THRES_NBD_CHANGED 1
00022
00023
00024 #define MAX_OBBT_ITER 1
00025
00026
00027 void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged);
00028
00029
00030
00031 int CouenneProblem::call_iter (CouenneSolverInterface *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 (CouenneSolverInterface *csi,
00066 OsiCuts &cs,
00067 t_chg_bounds *chg_bds,
00068 Bonmin::BabInfo * babInfo) const {
00069
00070
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
00084
00085
00086 csi -> setObjSense (1);
00087 csi -> setIntParam (OsiMaxNumIteration, MAX_OBBT_LP_ITERATION);
00088 csi -> applyCuts (cs);
00089 csi -> initialSolve ();
00090
00091 const CoinWarmStart *warmstart = csi -> getWarmStart ();
00092
00093
00094
00095 double *objcoe = (double *) malloc (ncols * sizeof (double));
00096
00097
00098 for (int i=ncols; i--;)
00099 *objcoe++ = 0.;
00100 objcoe -= ncols;
00101
00102 csi -> setObjective (objcoe);
00103 csi -> setObjSense (1);
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
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
00148
00149 if (doOBBT_ &&
00150 ((logObbtLev_ != 0) ||
00151 (info.level == 0)) &&
00152 (info.pass == 0) &&
00153 ((logObbtLev_ < 0) ||
00154 (info.level <= logObbtLev_) ||
00155
00156 (CoinDrand48 () < pow (2., (double) logObbtLev_ - (info.level + 1))))) {
00157
00158 jnlst_ -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING, "----- OBBT\n");
00159
00160
00161
00162
00163
00164 CouenneSolverInterface *csi = dynamic_cast <CouenneSolverInterface *> (si.clone (true));
00165
00166 csi -> setupForRepeatedUse ();
00167 csi -> doingResolve () = false;
00168
00169
00170
00171 int nImprov, nIter = 0;
00172
00173 bool notImproved = false;
00174
00175 while (!notImproved &&
00176 (nIter++ < MAX_OBBT_ITER) &&
00177 ((nImprov = obbtInner (csi, cs, chg_bds, babInfo)) > 0) &&
00178 (CoinCpuTime () < maxCpuTime_)) {
00179
00180 int nchanged, *changed = NULL;
00181
00183 sparse2dense (nVars (), chg_bds, changed, nchanged);
00184 cg -> genColCuts (*csi, cs, nchanged, changed);
00185
00186 if ((nIter < MAX_OBBT_ITER) &&
00187 (nImprov >= THRES_NBD_CHANGED)) {
00188
00189
00190 int nCurCuts = cs.sizeRowCuts ();
00191 cg -> genRowCuts (*csi, cs, nchanged, changed, chg_bds);
00192
00193 if (nCurCuts == cs.sizeRowCuts ())
00194 notImproved = true;
00195
00196 } else notImproved = true;
00197
00198 if (changed)
00199 free (changed);
00200 }
00201
00202 csi -> doingResolve () = true;
00203
00204 delete csi;
00205
00206 if (nImprov < 0) {
00207 jnlst_->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING, " Couenne: infeasible node after OBBT\n");
00208 return -1;
00209 }
00210 }
00211
00212 return 0;
00213 }