1 /* $Id$
2 *
3 * Name: CouenneFeasPumpConstructors.cpp
4 * Authors: Pietro Belotti
5 * Timo Berthold, ZIB Berlin
6 * Purpose: Constructors and service methods of the Feasibility Pump class
7 *
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include <string>
12
13 #include "CouenneConfig.h"
14 #include "CouenneFeasPump.hpp"
15 #include "CouenneFPpool.hpp"
16 #include "CouenneMINLPInterface.hpp"
17 #include "CouenneObject.hpp"
18 #include "CouenneProblemElem.hpp"
19 #include "CouenneProblem.hpp"
20 #include "CouenneExprClone.hpp"
21 #include "CouenneExprSub.hpp"
22 #include "CouenneExprPow.hpp"
23 #include "CouenneExprSum.hpp"
24 #include "CouenneTNLP.hpp"
25 #include "CouenneSparseMatrix.hpp"
26
27 using namespace Ipopt;
28 using namespace Couenne;
29
30 // common code for initializing ipopt application
initIpoptApp()31 void CouenneFeasPump::initIpoptApp () {
32
33 // Although app_ is only used in CouenneFPSolveNLP, we need to have
34 // an object lasting the program's lifetime as otherwise it appears
35 // to delete the nlp pointer at deletion.
36
37 if (!app_)
38 app_ = IpoptApplicationFactory ();
39
40 ApplicationReturnStatus status = app_ -> Initialize ();
41
42 app_ -> Options () -> SetIntegerValue ("max_iter", 1000);
43 app_ -> Options () -> SetIntegerValue // 0 for none, 4 for summary, 5 for iteration output
44 ("print_level", (problem_ -> Jnlst () -> ProduceOutput (J_ITERSUMMARY, J_NLPHEURISTIC) ? 4 :
45 problem_ -> Jnlst () -> ProduceOutput (J_MOREDETAILED, J_NLPHEURISTIC) ? 5 : 0));
46
47 app_ -> Options () -> SetStringValue ("fixed_variable_treatment", "make_parameter");
48
49 // Suppress iteration output from nonlinear solver
50 app_ -> Options () -> SetStringValue ("sb", "yes", false, true);
51
52 if (status != Solve_Succeeded)
53 printf ("FP: Error in initialization\n");
54 }
55
56
57 // Constructor //////////////////////////////////////////////////
CouenneFeasPump(CouenneProblem * couenne,CouenneCutGenerator * cg,Ipopt::SmartPtr<Ipopt::OptionsList> options)58 CouenneFeasPump::CouenneFeasPump (CouenneProblem *couenne,
59 CouenneCutGenerator *cg,
60 Ipopt::SmartPtr<Ipopt::OptionsList> options):
61 CbcHeuristic (),
62
63 problem_ (couenne),
64 couenneCG_ (cg),
65 nlp_ (NULL),
66 app_ (NULL),
67 milp_ (NULL),
68 postlp_ (NULL),
69 pool_ (NULL),
70
71 numberSolvePerLevel_ (5), // if options are not valid, don't overuse FP
72
73 multDistNLP_ (1.), // settings for classical FP
74 multHessNLP_ (0.),
75 multObjFNLP_ (0.),
76
77 multDistMILP_ (1.),
78 multHessMILP_ (0.),
79 multObjFMILP_ (0.),
80
81 compDistInt_ (FP_DIST_INT),
82 milpCuttingPlane_ (FP_CUT_NONE),
83 nSepRounds_ (0),
84 maxIter_ (COIN_INT_MAX),
85 useSCIP_ (false),
86 milpMethod_ (0),
87 tabuMgt_ (FP_TABU_NONE),
88 nCalls_ (0),
89 fadeMult_ (1) {
90
91 int compareTerm = INTEGER_VARS;
92
93 if (IsValid (options)) {
94
95 std::string s;
96
97 options -> GetIntegerValue ("feas_pump_iter", maxIter_, "couenne.");
98 options -> GetIntegerValue ("feas_pump_level", numberSolvePerLevel_, "couenne.");
99 options -> GetIntegerValue ("feas_pump_milpmethod", milpMethod_, "couenne.");
100
101 options -> GetNumericValue ("feas_pump_mult_dist_nlp", multDistNLP_, "couenne.");
102 options -> GetNumericValue ("feas_pump_mult_hess_nlp", multHessNLP_, "couenne.");
103 options -> GetNumericValue ("feas_pump_mult_objf_nlp", multObjFNLP_, "couenne.");
104
105 options -> GetNumericValue ("feas_pump_mult_dist_milp", multDistMILP_, "couenne.");
106 options -> GetNumericValue ("feas_pump_mult_hess_milp", multHessMILP_, "couenne.");
107 options -> GetNumericValue ("feas_pump_mult_objf_milp", multObjFMILP_, "couenne.");
108
109 options -> GetNumericValue ("feas_pump_fademult", fadeMult_, "couenne.");
110
111 options -> GetStringValue ("feas_pump_convcuts", s, "couenne.");
112
113 milpCuttingPlane_ =
114 (s == "none") ? FP_CUT_NONE :
115 (s == "integrated") ? FP_CUT_INTEGRATED :
116 (s == "postcut") ? FP_CUT_POST : FP_CUT_EXTERNAL;
117
118 options -> GetIntegerValue ("feas_pump_nseprounds", nSepRounds_, "couenne.");
119
120 options -> GetStringValue ("feas_pump_vardist", s, "couenne.");
121
122 compDistInt_ =
123 (s == "integer") ? FP_DIST_INT :
124 (s == "all") ? FP_DIST_ALL : FP_DIST_POST;
125
126 options -> GetIntegerValue ("feas_pump_milpmethod", milpMethod_, "couenne.");
127 options -> GetIntegerValue ("feas_pump_poolcomp", compareTerm, "couenne.");
128
129 options -> GetStringValue ("feas_pump_tabumgt", s, "couenne.");
130
131 tabuMgt_ =
132 (s == "pool") ? FP_TABU_POOL :
133 (s == "perturb") ? FP_TABU_PERTURB :
134 (s == "cut") ? FP_TABU_CUT : FP_TABU_NONE;
135
136 options -> GetStringValue ("feas_pump_usescip", s, "couenne.");
137
138 #ifdef COIN_HAS_SCIP
139 useSCIP_ = (s == "yes");
140 if (milpMethod_ < 0)
141 milpMethod_ = 0;
142 #else
143 if (s == "yes")
144 problem_ -> Jnlst () -> Printf (J_ERROR, J_COUENNE, "Warning: you have set feas_pump_usescip to true, but SCIP is not installed.\n");
145 #endif
146
147 }
148
149 pool_ = new CouenneFPpool (problem_, (enum what_to_compare) compareTerm);
150
151 //pool_ = new CouenneFPpool (SUM_NINF);
152 //pool_ = new CouenneFPpool (problem_, INTEGER_VARS);
153
154 setHeuristicName ("Couenne Feasibility Pump");
155
156 initIpoptApp ();
157 }
158
159
160 // Copy constructor /////////////////////////////////////////////
CouenneFeasPump(const CouenneFeasPump & other)161 CouenneFeasPump::CouenneFeasPump (const CouenneFeasPump &other)
162 {operator= (other);}
163
164
165 // Clone ////////////////////////////////////////////////////////
clone() const166 CbcHeuristic *CouenneFeasPump::clone () const
167 {return new CouenneFeasPump (*this);}
168
169
170 // Assignment operator //////////////////////////////////////////
operator =(const CouenneFeasPump & rhs)171 CouenneFeasPump &CouenneFeasPump::operator= (const CouenneFeasPump & rhs) {
172
173 if (this != &rhs) {
174
175 CbcHeuristic::operator= (rhs);
176
177 problem_ = rhs. problem_;
178 couenneCG_ = rhs. couenneCG_;
179 nlp_ = rhs. nlp_;
180 app_ = NULL;
181 milp_ = rhs. milp_ ? rhs. milp_ -> clone () : NULL;
182 postlp_ = rhs. postlp_ ? rhs. postlp_ -> clone () : NULL;
183 pool_ = NULL;
184
185 numberSolvePerLevel_ = rhs. numberSolvePerLevel_;
186
187 multDistNLP_ = rhs. multDistNLP_;
188 multHessNLP_ = rhs. multHessNLP_;
189 multObjFNLP_ = rhs. multObjFNLP_;
190
191 multDistMILP_ = rhs. multDistMILP_;
192 multHessMILP_ = rhs. multHessMILP_;
193 multObjFMILP_ = rhs. multObjFMILP_;
194
195 compDistInt_ = rhs. compDistInt_;
196 milpCuttingPlane_ = rhs. milpCuttingPlane_;
197 nSepRounds_ = rhs. nSepRounds_;
198 maxIter_ = rhs. maxIter_;
199 useSCIP_ = rhs. useSCIP_;
200 milpMethod_ = rhs. milpMethod_;
201 tabuMgt_ = rhs. tabuMgt_;
202 nCalls_ = rhs. nCalls_;
203 fadeMult_ = rhs. fadeMult_;
204
205 if (rhs. pool_)
206 pool_ = new CouenneFPpool (*(rhs. pool_));
207
208 for (std::set <CouenneFPsolution, compareSol>::const_iterator i = rhs.tabuPool_.begin ();
209 i != rhs.tabuPool_.end ();
210 ++i)
211 tabuPool_. insert (CouenneFPsolution (*i));
212
213 initIpoptApp ();
214 }
215
216 return *this;
217 }
218
219
220 // Destructor ///////////////////////////////////////////////////
~CouenneFeasPump()221 CouenneFeasPump::~CouenneFeasPump () {
222
223 if (pool_) delete pool_;
224 if (app_) delete app_;
225 if (milp_) delete milp_;
226 if (postlp_) delete postlp_;
227
228 //if (nlp_) delete nlp_; // already deleted by "delete app_;"
229 }
230
231
232 /// Set new expression as the NLP objective function using
233 /// argument as point to minimize distance from. Return new
234 /// objective function.
updateNLPObj(const double * iSol)235 expression *CouenneFeasPump::updateNLPObj (const double *iSol) {
236
237 expression **list = NULL;
238
239 int nTerms = 0;
240
241 const double *iS = iSol;
242
243 // TODO:
244 //
245 // 1) resize list
246 // 2) separate H norm from distance
247 // 3
248
249 if ((multHessNLP_ == 0.) ||
250 (nlp_ -> optHessian () == NULL)) {
251
252 list = new expression * [1 + problem_ -> nVars ()];
253
254 // here the objective function is ||x-x^0||_2^2
255
256 // create the argument list (x_i - x_i^0)^2 for all i's
257 for (int i=0; i<problem_ -> nVars (); ++i, ++iS) {
258
259 if (problem_ -> Var (i) -> Multiplicity () <= 0)
260 continue;
261
262 if (compDistInt_ == FP_DIST_INT &&
263 !(problem_ -> Var (i) -> isInteger ()))
264 continue;
265
266 expression *base;
267
268 if (*iS == 0.) base = new exprClone (problem_ -> Var (i));
269 else if (*iS < 0.) base = new exprSum (new exprClone (problem_ -> Var (i)), new exprConst (-*iS));
270 else base = new exprSub (new exprClone (problem_ -> Var (i)), new exprConst (*iS));
271
272 list [nTerms++] = new exprPow (base, new exprConst (2.));
273 }
274
275 } else {
276
277 // possibly a much larger set of operands
278
279 list = new expression * [problem_ -> nVars () *
280 problem_ -> nVars ()];
281
282 // here the objective function is
283 //
284 // ||P(x-x^0)||_2^2 = (x-x^0)' P'P (x-x^0)
285 //
286 // with P'P positive semidefinite stored in CouenneTNLP::optHessian_
287
288 // P is a convex combination, with weights multDistMILP_ and
289 // multHessMILP_, of the distance and the Hessian respectively
290
291 int *row = nlp_ -> optHessian () -> row ();
292 int *col = nlp_ -> optHessian () -> col ();
293 double *val = nlp_ -> optHessian () -> val ();
294
295 int num = nlp_ -> optHessian () -> num ();
296
297 double
298 trace_H = 0,
299 nActualTerms = 0;
300
301 // create the argument list (x_i - x_i^0)^2 for all i's
302 for (int i=0; i<problem_ -> nVars (); ++i)
303 if (!((problem_ -> Var (i) -> Multiplicity () <= 0) ||
304 (compDistInt_ == FP_DIST_INT &&
305 !(problem_ -> Var (i) -> isInteger ()))))
306 nActualTerms += 1;
307
308 nActualTerms = (nActualTerms == 0) ? 1 : (1 / sqrt (nActualTerms));
309
310 // Add Hessian part -- only lower triangular part
311 for (int i=0; i<num; ++i, ++val)
312 if (*row++ == *col++)
313 trace_H += *val * *val;
314
315 trace_H = (trace_H < COUENNE_EPS) ? 1 : (1 / sqrt (trace_H));
316
317 row = nlp_ -> optHessian () -> row ();
318 col = nlp_ -> optHessian () -> col ();
319 val = nlp_ -> optHessian () -> val ();
320
321 // Add Hessian part -- only lower triangular part
322 for (int i=0; i<num; ++i, ++row, ++col, ++val) {
323
324 if ((problem_ -> Var (*row) -> Multiplicity () <= 0) ||
325 (problem_ -> Var (*col) -> Multiplicity () <= 0))
326 continue;
327
328 // check if necessary given options
329
330 if (compDistInt_ == FP_DIST_INT &&
331 !(problem_ -> Var (*row) -> isInteger () &&
332 problem_ -> Var (*col) -> isInteger ()))
333 continue;
334
335 // second, only do subdiagonal elements
336
337 if (*col < *row) { // that is, lower triangular
338
339 if (2. * *val * trace_H == 1.) // check if this would have trivial coefficient when doubled (off-diagonal element)
340
341 list [nTerms++] = new exprMul (new exprSub (new exprClone (problem_ -> Var (*row)), new exprConst (iSol [*row])),
342 new exprSub (new exprClone (problem_ -> Var (*col)), new exprConst (iSol [*col])));
343
344 else if (fabs (*val * trace_H) > COUENNE_EPS) { // we don't need extreme precision...
345
346 expression **mlist = new expression * [3];
347
348 mlist [0] = new exprConst (2. * *val * trace_H); // twice elements off diagonal
349 mlist [1] = new exprSub (new exprClone (problem_ -> Var (*row)), new exprConst (iSol [*row]));
350 mlist [2] = new exprSub (new exprClone (problem_ -> Var (*col)), new exprConst (iSol [*col]));
351
352 list [nTerms++] = new exprMul (mlist, 3);
353 }
354
355 } else if (*col == *row) { // or diagonal elements
356
357 //if (multDistNLP_ != 0.)
358 //diag [*col] = true;
359
360 if (trace_H * *val + multDistNLP () * nActualTerms == 1.) // the plus is for the distance term
361
362 list [nTerms++] = new exprPow (new exprSub (new exprClone (problem_ -> Var (*row)),
363 new exprConst (iSol [*row])),
364 new exprConst (2.));
365
366 else if (fabs (trace_H * *val + nActualTerms * multDistNLP ()) > COUENNE_EPS)
367
368 list [nTerms++] = new exprMul (new exprConst (trace_H * *val + nActualTerms * multDistNLP ()),
369 new exprPow (new exprSub (new exprClone (problem_ -> Var (*row)),
370 new exprConst (iSol [*row])),
371 new exprConst (2.)));
372 }
373 }
374
375 // third, add missing diagonal elements. NO! Already added above (fewer terms)
376 /*
377 if (multDistNLP () > 0.) {
378
379 // create the argument list (x_i - x_i^0)^2 for all i's
380 for (int i=0; i<problem_ -> nVars (); ++i, ++iS) {
381
382 if (problem_ -> Var (i) -> Multiplicity () <= 0)
383 continue;
384
385 if ((compDistInt_ == FP_DIST_INT &&
386 !(problem_ -> Var (i) -> isInteger ())) ||
387 diag [i])
388 continue;
389
390 expression *base;
391
392 if (*iS == 0.) base = new exprClone (problem_ -> Var (i));
393 else if (*iS < 0.) base = new exprSum (new exprClone (problem_ -> Var (i)), new exprConst (-*iS));
394 else base = new exprSub (new exprClone (problem_ -> Var (i)), new exprConst (*iS));
395
396 base = new exprMul (base, new exprConst (nActualTerms));
397
398 list [nTerms++] = new exprPow (base, new exprConst (2.));
399 }
400
401 delete [] diag;
402 } */
403 }
404
405 // as per latest development: objective is multiplied by one to
406 // normalize it with distance and Hessian-based objective
407
408 if (multObjFNLP () != 0.)
409 list [nTerms++] = new exprMul (new exprConst (multObjFNLP ()),
410 new exprClone (problem_ -> Obj (0) -> Body ()));
411
412 // resize list
413
414 expression **tmp = list;
415 list = CoinCopyOfArray (tmp, nTerms);
416 delete [] tmp;
417
418 expression *retexpr = new exprSum (list, nTerms);
419
420 // printf ("new objective: "); retexpr -> print (); printf ("\n");
421
422 return retexpr;
423 }
424
425
426 /// Reads a (possibly fractional) solution and fixes the integer
427 /// components in the nonlinear problem for later re-solve
fixIntVariables(const double * sol)428 bool CouenneFeasPump::fixIntVariables (const double *sol) {
429
430 assert (sol);
431
432 t_chg_bounds *chg_bds = new t_chg_bounds [problem_ -> nVars ()];
433
434 for (int i = problem_ -> nVars (); i--;)
435
436 if ((problem_ -> Var (i) -> isInteger ()) &&
437 (problem_ -> Var (i) -> Multiplicity () > 0)) {
438
439 double
440 value = sol [i],
441 rUp = ceil (value - COUENNE_EPS),
442 rDn = floor (value + COUENNE_EPS);
443
444 // If numerics or sol[i] fractional, set to closest
445
446 value =
447 (rUp < rDn + 0.5) ? rUp :
448 (rUp - value < value - rDn) ? rUp : rDn;
449
450 #define INT_NLP_BRACKET 1e-6
451
452 problem_ -> Lb (i) = value - INT_NLP_BRACKET;
453 problem_ -> Ub (i) = value + INT_NLP_BRACKET;
454
455 chg_bds [i].setLower (t_chg_bounds::CHANGED);
456 chg_bds [i].setUpper (t_chg_bounds::CHANGED);
457 }
458
459 // Now, to restrict the bounding box even more (and hopefully make
460 // it easier) apply BT
461
462 bool retval = problem_ -> btCore (chg_bds); // maybe fixing makes the nlp infeasible
463
464 delete [] chg_bds;
465
466 return retval;
467 }
468
469
470 /// initialize options
registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)471 void CouenneFeasPump::registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions) {
472
473 roptions -> AddStringOption4
474 ("feas_pump_heuristic",
475 "Apply the nonconvex Feasibility Pump",
476 "no",
477 "no", "never called",
478 "yes", "called any time Cbc calls heuristics",
479 "once", "call it at most once",
480 "only", "Call it exactly once and then exit",
481 "An implementation of the Feasibility Pump for nonconvex MINLPs");
482
483 roptions -> AddBoundedNumberOption
484 ("feas_pump_fademult",
485 "decrease/increase rate of multipliers",
486 0, false,
487 1, false,
488 1, "1 keeps initial multipliers from one call to the next; any <1 multiplies ALL of them");
489
490 roptions -> AddLowerBoundedIntegerOption
491 ("feas_pump_level",
492 "Specify the logarithm of the number of feasibility pumps to perform"
493 " on average for each level of given depth of the tree.",
494 -1,
495 3, "Solve as many nlp's at the nodes for each level of the tree. "
496 "Nodes are randomly selected. If for a "
497 "given level there are less nodes than this number nlp are solved for every nodes. "
498 "For example, if parameter is 8 NLPs are solved for all node until level 8, "
499 "then for half the node at level 9, 1/4 at level 10.... "
500 "Set to -1 to perform at all nodes.");
501
502 roptions -> AddLowerBoundedIntegerOption
503 ("feas_pump_iter",
504 "Number of iterations in the main Feasibility Pump loop (default: 10)",
505 -1,
506 10, "-1 means no limit");
507
508 // six options
509
510 char option [40];
511 char help [250];
512
513 std::string terms [] = {"dist", "hess", "objf"};
514 std::string types [] = {"nlp", "milp"};
515
516 for (int j=0; j<3; j++)
517 for (int i=0; i<2; i++) {
518
519 sprintf (option, "feas_pump_mult_%s_%s", terms [j].c_str (), types [i].c_str ());
520 sprintf (help, "Weight of the %s in the distance function of the %s problem",
521 !(strcmp ("dist", terms [j].c_str ())) ? "distance" :
522 !(strcmp ("hess", terms [j].c_str ())) ? "Hessian" : "original objective function", types [i].c_str ());
523
524 roptions -> AddBoundedNumberOption
525 (option, help,
526 -1., true,
527 +1., false,
528 0., "0: neglected; 1: full weight; a in ]0,1[: weight is a^k where k is the FP iteration; a in ]-1,0[: weight is 1-|a|^k");
529 }
530
531 roptions -> AddStringOption3
532 ("feas_pump_vardist",
533 "Distance computed on integer-only or on both types of variables, in different flavors.",
534 "integer",
535 "integer", "Only compute the distance based on integer coordinates (use post-processing if numerical errors occur)",
536 "all", "Compute the distance using continuous and integer variables",
537 "int-postprocess", "Use a post-processing fixed-IP LP to determine a closest-point solution");
538
539 roptions -> AddStringOption4
540 ("feas_pump_convcuts",
541 "Separate MILP-feasible, MINLP-infeasible solution during or after MILP solver.",
542 "none",
543 "integrated", "Done within the MILP solver in a branch-and-cut fashion",
544 "external", "Done after the MILP solver, in a Benders-like fashion",
545 "postcut", "Do one round of cuts and proceed with NLP",
546 "none", "Just proceed to the NLP");
547
548 roptions -> AddBoundedIntegerOption
549 ("feas_pump_nseprounds",
550 "Number of rounds of convexification cuts. Must be at least 1",
551 1, 1e5, 4,
552 "");
553
554 roptions -> AddStringOption4
555 ("feas_pump_tabumgt",
556 "Retrieval of MILP solutions when the one returned is unsatisfactory",
557 "pool",
558 "pool", "Use a solution pool and replace unsatisfactory solution with Euclidean-closest in pool",
559 "perturb", "Randomly perturb unsatisfactory solution",
560 "cut", "Separate convexification cuts",
561 "none", "Bail out of feasibility pump");
562
563 roptions -> AddStringOption2
564 ("feas_pump_usescip",
565 "Should SCIP be used to solve the MILPs?",
566 #ifdef COIN_HAS_SCIP
567 "yes", // we want it by default if SCIP is available
568 #else
569 "no", // otherwise switch it off and warn the user if turned on
570 #endif
571 "no", "Use Cbc's branch-and-cut to solve the MILP",
572 "yes", "Use SCIP's branch-and-cut or heuristics (see feas_pump_milpmethod option) to solve the MILP",
573 "");
574
575 roptions -> AddBoundedIntegerOption
576 ("feas_pump_milpmethod",
577 "How should the integral solution be constructed?",
578 -1, 6, 0,
579 "0: automatic, 1: aggressive heuristics, large node limit, 2: default, node limit, 3: RENS, 4: Objective Feasibility Pump, 5: MINLP rounding heuristic, 6: rounding, -1: solve MILP completely");
580
581 roptions -> AddBoundedIntegerOption
582 ("feas_pump_poolcomp",
583 "Priority field to compare solutions in FP pool",
584 0, 4, 4,
585 "\
586 0: total number of infeasible objects (integer and nonlinear); \
587 1: maximum infeasibility (integer or nonlinear); \
588 2: objective value; \
589 3: compare value of all variables; \
590 4: compare value of all integers (RECOMMENDED).");
591 }
592