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)) {printf (" --> "); (*i) -> print (); printf ("\n\n");}
00335
00336
00337
00338
00339 }
00340
00341 for (unsigned int i = iters2erase.size (); i--;)
00342 constraints_. erase (iters2erase [i]);
00343
00344 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00345
00346 printf ("done with standardization: (careful, bounds below can be nonsense)\n");
00347 print ();
00348 }
00349
00350 delete auxSet_;
00351
00352
00353
00354
00355 domain_.current () -> resize (nVars ());
00356
00357
00358 graph_ -> createOrder ();
00359
00360
00361 assert (graph_ -> checkCycles () == false);
00362
00363
00364
00365 int n = nVars ();
00366 numbering_ = new int [n];
00367 std::set <DepNode *, compNode> vertices = graph_ -> Vertices ();
00368
00369 for (std::set <DepNode *, compNode>::iterator i = vertices.begin ();
00370 i != vertices.end (); ++i)
00371
00372 numbering_ [(*i) -> Order ()] = (*i) -> Index ();
00373
00375
00376
00377
00378 for (int i = 0; i < nVars (); i++) {
00379
00380 int ord = numbering_ [i];
00381
00382 if (variables_ [ord] -> Type () == AUX) {
00383
00384
00385
00386
00387 if (variables_ [ord] -> Index () >= nOrigVars_) {
00388
00389 domain_.lb (ord) = -COIN_DBL_MAX;
00390 domain_.ub (ord) = COIN_DBL_MAX;
00391 }
00392
00393
00394
00395
00396 variables_ [ord] -> crossBounds ();
00397
00398
00399
00400 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00401 printf (":::: %3d %10g [%10g, %10g]",
00402 ord, domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00403 }
00404
00405
00406 domain_.x (ord) = (*(variables_ [ord] -> Image ())) ();
00407 domain_.lb (ord) = (*(variables_ [ord] -> Lb ())) ();
00408 domain_.ub (ord) = (*(variables_ [ord] -> Ub ())) ();
00409
00410
00411
00412
00413
00414
00415
00416 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00417 printf (" --> %10g [%10g, %10g] [",
00418 domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00419 variables_ [ord] -> Lb () -> print (); printf (",");
00420 variables_ [ord] -> Ub () -> print (); printf ("]\n");
00421 }
00422
00423 bool integer = variables_ [ord] -> isInteger ();
00424
00425 if (integer) {
00426 domain_.lb (ord) = ceil (domain_.lb (ord) - COUENNE_EPS);
00427 domain_.ub (ord) = floor (domain_.ub (ord) + COUENNE_EPS);
00428 }
00429 }
00430 }
00431
00432
00433
00434
00435
00436 std::string delete_redund;
00437
00438 if (bonBase_) bonBase_ -> options () -> GetStringValue ("delete_redundant", delete_redund, "couenne.");
00439 else delete_redund = "yes";
00440
00441 if (delete_redund == "yes")
00442
00443
00444 for (std::vector <exprVar *>::iterator i = variables_.begin ();
00445 i != variables_.end (); ++i)
00446
00447 if (((*i) -> Type () == AUX) && ((*i) -> sign () == expression::AUX_EQ)) {
00448
00449 int type = (*i) -> Image () -> Type ();
00450
00451 if ((type == VAR) || (type == AUX)) {
00452
00453
00454
00455
00456
00457
00458
00459
00460
00461
00462
00463
00464
00465 int
00466 indStays = (*i) -> Image () -> Index (),
00467 indLeaves = (*i) -> Index ();
00468
00469 if (indStays == indLeaves)
00470 continue;
00471
00472
00473
00474
00475
00476
00477 exprVar
00478 *varStays = variables_ [indStays],
00479 *varLeaves = variables_ [indLeaves];
00480
00481
00482
00483 varStays -> lb () = varLeaves -> lb () = CoinMax (varStays -> lb (), varLeaves -> lb ());
00484 varStays -> ub () = varLeaves -> ub () = CoinMin (varStays -> ub (), varLeaves -> ub ());
00485
00486 if (varStays -> isInteger () ||
00487 varLeaves -> isInteger ()) {
00488
00489 varStays -> lb () = ceil (varStays -> lb ());
00490 varStays -> ub () = floor (varStays -> ub ());
00491
00492 if (varStays -> Type () == AUX)
00493 varStays -> setInteger (true);
00494 else {
00495
00496 variables_ [indStays] = varStays = new exprIVar (indStays, &domain_);
00497 auxiliarize (varStays);
00498
00499 }
00500 }
00501
00502 auxiliarize (varLeaves, varStays);
00503
00504
00505 varLeaves -> zeroMult ();
00506 }
00507 }
00508
00514 for (int ii=0; ii < nVars (); ii++) {
00515
00516 int i = numbering_ [ii];
00517
00518 if ((Var (i) -> Multiplicity () > 0) &&
00519 (Var (i) -> Type () == AUX) &&
00520 (Var (i) -> Image () -> isInteger ()) &&
00521 (Var (i) -> sign () == expression::AUX_EQ))
00522 Var (i) -> setInteger (true);
00523
00524
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 delete [] commuted_; commuted_ = NULL;
00560 delete graph_; graph_ = NULL;
00561
00562 return retval;
00563 }