00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include <vector>
00012
00013 #include "CoinHelperFunctions.hpp"
00014 #include "CoinTime.hpp"
00015
00016 #include "CouenneTypes.hpp"
00017
00018 #include "expression.hpp"
00019 #include "exprConst.hpp"
00020 #include "exprGroup.hpp"
00021 #include "exprClone.hpp"
00022 #include "exprAux.hpp"
00023 #include "lqelems.hpp"
00024 #include "CouenneProblem.hpp"
00025 #include "CouenneProblemElem.hpp"
00026 #include "lqelems.hpp"
00027
00028
00029 const CouNumber SafeCutoff = 1e-4;
00030
00033
00034 void CouenneProblem::initAuxs () const {
00035
00036 domain_.current () -> resize (nVars ());
00037
00038
00039
00040
00041 int nvars = nVars ();
00042
00043 for (int i=0; i < nvars; i++) {
00044
00045 int indvar = variables_ [i] -> Index ();
00046
00047 if ((variables_ [i] -> Type () == AUX) &&
00048 (indvar >= nOrigVars_) ||
00049 (variables_ [i] -> Multiplicity () == 0))
00050
00051 Lb (indvar) = - (Ub (indvar) = COIN_DBL_MAX);
00052 }
00053
00054
00055
00056
00057
00058 for (std::vector <CouenneConstraint *>::const_iterator con = constraints_.begin ();
00059 con != constraints_.end (); ++con) {
00060
00061 CouNumber
00062 lb = (*((*con) -> Lb ())) (),
00063 ub = (*((*con) -> Ub ())) ();
00064
00065 int index = (*con) -> Body () -> Index ();
00066
00067 assert (index >= 0);
00068
00069 if ((Lb (index) = CoinMax (Lb (index), lb)) <= -COUENNE_INFINITY) Lb (index) = -COIN_DBL_MAX;
00070 if ((Ub (index) = CoinMin (Ub (index), ub)) >= COUENNE_INFINITY) Ub (index) = COIN_DBL_MAX;
00071 }
00072
00073
00074
00075
00076 Jnlst () -> Printf (Ipopt::J_MOREMATRIX, J_PROBLEM, "InitAux -- assigning bounds\n");
00077
00078 for (int j=0, i=nVars (); i--; j++) {
00079
00080 int ord = numbering_ [j];
00081
00082
00083 if (variables_ [ord] -> Multiplicity () == 0) {
00084 Lb (ord) = - (Ub (ord) = COIN_DBL_MAX);
00085 X (ord) = 0.;
00086 continue;
00087 }
00088
00089
00090 if (variables_ [ord] -> Type () == AUX) {
00091
00092 Jnlst () -> Printf (Ipopt::J_MOREMATRIX, J_PROBLEM,
00093 "w_%04d [%10g,%10g] ", ord, Lb (ord), Ub (ord));
00094
00095 CouNumber l, u;
00096
00097 variables_ [ord] -> Image () -> getBounds (l, u);
00098
00099
00100
00101
00102
00103 Jnlst () -> Printf (Ipopt::J_MOREMATRIX, J_PROBLEM,
00104 " ( --> w_%04d [%10g,%10g] ) vs [%10g %10g]",
00105 ord, l, u, Lb (ord), Ub (ord));
00106
00107
00108 if ((Lb (ord) = CoinMax (Lb (ord), l)) <= -COUENNE_INFINITY) Lb (ord) = -COIN_DBL_MAX;
00109 if ((Ub (ord) = CoinMin (Ub (ord), u)) >= COUENNE_INFINITY) Ub (ord) = COIN_DBL_MAX;
00110
00111
00112
00113 Jnlst () -> Printf (Ipopt::J_MOREMATRIX, J_PROBLEM,
00114 " --> [%10g,%10g]\n", Lb (ord), Ub (ord));
00115
00116 bool integer = variables_ [ord] -> isInteger ();
00117
00118 if (integer) {
00119 Lb (ord) = ceil (Lb (ord) - COUENNE_EPS);
00120 Ub (ord) = floor (Ub (ord) + COUENNE_EPS);
00121 }
00122
00123 X (ord) = CoinMax (Lb (ord), CoinMin (Ub (ord), (*(variables_ [ord] -> Image ())) ()));
00124 }
00125 }
00126
00127 restoreUnusedOriginals ();
00128 }
00129
00130
00133 void CouenneProblem::getAuxs (CouNumber * x) const {
00134
00135
00136 domain_.push (nVars (), x, domain_.lb (), domain_.ub (), false);
00137
00138
00139
00140
00141
00142
00143 for (int j=0, i=nVars (); i--; j++) {
00144
00145 int index = numbering_ [j];
00146 exprVar *var = variables_ [index];
00147
00148 if (var -> Multiplicity () > 0) {
00149
00150 CouNumber l, u;
00151
00152 if (var -> Type () == AUX)
00153 var -> Image () -> getBounds (l,u);
00154 else {
00155 l = Lb (index);
00156 u = Ub (index);
00157 }
00158
00159 if (var -> Type () == AUX) {
00160 X (index) =
00161 CoinMax (l, CoinMin (u, (*(var -> Image ())) ()));
00162 }
00163 } else X (index) = 0.;
00164 }
00165
00166 restoreUnusedOriginals ();
00167
00168 domain_.pop ();
00169 }
00170
00171
00174
00175 void CouenneProblem::fillObjCoeff (double *&obj) {
00176
00177
00178
00179
00180
00181 expression *body = objectives_ [0] -> Body ();
00182
00183
00184 switch (body -> code ()) {
00185
00186 case COU_EXPRVAR:
00187 obj [body -> Index ()] = 1;
00188 break;
00189
00190 case COU_EXPRSUB: {
00191
00192 expression **arglist = body -> ArgList ();
00193
00194 obj [arglist [0] -> Index ()] = 1;
00195 obj [arglist [1] -> Index ()] = -1;
00196
00197 } break;
00198
00199 case COU_EXPRGROUP: {
00200
00201 exprGroup *eg = dynamic_cast <exprGroup *> (body -> isaCopy () ?
00202 body -> Copy () :
00203 body);
00204
00205 const exprGroup::lincoeff &lcoe = eg -> lcoeff ();
00206
00207
00208
00209
00210 for (int n = lcoe.size (), i=0; n--; i++)
00211
00212 obj [lcoe [i]. first -> Index ()] = lcoe [i]. second;
00213
00214
00215
00216
00217 }
00218
00219 case COU_EXPRSUM: {
00220
00221 expression **arglist = body -> ArgList ();
00222
00223 for (int i = body -> nArgs (); i--;)
00224 switch ((arglist [i]) -> code ()) {
00225
00226 case COU_EXPRCONST:
00227 break;
00228
00229 case COU_EXPRVAR:
00230 obj [arglist [i] -> Index ()] = 1;
00231 break;
00232
00233 case COU_EXPRMUL: {
00234
00235 expression **mulArgList = arglist [i] -> ArgList ();
00236 int index = mulArgList [0] -> Index ();
00237
00238 if (index >= 0) obj [index] = mulArgList [1] -> Value ();
00239 else obj [mulArgList [1] -> Index ()] = mulArgList [0] -> Value ();
00240 } break;
00241
00242 default:
00243 Jnlst()->Printf(Ipopt::J_ERROR, J_PROBLEM,
00244 "Couenne: invalid element of sum\nAborting\n");
00245 exit (-1);
00246 }
00247 } break;
00248
00249 case COU_EXPRCONST: break;
00250
00251 default:
00252 Jnlst()->Printf(Ipopt::J_WARNING, J_PROBLEM,
00253 "Couenne: warning, objective function not recognized\n");
00254 break;
00255 }
00256 }
00257
00258
00260 void CouenneProblem::setCutOff (CouNumber cutoff) const {
00261
00262 int indobj = objectives_ [0] -> Body () -> Index ();
00263
00264
00265
00266 if ((indobj >= 0) && (cutoff < pcutoff_ -> getCutOff () - COUENNE_EPS)) {
00267
00268 Jnlst () -> Printf (Ipopt::J_DETAILED, J_PROBLEM,
00269 "Setting new cutoff %.10e for optimization variable index %d val = %.10e\n",
00270 cutoff, indobj,
00271 pcutoff_ -> getCutOff ());
00272
00273 if (Var (indobj) -> isInteger ())
00274 pcutoff_ -> setCutOff (floor (cutoff + COUENNE_EPS));
00275 else pcutoff_ -> setCutOff (cutoff + SafeCutoff * (1. + fabs(cutoff)));
00276 }
00277 }
00278
00279
00282 void CouenneProblem::installCutOff () const {
00283
00284 int indobj = objectives_ [0] -> Body () -> Index ();
00285
00286 if (indobj >= 0) {
00287
00288
00289 double cutoff = pcutoff_ -> getCutOff();
00290
00291 if (cutoff < Ub (indobj))
00292 Ub (indobj) = cutoff;
00293
00294 } else jnlst_ -> Printf (J_SUMMARY, J_PROBLEM,
00295 "Warning, could not install cutoff - negative objective index\n");
00296 }
00297
00298
00299
00300 void CouenneProblem::realign () {
00301
00302
00303 for (std::vector <exprVar *>::iterator i = variables_.begin ();
00304 i != variables_.end (); ++i) {
00305
00306 (*i) -> linkDomain (&domain_);
00307 (*i) -> realign (this);
00308 if ((*i) -> Type () == AUX)
00309 (*i) -> Image () -> realign (this);
00310 }
00311
00312
00313 for (std::vector <CouenneObjective *>::iterator i = objectives_.begin ();
00314 i != objectives_.end (); ++i)
00315 (*i) -> Body () -> realign (this);
00316
00317
00318
00319 for (std::vector <CouenneConstraint *>::iterator i = constraints_.begin ();
00320 i != constraints_.end (); ++i)
00321 (*i) -> Body () -> realign (this);
00322 }
00323
00324
00326 void CouenneProblem::registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions) {
00327
00328 roptions -> SetRegisteringCategory ("Couenne options", Bonmin::RegisteredOptions::CouenneCategory);
00329
00330 roptions -> AddNumberOption
00331 ("art_cutoff",
00332 "Artificial cutoff",
00333 COIN_DBL_MAX,
00334 "Default value is infinity.");
00335
00336 roptions -> AddNumberOption
00337 ("opt_window",
00338 "Window around known optimum",
00339 COIN_DBL_MAX,
00340 "Default value is infinity.");
00341
00342 roptions -> AddNumberOption
00343 ("feas_tolerance",
00344 "Tolerance for constraints/auxiliary variables",
00345 feas_tolerance_default,
00346 "Default value is zero.");
00347
00348 roptions -> AddStringOption2
00349 ("feasibility_bt",
00350 "Feasibility-based (cheap) bound tightening (FBBT)",
00351 "yes",
00352 "no","",
00353 "yes","",
00354 "A pre-processing technique to reduce the bounding box, before the generation of linearization cuts. "
00355 "This is a quick and effective way to reduce the solution set, and it is highly recommended to keep it active."
00356 );
00357
00358 roptions -> AddStringOption2
00359 ("redcost_bt",
00360 "Reduced cost bound tightening",
00361 "yes",
00362 "no","",
00363 "yes","",
00364 "This bound reduction technique uses the reduced costs of the LP in order to infer better variable bounds.");
00365
00366 roptions -> AddStringOption2
00367 ("use_quadratic",
00368 "Use quadratic expressions and related exprQuad class",
00369 "no",
00370 "no","Use an auxiliary for each bilinear term",
00371 "yes","Create only one auxiliary for a quadratic expression",
00372 "If enabled, then quadratic forms are not reformulated and therefore decomposed as a sum of auxiliary variables, each associated with a bilinear term, but rather taken as a whole expression. "
00373 "Envelopes for these expressions are generated through alpha-convexification."
00374 );
00375
00376 roptions -> AddStringOption2
00377 ("optimality_bt",
00378 "Optimality-based (expensive) bound tightening (OBBT)",
00379 "yes",
00380 "no","",
00381 "yes","",
00382 "This is another bound reduction technique aiming at reducing the solution set by looking at the initial LP relaxation. "
00383 "This technique is computationally expensive, and should be used only when necessary."
00384 );
00385
00386 roptions -> AddLowerBoundedIntegerOption
00387 ("log_num_obbt_per_level",
00388 "Specify the frequency (in terms of nodes) for optimality-based bound tightening.",
00389 -1,1,
00390 "\
00391 If -1, apply at every node (expensive!). \
00392 If 0, apply at root node only. \
00393 If k>=0, apply with probability 2^(k - level), level being the current depth of the B&B tree.");
00394
00395 roptions -> AddStringOption2
00396 ("aggressive_fbbt",
00397 "Aggressive feasibility-based bound tightening (to use with NLP points)",
00398 "yes",
00399 "no","",
00400 "yes","",
00401 "Aggressive FBBT is a version of probing that also allows to reduce the solution set, although it is not as quick as FBBT. "
00402 "It can be applied up to a certain depth of the B&B tree -- see ``log_num_abt_per_level''. "
00403 "In general, this option is useful but can be switched off if a problem is too large and seems not to benefit from it."
00404 );
00405
00406 roptions -> AddLowerBoundedIntegerOption
00407 ("log_num_abt_per_level",
00408 "Specify the frequency (in terms of nodes) for aggressive bound tightening.",
00409 -1,2,
00410 "\
00411 If -1, apply at every node (expensive!). \
00412 If 0, apply at root node only. \
00413 If k>=0, apply with probability 2^(k - level), level being the current depth of the B&B tree.");
00414
00415 roptions -> AddNumberOption
00416 ("art_lower",
00417 "Artificial lower bound",
00418 -COIN_DBL_MAX,
00419 "Default value is -COIN_DBL_MAX.");
00420
00421 roptions -> AddStringOption3
00422 ("branching_object",
00423 "type of branching object for variable selection",
00424 "var_obj",
00425 "vt_obj", "use Violation Transfer from Tawarmalani and Sahinidis",
00426 "var_obj", "use one object for each variable",
00427 "expr_obj", "use one object for each nonlinear expression");
00428
00429 roptions -> AddStringOption2
00430 ("delete_redundant",
00431 "Eliminate redundant variables, which appear in the problem as x_k = x_h",
00432 "yes",
00433 "no","Keep redundant variables, making the problem a bit larger",
00434 "yes","Eliminate redundant variables (the problem will be equivalent, only smaller)");
00435 }