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 exprAux *aux = (*i) -> standardize (this);
00183
00184 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00185 printf (" objective "); (*i) -> print ();
00186 if (aux) {printf (" admits aux "); aux -> print ();}
00187 }
00188
00189 if (aux) {
00190
00191 (*i) -> Body (new exprClone (aux));
00192 }
00193
00194 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00195 printf (". New obj: "); (*i) -> print (); printf ("\n");
00196 }
00197 }
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211 commuted_ = new bool [nVars ()];
00212 CoinFillN (commuted_, nVars (), false);
00213
00214 std::vector <std::vector <CouenneConstraint *>::iterator> iters2erase;
00215
00216 for (std::vector <CouenneConstraint *>::iterator i = constraints_.begin ();
00217 i != constraints_.end (); ++i) {
00218
00219 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00220 printf ("\nReformulating constraint: ");
00221 (*i) -> print ();
00222 }
00223
00224 CouNumber
00225 conLb = (*((*i) -> Lb ())) (),
00226 conUb = (*((*i) -> Ub ())) ();
00227
00228
00229
00230
00231
00232 expression *eBody = (*i) -> Body ();
00233
00234 if (eBody -> Linearity () <= CONSTANT) {
00235
00236 CouNumber bodyVal = (*eBody)();
00237
00238 if ((bodyVal < conLb - COUENNE_BOUND_PREC) ||
00239 (bodyVal > conUb + COUENNE_BOUND_PREC)) {
00240
00241 jnlst_ -> Printf (J_SUMMARY, J_PROBLEM,
00242 "Constraint: all variables eliminated, but value %g out of bounds [%g,%g]: ",
00243 bodyVal, conLb, conUb);
00244
00245 if (jnlst_ -> ProduceOutput (J_SUMMARY, J_PROBLEM))
00246 (*i) -> print ();
00247
00248 retval = false;
00249 break;
00250
00251 } else {
00252
00253 iters2erase.push_back (i);
00254 continue;
00255 }
00256 }
00257
00258 exprAux *aux = (*i) -> standardize (this);
00259
00260 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00261 printf (" reformulated: aux w[%d] ", aux ? (aux -> Index ()) : -2);
00262 (*i) -> print ();
00263 }
00264
00265 if (aux) {
00266
00267
00268
00269
00270
00271 aux -> top_level () = true;
00272
00273
00274
00275
00276
00277
00278
00279
00280 (*i) -> Body (new exprClone (aux));
00281
00282
00283 }
00284 else {
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315 iters2erase.push_back (i);
00316 }
00317
00318
00319
00320 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00321 printf (" --> "); (*i) -> print (); printf ("\n\n");
00322 }
00323
00324
00325
00326
00327 }
00328
00329 for (unsigned int i = iters2erase.size (); i--;)
00330 constraints_. erase (iters2erase [i]);
00331
00332 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00333
00334 printf ("done with standardization: (careful, bounds below can be nonsense)\n");
00335 print ();
00336 }
00337
00338 delete auxSet_;
00339
00340
00341
00342
00343 domain_.current () -> resize (nVars ());
00344
00345
00346 graph_ -> createOrder ();
00347
00348
00349 assert (graph_ -> checkCycles () == false);
00350
00351
00352
00353 int n = nVars ();
00354 numbering_ = new int [n];
00355 std::set <DepNode *, compNode> vertices = graph_ -> Vertices ();
00356
00357 for (std::set <DepNode *, compNode>::iterator i = vertices.begin ();
00358 i != vertices.end (); ++i)
00359
00360 numbering_ [(*i) -> Order ()] = (*i) -> Index ();
00361
00363
00364
00365
00366 for (int i = 0; i < nVars (); i++) {
00367
00368 int ord = numbering_ [i];
00369
00370 if (variables_ [ord] -> Type () == AUX) {
00371
00372
00373
00374
00375 if (variables_ [ord] -> Index () >= nOrigVars_) {
00376
00377 domain_.lb (ord) = -COIN_DBL_MAX;
00378 domain_.ub (ord) = COIN_DBL_MAX;
00379 }
00380
00381
00382
00383
00384 variables_ [ord] -> crossBounds ();
00385
00386
00387
00388 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00389 printf (":::: %3d %10g [%10g, %10g]",
00390 ord, domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00391 }
00392
00393
00394 domain_.x (ord) = (*(variables_ [ord] -> Image ())) ();
00395 domain_.lb (ord) = (*(variables_ [ord] -> Lb ())) ();
00396 domain_.ub (ord) = (*(variables_ [ord] -> Ub ())) ();
00397
00398
00399
00400
00401
00402
00403
00404 if (jnlst_ -> ProduceOutput (J_ALL, J_REFORMULATE)) {
00405 printf (" --> %10g [%10g, %10g] [",
00406 domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00407 variables_ [ord] -> Lb () -> print (); printf (",");
00408 variables_ [ord] -> Ub () -> print (); printf ("]\n");
00409 }
00410
00411 bool integer = variables_ [ord] -> isInteger ();
00412
00413 if (integer) {
00414 domain_.lb (ord) = ceil (domain_.lb (ord) - COUENNE_EPS);
00415 domain_.ub (ord) = floor (domain_.ub (ord) + COUENNE_EPS);
00416 }
00417 }
00418 }
00419
00420
00421
00422
00423
00424 std::string delete_redund;
00425
00426 if (bonBase_) bonBase_ -> options () -> GetStringValue ("delete_redundant", delete_redund, "couenne.");
00427 else delete_redund = "yes";
00428
00429 if (delete_redund == "yes")
00430
00431
00432 for (std::vector <exprVar *>::iterator i = variables_.begin ();
00433 i != variables_.end (); ++i)
00434
00435 if (((*i) -> Type () == AUX) && ((*i) -> sign () == expression::AUX_EQ)) {
00436
00437 int type = (*i) -> Image () -> Type ();
00438
00439 if ((type == VAR) || (type == AUX)) {
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453 int
00454 indStays = (*i) -> Image () -> Index (),
00455 indLeaves = (*i) -> Index ();
00456
00457 if (indStays == indLeaves)
00458 continue;
00459
00460
00461
00462
00463
00464
00465 exprVar
00466 *varStays = variables_ [indStays],
00467 *varLeaves = variables_ [indLeaves];
00468
00469
00470
00471 varStays -> lb () = varLeaves -> lb () = CoinMax (varStays -> lb (), varLeaves -> lb ());
00472 varStays -> ub () = varLeaves -> ub () = CoinMin (varStays -> ub (), varLeaves -> ub ());
00473
00474 if (varStays -> isInteger () ||
00475 varLeaves -> isInteger ()) {
00476
00477 varStays -> lb () = ceil (varStays -> lb ());
00478 varStays -> ub () = floor (varStays -> ub ());
00479
00480 if (varStays -> Type () == AUX)
00481 varStays -> setInteger (true);
00482 else {
00483
00484 variables_ [indStays] = varStays = new exprIVar (indStays, &domain_);
00485 auxiliarize (varStays);
00486
00487 }
00488 }
00489
00490 auxiliarize (varLeaves, varStays);
00491
00492
00493 varLeaves -> zeroMult ();
00494 }
00495 }
00496
00502 for (int ii=0; ii < nVars (); ii++) {
00503
00504 int i = numbering_ [ii];
00505
00506 if ((Var (i) -> Multiplicity () > 0) &&
00507 (Var (i) -> Type () == AUX) &&
00508 (Var (i) -> Image () -> isInteger ()) &&
00509 (Var (i) -> sign () == expression::AUX_EQ))
00510 Var (i) -> setInteger (true);
00511
00512
00513
00514 }
00515
00516
00517
00518
00519
00520
00521
00522
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 delete [] commuted_; commuted_ = NULL;
00548 delete graph_; graph_ = NULL;
00549
00550 return retval;
00551 }