00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "CouenneProblem.hpp"
00012 #include "CouenneCutGenerator.hpp"
00013 #include "CouenneDisjCuts.hpp"
00014
00015
00017 OsiCuts *CouenneDisjCuts::getSingleDisjunction (OsiSolverInterface &si) const {
00018
00019 int
00020 ncols = si.getNumCols (), nNL = 0, nNU = 0,
00021 *indNL = new int [ncols],
00022 *indNU = new int [ncols];
00023
00024 double
00025 *oldL = couenneCG_ -> Problem () -> Lb (), *valNL = new double [ncols],
00026 *oldU = couenneCG_ -> Problem () -> Ub (), *valNU = new double [ncols];
00027
00028 const double
00029 *newL = si.getColLower (),
00030 *newU = si.getColUpper ();
00031
00032 for (int i=0; i<ncols; i++) {
00033 if (newL [i] > oldL [i] + COUENNE_EPS) {indNL [nNL] = i; valNL [nNL++] = newL [i];}
00034 if (newU [i] < oldU [i] - COUENNE_EPS) {indNU [nNU] = i; valNU [nNU++] = newU [i];}
00035 }
00036
00037 OsiColCut cut;
00038
00039 cut. setLbs (nNL, indNL, valNL);
00040 cut. setUbs (nNU, indNU, valNU);
00041
00042 OsiCuts *cuts = new OsiCuts;
00043
00044 cuts -> insert (cut);
00045
00046 delete [] indNL; delete [] valNL;
00047 delete [] indNU; delete [] valNU;
00048
00049 return cuts;
00050 }
00051
00052
00054 int CouenneDisjCuts::checkDisjSide (OsiSolverInterface &si, OsiCuts *cuts) const {
00055
00056 int retval = COUENNE_FEASIBLE;
00057
00058 const double
00059 *lower = si.getColLower (),
00060 *upper = si.getColUpper ();
00061
00062
00063
00064 for (int i = cuts -> sizeColCuts (); i--;) {
00065
00066
00067
00068 const CoinPackedVector &lbs = cuts -> colCutPtr (i) -> lbs ();
00069 const int *lindices = lbs.getIndices ();
00070 const double *lvalues = lbs.getElements ();
00071
00072 for (int j = lbs.getNumElements (); j--;) {
00073 register double lb = *lvalues++;
00074 register int ind = *lindices++;
00075
00076 if (lb > upper [ind] + COUENNE_EPS)
00077 return COUENNE_INFEASIBLE;
00078
00079 if (lb > lower [ind] + COUENNE_EPS)
00080 retval = COUENNE_TIGHTENED;
00081 }
00082
00083
00084
00085 const CoinPackedVector &ubs = cuts -> colCutPtr (i) -> ubs ();
00086 const int *uindices = ubs.getIndices ();
00087 const double *uvalues = ubs.getElements ();
00088
00089 for (int j = ubs.getNumElements (); j--;) {
00090 register double ub = *uvalues++;
00091 register int ind = *uindices++;
00092
00093 if (ub < lower [ind] - COUENNE_EPS)
00094 return COUENNE_INFEASIBLE;
00095
00096 if (ub < upper [ind] - COUENNE_EPS)
00097 retval = COUENNE_TIGHTENED;
00098 }
00099 }
00100
00101 return retval;
00102 }
00103
00104
00106 int CouenneDisjCuts::getBoxUnion (OsiSolverInterface &si,
00107 OsiCuts *left, OsiCuts *right,
00108 CoinPackedVector &lower, CoinPackedVector &upper) const {
00109
00110 int retval = COUENNE_FEASIBLE;
00111
00112 CoinPackedVector
00113 lowerLeft, upperLeft,
00114 lowerRight, upperRight;
00115
00116
00117 for (int i = left -> sizeColCuts (); i--;) {
00118 lowerLeft. append (left -> colCutPtr (i) -> lbs ());
00119 upperLeft. append (left -> colCutPtr (i) -> ubs ());
00120 }
00121
00122
00123 for (int i = right -> sizeColCuts (); i--;) {
00124 lowerRight. append (right -> colCutPtr (i) -> lbs ());
00125 upperRight. append (right -> colCutPtr (i) -> ubs ());
00126 }
00127
00128
00129 lowerLeft. sortIncrIndex (); upperLeft. sortIncrIndex ();
00130 lowerRight. sortIncrIndex (); upperRight. sortIncrIndex ();
00131
00132
00133
00134 mergeBoxes (-1, lowerLeft, lowerRight, lower);
00135 mergeBoxes (+1, upperLeft, upperRight, upper);
00136
00137 return retval;
00138 }
00139
00140
00142 void CouenneDisjCuts::mergeBoxes (int dir,
00143 CoinPackedVector &left,
00144 CoinPackedVector &right,
00145 CoinPackedVector merged) const {
00146 int
00147 Ln = left. getNumElements (),
00148 Rn = right. getNumElements ();
00149
00150 if (!Ln || !Rn)
00151 return;
00152
00153 const int
00154 *Li = left. getIndices (),
00155 *Ri = right. getIndices ();
00156
00157 const double
00158 *Le = left. getElements (),
00159 *Re = right. getElements ();
00160
00161 for (;;) {
00162
00163 for (;;) {
00164
00165 register int diff = *Li - *Ri;
00166
00167 if (diff < 0) {if (!--Ln) break; Li++; Le++;}
00168 else if (diff > 0) {if (!--Rn) break; Ri++; Re++;}
00169 else break;
00170 }
00171
00172 if (!Ln || !Rn) break;
00173 if (dir < 0) merged. insert (*Li, *Le<*Re ? *Le : *Re);
00174 else merged. insert (*Li, *Le>*Re ? *Le : *Re);
00175
00176 Li++; Ri++;
00177 Le++; Re++;
00178
00179 if (!--Ln || !--Rn) break;
00180 }
00181 }