00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include "CoinTime.hpp"
00013 #include "BonChooseVariable.hpp"
00014 #include "CouenneChooseStrong.hpp"
00015 #include "CouenneProblem.hpp"
00016 #include "CouenneBranchingObject.hpp"
00017
00020 double distance (const double *p1, const double *p2, int size, double k=2.) {
00021
00022 double
00023 result = 0.,
00024 element;
00025
00026 if (k == 2.)
00027
00028 while (size--) {
00029 element = *p1++ - *p2++;
00030 result += element * element;
00031 }
00032
00033 else
00034
00035 while (size--) {
00036 element = *p1++ - *p2++;
00037 result += pow (element, k);
00038 }
00039
00040 return pow (result, 1. / k);
00041 }
00042
00043
00044
00045
00058 int CouenneChooseStrong::doStrongBranching (OsiSolverInterface *solver,
00059 OsiBranchingInformation *info,
00060 int numberToDo, int returnCriterion) {
00061
00062
00063
00064 jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING,
00065 "\n-\n------- CCS: trying %d objects:\n", numberToDo);
00066
00067
00068
00069 int numberColumns = solver -> getNumCols ();
00070
00071 solver -> markHotStart ();
00072
00073 const double
00074 *lower = info -> lower_,
00075 *upper = info -> upper_;
00076
00077 double
00078 *saveLower = CoinCopyOfArray (info -> lower_, numberColumns),
00079 *saveUpper = CoinCopyOfArray (info -> upper_, numberColumns),
00080
00081 *Lower0 = NULL,
00082 *Upper0 = NULL,
00083
00084 *oldLower = new double [numberColumns],
00085 *oldUpper = new double [numberColumns],
00086
00087 *lpSol = NULL,
00088 timeStart = CoinCpuTime ();
00089
00090 if (jnlst_ -> ProduceOutput (J_DETAILED, J_BRANCHING)) {
00091 Lower0 = CoinCopyOfArray (info -> lower_, numberColumns);
00092 Upper0 = CoinCopyOfArray (info -> upper_, numberColumns);
00093 }
00094
00095
00096 if (pseudoUpdateLP_)
00097 lpSol = CoinCopyOfArray (info -> solution_, numberColumns);
00098
00099
00100 problem_ -> domain () -> push
00101 (problem_ -> nVars (),
00102 info -> solution_,
00103 info -> lower_,
00104 info -> upper_);
00105
00106 int returnCode = 0, iDo = 0;
00107
00108 for (;iDo < numberToDo; iDo++) {
00109
00110 Bonmin::HotInfo * result = results_ () + iDo;
00111
00112 OsiObject *Object = solver_ -> objects () [result -> whichObject ()];
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125 OsiBranchingObject * branch = result -> branchingObject ();
00126 assert (branch->numberBranches()==2);
00127
00128 CouenneBranchingObject *cb = dynamic_cast <CouenneBranchingObject *> (branch);
00129 if (cb) cb -> setSimulate (true);
00130
00131 int
00132 status0 = -1,
00133 status1 = -1;
00134
00136
00137
00138
00139
00140
00141 status0 = simulateBranch (Object, info, branch, solver, result, -1);
00142
00143
00144
00145 CoinCopyN (problem_ -> Lb (), numberColumns, oldLower);
00146 CoinCopyN (problem_ -> Ub (), numberColumns, oldUpper);
00147
00148
00149 for (int j=0; j<numberColumns; j++) {
00150
00151 if (saveLower [j] != lower [j]) solver -> setColLower (j, saveLower [j]);
00152 if (saveUpper [j] != upper [j]) solver -> setColUpper (j, saveUpper [j]);
00153 }
00154
00155 status1 = simulateBranch (Object, info, branch, solver, result, +1);
00156
00158
00159 jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, "-------\n");
00160
00161 if (cb) cb -> setSimulate (false);
00162
00164
00165 bool tightened = false;
00166
00167 t_chg_bounds *chg_bds = new t_chg_bounds [numberColumns];
00168
00169
00170 for (int j=0; j<numberColumns; j++) {
00171
00172 if (oldLower [j] < problem_ -> Lb (j)) problem_ -> Lb (j) = oldLower [j];
00173 if (oldUpper [j] > problem_ -> Ub (j)) problem_ -> Ub (j) = oldUpper [j];
00174
00175 if (problem_ -> Lb (j) > lower [j] + COUENNE_EPS) {
00176 chg_bds [j].setLower (t_chg_bounds::CHANGED);
00177 tightened = true;
00178 }
00179
00180 if (problem_ -> Ub (j) < upper [j] - COUENNE_EPS) {
00181 chg_bds [j].setUpper (t_chg_bounds::CHANGED);
00182 tightened = true;
00183 }
00184 }
00185
00186 if (tightened &&
00187 (problem_ -> doFBBT ()) &&
00188 !(problem_ -> btCore (chg_bds)))
00189
00190 status0 = status1 = 1;
00191
00192 delete [] chg_bds;
00193
00194
00195 for (int j=0; j<numberColumns; j++) {
00196
00197 if (oldLower [j] < problem_ -> Lb (j)) problem_ -> Lb (j) = oldLower [j];
00198 if (oldUpper [j] > problem_ -> Ub (j)) problem_ -> Ub (j) = oldUpper [j];
00199 }
00200
00201
00202
00203 for (int j=0; j<numberColumns; j++) {
00204
00205 solver -> setColLower (j, saveLower [j] = problem_ -> Lb (j));
00206 solver -> setColUpper (j, saveUpper [j] = problem_ -> Ub (j));
00207 }
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224 if (status0 == 1 &&
00225 status1 == 1) {
00226 returnCode=-1;
00227 break;
00228 } else if (status0==1 || status1==1) {
00229 numberStrongFixed_++;
00230 if (!returnCriterion) {
00231 returnCode=1;
00232 } else {
00233 returnCode=2;
00234 break;
00235 }
00236 }
00237
00238 bool hitMaxTime = ( CoinCpuTime()-timeStart > info->timeRemaining_);
00239 if (hitMaxTime) {
00240 returnCode=3;
00241 break;
00242 }
00243 }
00244
00245
00246 if (jnlst_ -> ProduceOutput (J_DETAILED, J_BRANCHING)) {
00247 printf ("tightened bounds: ");
00248
00249 for (int j=0; j<numberColumns; j++) {
00250
00251 if (problem_ -> Lb (j) > Lower0 [j]) printf ("l%d (%g-->%g) ", j,Lower0[j], problem_->Lb (j));
00252 if (problem_ -> Ub (j) < Upper0 [j]) printf ("u%d (%g-->%g) ", j,Upper0[j], problem_->Ub (j));
00253 }
00254
00255 delete [] Lower0;
00256 delete [] Upper0;
00257 }
00258
00259 problem_ -> domain () -> pop ();
00260
00261 delete [] lpSol;
00262
00263 jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, "----------------------done\n\n\n");
00264
00265 if (iDo < numberToDo) iDo++;
00266 assert (iDo <= (int) results_.size());
00267 results_.resize (iDo);
00268
00269 delete [] oldLower;
00270 delete [] oldUpper;
00271
00272 delete [] saveLower;
00273 delete [] saveUpper;
00274
00275 solver -> unmarkHotStart ();
00276
00277
00278 branchtime_ += CoinCpuTime () - timeStart;
00279
00280 return returnCode;
00281 }
00282
00283
00284
00285 int CouenneChooseStrong::simulateBranch (OsiObject *Object,
00286 OsiBranchingInformation *info,
00287 OsiBranchingObject *branch,
00288 OsiSolverInterface *solver,
00289 Bonmin::HotInfo * result,
00290 int direction) {
00291
00292 bool boundBranch = branch -> boundBranch ();
00293
00294 int status = -1;
00295
00296 OsiSolverInterface *thisSolver =
00297 boundBranch ? solver : solver -> clone ();
00298
00299 CouenneObject *CouObj = dynamic_cast <CouenneObject *> (Object);
00300
00301 if ((branch -> branch (thisSolver) > COUENNE_INFINITY) ||
00302
00303 (!CouObj && !BranchingFBBT (problem_, Object, thisSolver))) {
00304
00305 status = 1;
00306
00307 if (direction < 0) result -> setDownStatus (1);
00308 else result -> setUpStatus (1);
00309
00310 } else {
00311
00312 if (boundBranch) thisSolver -> solveFromHotStart ();
00313 else {
00314
00315 int limit;
00316 thisSolver -> getIntParam (OsiMaxNumIterationHotStart, limit);
00317 thisSolver -> setIntParam (OsiMaxNumIteration, limit);
00318
00319 thisSolver -> resolve ();
00320 }
00321
00322 if (pseudoUpdateLP_ && CouObj && thisSolver -> isProvenOptimal ()) {
00323 CouNumber dist = distance (info -> solution_, thisSolver -> getColSolution (),
00324 problem_ -> nVars ());
00325 if (dist > COUENNE_EPS)
00326 CouObj -> setEstimate (dist, direction < 0 ? 0 : 1);
00327 }
00328 }
00329
00330
00331
00332
00333
00334 if (status < 0)
00335 status = result -> updateInformation (thisSolver, info, this);
00336
00337 numberStrongIterations_ += thisSolver -> getIterationCount ();
00338
00339 if ((status == 3) && (trustStrongForSolution_)) {
00340
00341 info -> cutoff_ = goodObjectiveValue_;
00342 problem_ -> setCutOff (goodObjectiveValue_);
00343 status = 0;
00344 }
00345
00346 if (solver != thisSolver)
00347 delete thisSolver;
00348
00349 return status;
00350 }