00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include <vector>
00012
00013 #include "CoinHelperFunctions.hpp"
00014
00015 #include "BonBabSetupBase.hpp"
00016
00017 #include "CouenneTypes.hpp"
00018 #include "CouenneExpression.hpp"
00019 #include "CouenneExprIVar.hpp"
00020 #include "CouenneExprSub.hpp"
00021 #include "CouenneExprClone.hpp"
00022 #include "CouenneProblem.hpp"
00023 #include "CouenneProblemElem.hpp"
00024 #include "CouenneDepGraph.hpp"
00025
00026 using namespace Ipopt;
00027 using namespace Couenne;
00028
00029 void replace (CouenneProblem *p, int wind, int xind);
00030
00032
00033 bool CouenneProblem::standardize () {
00034
00035 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00036 printf ("Reformulation. current point: %d vars -------------------\n",
00037 domain_.current () -> Dimension ());
00038 for (int i=0; i<domain_.current () -> Dimension (); i++)
00039 printf ("%3d %20g [%20g %20g]\n", i, domain_.x (i), domain_.lb (i), domain_.ub (i));
00040 }
00041
00042 bool retval = true;
00043
00044
00045
00046 graph_ = new DepGraph;
00047
00048 for (std::vector <exprVar *>::iterator i = variables_ . begin ();
00049 i != variables_ . end (); ++i)
00050 graph_ -> insert (*i);
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174 for (std::vector <CouenneObjective *>::iterator i = objectives_.begin ();
00175 i != objectives_.end (); ++i) {
00176
00177 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00178 printf ("Objective [code: %d]", (*i) -> Body () -> code ());
00179 (*i) -> print ();
00180 }
00181
00182
00183
00184 std::set <int> deplist;
00185
00186 if (0 == (*i) -> Body () -> DepList (deplist, TAG_AND_RECURSIVE)) {
00187
00188
00189
00190
00191 constObjVal_ = (*i) -> Body () -> Value ();
00192
00193 } else {
00194
00195 exprAux *aux = (*i) -> standardize (this);
00196
00197 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00198 printf (" objective "); (*i) -> print ();
00199 if (aux) {printf (" admits aux "); aux -> print ();}
00200 }
00201
00202 if (aux) {
00203
00204 (*i) -> Body (new exprClone (aux));
00205 }
00206
00207 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00208 printf (". New obj: "); (*i) -> print (); printf ("\n");
00209 }
00210 }
00211 }
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225 commuted_ = new bool [nVars ()];
00226 CoinFillN (commuted_, nVars (), false);
00227
00228 std::vector <std::vector <CouenneConstraint *>::iterator> iters2erase;
00229
00230 for (std::vector <CouenneConstraint *>::iterator i = constraints_.begin ();
00231 i != constraints_.end (); ++i) {
00232
00233 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00234 printf ("\nReformulating constraint: ");
00235 (*i) -> print ();
00236 }
00237
00238 CouNumber
00239 conLb = (*((*i) -> Lb ())) (),
00240 conUb = (*((*i) -> Ub ())) ();
00241
00242
00243
00244
00245
00246 expression *eBody = (*i) -> Body ();
00247
00248 if (eBody -> Linearity () <= CONSTANT) {
00249
00250 CouNumber bodyVal = (*eBody)();
00251
00252 if ((bodyVal < conLb - COUENNE_BOUND_PREC) ||
00253 (bodyVal > conUb + COUENNE_BOUND_PREC)) {
00254
00255 jnlst_ -> Printf (J_SUMMARY, J_PROBLEM,
00256 "Constraint: all variables eliminated, but value %g out of bounds [%g,%g]: ",
00257 bodyVal, conLb, conUb);
00258
00259 if (jnlst_ -> ProduceOutput (J_SUMMARY, J_PROBLEM))
00260 (*i) -> print ();
00261
00262 retval = false;
00263 break;
00264
00265 } else {
00266
00267 iters2erase.push_back (i);
00268 continue;
00269 }
00270 }
00271
00272 exprAux *aux = (*i) -> standardize (this);
00273
00274 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00275 printf (" reformulated: aux w[%d] ", aux ? (aux -> Index ()) : -2);
00276 (*i) -> print ();
00277 }
00278
00279 if (aux) {
00280
00281
00282
00283
00284
00285 aux -> top_level () = true;
00286
00287
00288
00289
00290
00291
00292
00293
00294 (*i) -> Body (new exprClone (aux));
00295
00296
00297 }
00298 else {
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329 iters2erase.push_back (i);
00330 }
00331
00332
00333
00334 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00335 printf (" --> "); (*i) -> print (); printf ("\n\n");
00336 }
00337
00338
00339
00340
00341 }
00342
00343 for (unsigned int i = iters2erase.size (); i--;)
00344 constraints_. erase (iters2erase [i]);
00345
00346 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00347
00348 printf ("done with standardization: (careful, bounds below can be nonsense)\n");
00349 print ();
00350 }
00351
00352 delete auxSet_;
00353
00354
00355
00356
00357 domain_.current () -> resize (nVars ());
00358
00359
00360 graph_ -> createOrder ();
00361
00362
00363 assert (graph_ -> checkCycles () == false);
00364
00365
00366
00367 int n = nVars ();
00368 numbering_ = new int [n];
00369 std::set <DepNode *, compNode> vertices = graph_ -> Vertices ();
00370
00371 for (std::set <DepNode *, compNode>::iterator i = vertices.begin ();
00372 i != vertices.end (); ++i)
00373
00374 numbering_ [(*i) -> Order ()] = (*i) -> Index ();
00375
00377
00378
00379
00380 for (int i = 0; i < nVars (); i++) {
00381
00382 int ord = numbering_ [i];
00383
00384 if (variables_ [ord] -> Type () == AUX) {
00385
00386
00387
00388
00389 if (variables_ [ord] -> Index () >= nOrigVars_) {
00390
00391 domain_.lb (ord) = -COIN_DBL_MAX;
00392 domain_.ub (ord) = COIN_DBL_MAX;
00393 }
00394
00395
00396
00397
00398 variables_ [ord] -> crossBounds ();
00399
00400
00401
00402 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00403 printf (":::: %3d %10g [%10g, %10g]",
00404 ord, domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00405 }
00406
00407
00408 domain_.x (ord) = (*(variables_ [ord] -> Image ())) ();
00409 domain_.lb (ord) = (*(variables_ [ord] -> Lb ())) ();
00410 domain_.ub (ord) = (*(variables_ [ord] -> Ub ())) ();
00411
00412
00413
00414
00415
00416
00417
00418 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00419 printf (" --> %10g [%10g, %10g] [",
00420 domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00421 variables_ [ord] -> Lb () -> print (); printf (",");
00422 variables_ [ord] -> Ub () -> print (); printf ("]\n");
00423 }
00424
00425 bool integer = variables_ [ord] -> isInteger ();
00426
00427 if (integer) {
00428 domain_.lb (ord) = ceil (domain_.lb (ord) - COUENNE_EPS);
00429 domain_.ub (ord) = floor (domain_.ub (ord) + COUENNE_EPS);
00430 }
00431 }
00432 }
00433
00434
00435
00436
00437
00438 std::string delete_redund;
00439
00440 if (bonBase_) bonBase_ -> options () -> GetStringValue ("delete_redundant", delete_redund, "couenne.");
00441 else delete_redund = "yes";
00442
00443 if (delete_redund == "yes")
00444
00445
00446 for (std::vector <exprVar *>::iterator i = variables_.begin ();
00447 i != variables_.end (); ++i)
00448
00449 if (((*i) -> Type () == AUX) && ((*i) -> sign () == expression::AUX_EQ)) {
00450
00451 int type = (*i) -> Image () -> Type ();
00452
00453 if ((type == VAR) || (type == AUX)) {
00454
00455
00456
00457
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467 int
00468 indStays = (*i) -> Image () -> Index (),
00469 indLeaves = (*i) -> Index ();
00470
00471 if (indStays == indLeaves)
00472 continue;
00473
00474
00475
00476
00477
00478
00479 exprVar
00480 *varStays = variables_ [indStays],
00481 *varLeaves = variables_ [indLeaves];
00482
00483
00484
00485 varStays -> lb () = varLeaves -> lb () = CoinMax (varStays -> lb (), varLeaves -> lb ());
00486 varStays -> ub () = varLeaves -> ub () = CoinMin (varStays -> ub (), varLeaves -> ub ());
00487
00488 if (varStays -> isInteger () ||
00489 varLeaves -> isInteger ()) {
00490
00491 varStays -> lb () = ceil (varStays -> lb ());
00492 varStays -> ub () = floor (varStays -> ub ());
00493
00494 if (varStays -> Type () == AUX)
00495 varStays -> setInteger (true);
00496 else {
00497
00498 variables_ [indStays] = varStays = new exprIVar (indStays, &domain_);
00499 auxiliarize (varStays);
00500
00501 }
00502 }
00503
00504 auxiliarize (varLeaves, varStays);
00505
00506
00507 varLeaves -> zeroMult ();
00508 }
00509 }
00510
00516 for (int ii=0; ii < nVars (); ii++) {
00517
00518 int i = numbering_ [ii];
00519
00520 if ((Var (i) -> Multiplicity () > 0) &&
00521 (Var (i) -> Type () == AUX) &&
00522 (Var (i) -> Image () -> isInteger ()) &&
00523 (Var (i) -> sign () == expression::AUX_EQ))
00524 Var (i) -> setInteger (true);
00525
00526
00527
00528 }
00529
00530
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561 delete [] commuted_; commuted_ = NULL;
00562 delete graph_; graph_ = NULL;
00563
00564 return retval;
00565 }