00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "CouenneCutGenerator.hpp"
00012 #include "CouenneProblem.hpp"
00013 #include "CouenneObject.hpp"
00014 #include "CouenneBranchingObject.hpp"
00015 #include "CouenneDisjCuts.hpp"
00016
00017 using namespace Ipopt;
00018 using namespace Couenne;
00019
00022 bool BranchingFBBT (CouenneProblem *problem,
00023 OsiObject *Object,
00024 OsiSolverInterface *solver);
00025
00027 int CouenneDisjCuts::getDisjunctions (std::vector <std::pair <OsiCuts *, OsiCuts *> > &disjs,
00028 OsiSolverInterface &si,
00029 OsiCuts &cs,
00030 const CglTreeInfo &info) const {
00031
00032 OsiBranchingInformation brInfo (&si,
00033 true,
00034 false);
00035
00036 if (jnlst_ -> ProduceOutput (J_MATRIX, J_DISJCUTS))
00037 for (int i=0; i<si.getNumCols (); i++)
00038 printf ("%3d. %8g [%8g %8g]\n", i,
00039 brInfo. solution_ [i],
00040 brInfo. lower_ [i],
00041 brInfo. upper_ [i]);
00042
00043
00044 branchingMethod_ -> setupList (&brInfo, true);
00045
00046 int
00047 ncols = si.getNumCols (),
00048 retval = COUENNE_FEASIBLE;
00049
00050 int nobjs = branchingMethod_ -> numberUnsatisfied ();
00051
00052 if (nobjs) {
00053
00054 if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS))
00055 printf ("--- %d disjunctive objects\n", nobjs);
00056
00057 const int *candidates = branchingMethod_ -> candidates ();
00058 OsiObject **objs = si. objects ();
00059
00060
00061
00062
00063 for (int candInd = 0, num = 0;
00064 (candInd < nobjs) && (num < numDisjunctions_);
00065 candInd++) {
00066
00067 OsiObject *Object = objs [candidates [candInd]];
00068 CouenneObject *cObj = dynamic_cast <CouenneObject *> (Object);
00069
00070
00071
00072 int indVar = Object -> columnNumber ();
00073 if (indVar < 0)
00074 continue;
00075
00076 if (cObj &&
00077 ((cObj -> checkInfeasibility (&brInfo) == 0.) ||
00078 (cObj -> isCuttable ())))
00079 continue;
00080
00081 bool feasLeft = true, feasRight = true;
00082 OsiCuts *leftCuts = NULL, *rightCuts = NULL;
00083
00084 const double
00085 *saveLower = CoinCopyOfArray (si.getColLower (), ncols),
00086 *saveUpper = CoinCopyOfArray (si.getColUpper (), ncols);
00087
00088 OsiBranchingObject *brObj = Object -> createBranch (&si, &brInfo, 0);
00089
00090 if (brObj &&
00091 jnlst_ -> ProduceOutput (J_VECTOR, J_DISJCUTS) &&
00092 dynamic_cast <CouenneBranchingObject *> (brObj) &&
00093 dynamic_cast <CouenneBranchingObject *> (brObj) -> variable ())
00094 printf ("--- cand [%d] is %d: x_%d <>= %g [%g,%g]\n",
00095 candInd,
00096 candidates [candInd],
00097 dynamic_cast <CouenneBranchingObject *> (brObj) -> variable () -> Index (),
00098 brObj -> value (),
00099 couenneCG_->Problem()->Lb(dynamic_cast<CouenneBranchingObject*>(brObj)
00100 ->variable()->Index ()),
00101 couenneCG_->Problem()->Ub(dynamic_cast<CouenneBranchingObject*>(brObj)
00102 ->variable()->Index ()));
00103
00104
00105
00106 if ((brObj -> branch (&si) >= COUENNE_INFINITY) ||
00107
00108 (!cObj && !BranchingFBBT (couenneCG_ -> Problem (), Object, &si)))
00109 feasLeft = false;
00110 else leftCuts = getSingleDisjunction (si);
00111
00112
00113 si.setColLower (saveLower);
00114 si.setColUpper (saveUpper);
00115
00116 delete brObj;
00117
00118
00119
00120 brObj = Object -> createBranch (&si, &brInfo, 1);
00121
00122 if ((brObj -> branch (&si) >= COUENNE_INFINITY) ||
00123
00124 (!cObj && !BranchingFBBT (couenneCG_ -> Problem (), Object, &si)))
00125 feasRight = false;
00126 else rightCuts = getSingleDisjunction (si);
00127
00128 delete brObj;
00129
00130
00131 si.setColLower (saveLower);
00132 si.setColUpper (saveUpper);
00133
00134
00135
00136 if (feasLeft && feasRight) {
00137
00138
00139
00140 std::pair <OsiCuts *, OsiCuts *> newpair;
00141 newpair.first = leftCuts;
00142 newpair.second = rightCuts;
00143
00144 disjs.push_back (newpair);
00145
00146 num++;
00147
00148 } else if (feasLeft) {
00149
00150 jnlst_ -> Printf (J_VECTOR, J_DISJCUTS, "--- disj: infeasible right\n");
00151 applyColCuts (si, leftCuts);
00152 retval = COUENNE_TIGHTENED;
00153
00154 } else if (feasRight) {
00155
00156 jnlst_ -> Printf (J_VECTOR, J_DISJCUTS, "--- infeasible left\n");
00157 applyColCuts (si, rightCuts);
00158 retval = COUENNE_TIGHTENED;
00159
00160 } else {
00161 jnlst_ -> Printf (J_VECTOR, J_DISJCUTS, "--- infeasible!!!\n");
00162 retval = COUENNE_INFEASIBLE;
00163 break;
00164 }
00165
00166 delete [] saveLower;
00167 delete [] saveUpper;
00168 }
00169 }
00170
00171
00172
00173
00174
00175 if (retval != COUENNE_INFEASIBLE) {
00176
00177 if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS))
00178 printf ("have %d disjunctions\n", (int) (disjs.size ()));
00179
00180
00181
00182
00183
00184
00185 for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjs.begin ();
00186 disjI != disjs.end (); ++disjI) {
00187
00188 if (checkDisjSide (si, disjI -> first) == COUENNE_INFEASIBLE) {
00189 if (checkDisjSide (si, disjI -> second) == COUENNE_INFEASIBLE) {
00190
00191 retval = COUENNE_INFEASIBLE;
00192 break;
00193
00194 } else {
00195
00196 if (jnlst_ -> ProduceOutput (J_VECTOR, J_DISJCUTS))
00197 printf ("--- infeasible left [2]!\n");
00198 applyColCuts (si, disjI -> second);
00199 retval = COUENNE_TIGHTENED;
00200 }
00201 } else if (checkDisjSide (si, disjI -> second) == COUENNE_INFEASIBLE) {
00202
00203 if (jnlst_ -> ProduceOutput (J_VECTOR, J_DISJCUTS))
00204 printf ("--- infeasible right [2]!\n");
00205 applyColCuts (si, disjI -> first);
00206 retval = COUENNE_TIGHTENED;
00207 }
00208 }
00209
00210 if (retval == COUENNE_INFEASIBLE)
00211 return retval;
00212
00213
00214
00215
00216
00217 for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjs.begin ();
00218 disjI != disjs.end (); ++disjI) {
00219
00220 CoinPackedVector lowerChg, upperChg;
00221
00222
00223 getBoxUnion (si, disjI -> first, disjI -> second, lowerChg, upperChg);
00224
00225 if ((lowerChg.getNumElements () > 0) ||
00226 (upperChg.getNumElements () > 0)) {
00227
00228 OsiColCut cut;
00229 cut.setLbs (lowerChg);
00230 cut.setUbs (upperChg);
00231 applyColCuts (si, &cut);
00232
00233 cs.insert (cut);
00234 }
00235 }
00236 }
00237
00238 return retval;
00239 }
00240
00241
00243 void CouenneDisjCuts::applyColCuts (OsiSolverInterface &si, OsiCuts *cuts) const {
00244
00245 if (jnlst_ -> ProduceOutput (J_MATRIX, J_DISJCUTS)) {
00246 printf ("applying cuts to SI:\n");
00247
00248 for (int i = cuts -> sizeColCuts (); i--;)
00249 cuts -> colCutPtr (i) -> print ();
00250 printf ("--------------------\n");
00251 }
00252
00253
00254 for (int i = cuts -> sizeColCuts (); i--;)
00255 applyColCuts (si, cuts -> colCutPtr (i));
00256 }
00257
00258
00260 void CouenneDisjCuts::applyColCuts (OsiSolverInterface &si, OsiColCut *cut) const {
00261
00262
00263 if (jnlst_ -> ProduceOutput (J_VECTOR, J_DISJCUTS)) {
00264 printf ("tightening bounds: ");
00265 cut -> print ();
00266 }
00267
00268 const CoinPackedVector
00269 &lbs = cut -> lbs (),
00270 &ubs = cut -> ubs ();
00271
00272 const int *lind = lbs.getIndices (), *uind = ubs.getIndices ();
00273 const double *lval = lbs.getElements (), *uval = ubs.getElements (),
00274 *oldLower = si.getColLower (),
00275 *oldUpper = si.getColUpper ();
00276
00277 for (int j=lbs.getNumElements (); j--; lval++, lind++)
00278 if (*lval > oldLower [*lind] + COUENNE_EPS)
00279 si.setColLower (*lind, *lval);
00280
00281 for (int j=ubs.getNumElements (); j--; uval++, uind++)
00282 if (*uval < oldUpper [*uind] - COUENNE_EPS)
00283 si.setColUpper (*uind, *uval);
00284 }