1 // $Id$
2 //
3 // (C) Copyright International Business Machines Corporation 2007
4 // All Rights Reserved.
5 // This code is published under the Eclipse Public License (EPL).
6 //
7 // Authors :
8 // Pierre Bonami, International Business Machines Corporation
9 // Pietro Belotti, Clemson University
10 //
11 // Date : 04/18/2007
12
13 // Ampl includes
14
15 #include "CouenneConfig.h"
16
17 #include "OsiClpSolverInterface.hpp"
18
19 #ifdef COIN_HAS_CPX
20 #include "OsiCpxSolverInterface.hpp"
21 #endif
22 #ifdef COIN_HAS_GRB
23 #include "OsiGrbSolverInterface.hpp"
24 #endif
25 #ifdef COIN_HAS_SPX
26 #include "OsiSpxSolverInterface.hpp"
27 #endif
28 #ifdef COIN_HAS_XPR
29 #include "OsiXprSolverInterface.hpp"
30 #endif
31
32 // MILP cuts
33 #include "CglGomory.hpp"
34 #include "CglProbing.hpp"
35 #include "CglKnapsackCover.hpp"
36 #include "CglOddHole.hpp"
37 #include "CglClique.hpp"
38 #include "CglFlowCover.hpp"
39 #include "CglMixedIntegerRounding2.hpp"
40 #include "CglTwomir.hpp"
41 #include "CglPreProcess.hpp"
42 #include "CglLandP.hpp"
43 #include "CglRedSplit.hpp"
44
45 #include "BonCouenneSetup.hpp"
46 #include "CouenneFeasPump.hpp"
47 #include "CouenneIterativeRounding.hpp"
48 #include "BonCouenneInterface.hpp"
49 #include "BonInitHeuristic.hpp"
50 #include "BonNlpHeuristic.hpp"
51
52 #include "BonFixAndSolveHeuristic.hpp"
53 #include "BonDummyPump.hpp"
54 #include "BonPumpForMinlp.hpp"
55 #include "BonHeuristicRINS.hpp"
56 #include "BonHeuristicLocalBranching.hpp"
57 #include "BonHeuristicFPump.hpp"
58 #include "BonHeuristicDiveFractional.hpp"
59 #include "BonHeuristicDiveVectorLength.hpp"
60 #include "BonHeuristicDiveMIPFractional.hpp"
61 #include "BonHeuristicDiveMIPVectorLength.hpp"
62 #include "BonMilpRounding.hpp"
63
64 #include "BonGuessHeuristic.hpp"
65 #include "CbcCompareActual.hpp"
66
67 #include "CouenneObject.hpp"
68 #include "CouenneVarObject.hpp"
69 #include "CouenneVTObject.hpp"
70 #include "CouenneOrbitObj.hpp"
71 #include "CouenneChooseVariable.hpp"
72 #include "CouenneChooseStrong.hpp"
73 #include "CouenneSolverInterface.hpp"
74 #include "CouenneFixPoint.hpp"
75 #include "CouenneCutGenerator.hpp"
76 #include "CouenneDisjCuts.hpp"
77 #include "CouenneCrossConv.hpp"
78 #include "CouenneSdpCuts.hpp"
79 #include "CouenneTwoImplied.hpp"
80
81 #include "BonCouenneInfo.hpp"
82 #include "BonCbcNode.hpp"
83 #include "BonCbc.hpp"
84
85 // ASL includes need to come behind OsiClp and Bonmin, because it defines "filename",
86 // which is used as variablename in Clp
87 // (similar bad as windows.h, which defines "small")
88 #ifdef COIN_HAS_ASL
89 #include "asl.h"
90 #include "getstub.h"
91 #endif
92
93 using namespace Ipopt;
94 using namespace Couenne;
95
~CouenneSetup()96 CouenneSetup::~CouenneSetup(){
97 if (couenneProb_ && couenneProb_is_own_)
98 delete couenneProb_;
99
100 #ifdef COIN_HAS_ASL
101 // free (aslfg_ -> asl); // triggers segfault -- apparently freed in ancestor class
102 #endif
103 }
104
InitializeCouenne(char ** argv,CouenneProblem * couenneProb,Ipopt::SmartPtr<Bonmin::TMINLP> tminlp,CouenneInterface * ci,Bonmin::Bab * bb)105 bool CouenneSetup::InitializeCouenne (char ** argv,
106 CouenneProblem *couenneProb,
107 Ipopt::SmartPtr<Bonmin::TMINLP> tminlp,
108 CouenneInterface *ci,
109 Bonmin::Bab *bb) {
110 int freq;
111
112 bool retval = true;
113
114 std::string s;
115
116 if (couenneProb) {
117 //TODO create a copy of user problem, since we modify it?
118 couenneProb_ = couenneProb;
119 couenneProb_is_own_ = false;
120 }
121
122 /* Get the basic options. */
123 readOptionsFile();
124
125 // Suppress iteration output from nonlinear solver
126 options () -> SetStringValue ("sb", "yes", false, true);
127
128 // in check mode, avoid pop-up error message (there are quite a few messages)
129 //options_ -> GetStringValue ("test_mode", s, "couenne.");
130 //if (s == "yes")
131 //WindowsErrorPopupBlocker();
132
133 /** Change default value for failure behavior so that code doesn't crash
134 when Ipopt does not solve a sub-problem.*/
135
136 options_ -> SetStringValue ("nlp_failure_behavior", "fathom", "couenne.");
137
138 gatherParametersValues (options_);
139
140 if (!ci) {
141
142 ci = new CouenneInterface;
143
144 if (!couenneProb_ && argv) {
145 #ifdef COIN_HAS_ASL
146 /* Read the model in various places. */
147 ci -> readAmplNlFile (argv, roptions (), options (), journalist ());
148 aslfg_ = new SmartAsl;
149 aslfg_ -> asl = readASLfg (argv);
150 #else
151 std::cerr <<
152 "Couenne was compiled without AMPL Solver Library. Cannot initialize from AMPL NL File."
153 << std::endl;
154 exit (-1);
155 #endif
156 } else {
157 assert (couenneProb_ != NULL);
158 assert (IsValid (tminlp)); //TODO would be great to setup own TMINLP based on CouenneProblem formulation
159 ci -> initialize (roptions_, options_, journalist_,
160 Ipopt::SmartPtr <Bonmin::TMINLP> (dynamic_cast <Bonmin::TMINLP *> (Ipopt::GetRawPtr (tminlp))));
161 }
162 }
163
164 nonlinearSolver_ = ci;
165
166 /** Set the output level of the journalist for all Couenne
167 categories. We probably want to make that a bit more flexible
168 later. */
169
170 int i;
171
172 /// trying to avoid repetitions here...
173
174 #define addJournalist(optname,jlevel) { \
175 options () -> GetIntegerValue ((optname), i, "couenne."); \
176 journalist () -> GetJournal ("console") -> SetPrintLevel ((jlevel), (EJournalLevel) i); \
177 }
178
179 addJournalist ("output_level", J_COUENNE);
180 addJournalist ("boundtightening_print_level", J_BOUNDTIGHTENING);
181 addJournalist ("branching_print_level", J_BRANCHING);
182 addJournalist ("convexifying_print_level", J_CONVEXIFYING);
183 addJournalist ("problem_print_level", J_PROBLEM);
184 addJournalist ("nlpheur_print_level", J_NLPHEURISTIC);
185 addJournalist ("disjcuts_print_level", J_DISJCUTS);
186 addJournalist ("reformulate_print_level", J_REFORMULATE);
187
188 options_ -> SetIntegerValue ("print_level", 0);
189
190 /* Initialize Couenne cut generator.*/
191 //int ivalue, num_points;
192 //options()->GetEnumValue("convexification_type", ivalue,"couenne.");
193 //options()->GetIntegerValue("convexification_points",num_points,"couenne.");
194
195 if (!couenneProb_)
196 couenneProb_ = new CouenneProblem (aslfg_ -> asl, this, journalist ());
197
198 CouenneCutGenerator * couenneCg =
199 new CouenneCutGenerator (ci, this, couenneProb_, NULL);
200
201 options_ -> GetStringValue ("lp_solver", s, "couenne.");
202
203 if (s == "clp") {
204
205 CouenneSolverInterface <OsiClpSolverInterface> *CSI = new CouenneSolverInterface <OsiClpSolverInterface>;
206 continuousSolver_ = CSI;
207 CSI -> setCutGenPtr (couenneCg);
208
209 } else if (s == "cplex") {
210
211 #ifdef COIN_HAS_CPX
212 CouenneSolverInterface <OsiCpxSolverInterface> *CSI = new CouenneSolverInterface <OsiCpxSolverInterface>;
213 continuousSolver_ = CSI;
214 CSI -> setCutGenPtr (couenneCg);
215 #else
216 journalist()->Printf(J_ERROR, J_INITIALIZATION, "Couenne was compiled without CPLEX interface. Please reconfigure, recompile, and try again.\n");
217 exit (-1);
218 #endif
219 } else if (s == "xpress-mp") {
220
221 #ifdef COIN_HAS_XPR
222 CouenneSolverInterface <OsiXprSolverInterface> *CSI = new CouenneSolverInterface <OsiXprSolverInterface>;
223 continuousSolver_ = CSI;
224 CSI -> setCutGenPtr (couenneCg);
225 #else
226 journalist()->Printf(J_ERROR, J_INITIALIZATION, "Couenne was compiled without Xpress-MP interface. Please reconfigure, recompile, and try again.\n");
227 exit (-1);
228 #endif
229 } else if (s == "gurobi") {
230
231 #ifdef COIN_HAS_GRB
232 CouenneSolverInterface <OsiGrbSolverInterface> *CSI = new CouenneSolverInterface <OsiGrbSolverInterface>;
233 continuousSolver_ = CSI;
234 CSI -> setCutGenPtr (couenneCg);
235 #else
236 journalist()->Printf(J_ERROR, J_INITIALIZATION, "Couenne was compiled without GUROBI interface. Please reconfigure, recompile, and try again.\n");
237 exit (-1);
238 #endif
239 } else if (s == "soplex") {
240
241 #ifdef COIN_HAS_SPX
242 CouenneSolverInterface <OsiSpxSolverInterface> *CSI = new CouenneSolverInterface <OsiSpxSolverInterface>;
243 continuousSolver_ = CSI;
244 CSI -> setCutGenPtr (couenneCg);
245 #else
246 journalist()->Printf(J_ERROR, J_INITIALIZATION, "Couenne was compiled without Soplex. Please reconfigure, recompile, and try again.\n");
247 exit (-1);
248 #endif
249 } else {
250 journalist ()-> Printf (J_ERROR, J_INITIALIZATION, "The LP solver you specified hasn't been added to Couenne yet.\n");
251 exit (-1);
252 }
253
254 continuousSolver_ -> passInMessageHandler(ci -> messageHandler());
255
256 couenneProb_ -> setBase (this);
257
258 assert (couenneProb_);
259
260 couenneProb_ -> reformulate (couenneCg);
261
262 Bonmin::BabInfo * extraStuff = new CouenneInfo (0);
263
264 // as per instructions by John Forrest, to get changed bounds
265 extraStuff -> setExtraCharacteristics (extraStuff -> extraCharacteristics () | 2);
266
267 continuousSolver_ -> setAuxiliaryInfo (extraStuff);
268 delete extraStuff;
269
270 extraStuff = dynamic_cast <Bonmin::BabInfo *> (continuousSolver_ -> getAuxiliaryInfo ());
271
272 // Setup log level of LP solver
273 int lpLogLevel;
274 options () -> GetIntegerValue ("lp_log_level", lpLogLevel, "couenne.");
275 continuousSolver_ -> messageHandler () -> setLogLevel (lpLogLevel);
276
277 // Add Couenne SOS ///////////////////////////////////////////////////////////////
278
279 int
280 nSOS = 0,
281 nVars = couenneProb_ -> nVars ();
282
283 OsiObject ** objects = NULL;
284
285 options () -> GetStringValue ("enable_sos", s, "couenne.");
286
287 if (s == "yes") {
288
289 // allocate sufficient space for both nonlinear variables and SOS's
290 objects = new OsiObject* [couenneProb_ -> nCons () + nVars];
291
292 nSOS = couenneProb_ -> findSOS (&(bb -> model()), dynamic_cast <OsiSolverInterface *> (nonlinearSolver ()), objects);
293
294 nonlinearSolver () -> addObjects (nSOS, objects);
295
296 //printf ("boncouennesetup 1: %d SOS objects --> %d\n", nSOS, nonlinearSolver () -> numberObjects ());
297
298 //printf ("==================== found %d SOS\n", nSOS);
299 //nonlinearSolver () -> addObjects (nSOS, objects);
300 //continuousSolver () -> addObjects (nSOS, objects);
301
302 //printf ("found %d SOS!\n", nSOS);
303
304 /*for (int i=0; i<nSOS; i++)
305 delete objects [i];
306 delete [] objects;*/
307
308 if (!nSOS) {
309 delete [] objects;
310 objects = NULL;
311 }
312 }
313
314 //model -> assignSolver (continuousSolver_, true);
315 //continuousSolver_ = model -> solver();
316
317 // Add Couenne objects for branching /////////////////////////////////////////////
318
319 options () -> GetStringValue ("display_stats", s, "couenne.");
320 displayStats_ = (s == "yes");
321
322 options () -> GetStringValue ("branching_object", s, "couenne.");
323
324 enum CouenneObject::branch_obj objType = CouenneObject::VAR_OBJ;
325
326 if (s == "vt_obj") objType = CouenneObject::VT_OBJ;
327 else if (s == "var_obj") objType = CouenneObject::VAR_OBJ;
328 else if (s == "expr_obj") objType = CouenneObject::EXPR_OBJ;
329 else {
330 printf ("CouenneSetup: Unknown branching object type\n");
331 exit (-1);
332 }
333
334 int
335 nobj = nSOS; // if no SOS then objects is empty
336
337 if (!objects)
338 objects = new OsiObject* [nVars];
339
340 int
341 contObjPriority,
342 intObjPriority;
343
344 options () -> GetIntegerValue ("cont_var_priority", contObjPriority, "couenne.");
345 options () -> GetIntegerValue ( "int_var_priority", intObjPriority, "couenne.");
346
347 int varSelection;
348 if (!options_ -> GetEnumValue ("variable_selection", varSelection, "couenne.")) {
349 // change the default for Couenne
350 varSelection = Bonmin::BabSetupBase::OSI_SIMPLE;
351 }
352
353 #ifdef TO_BE_REMOVED
354 if ((Bonmin::BabSetupBase::OSI_STRONG == varSelection) &&
355 (CouenneObject::VT_OBJ == objType)){
356
357 printf ("Warning: Violation Transfer and strong branching are mutually exclusive.\nResetting to Violation Transfer only.");
358 varSelection = Bonmin::BabSetupBase::OSI_SIMPLE;
359 }
360 #endif
361
362 for (int i = 0; i < nVars; i++) { // for each variable
363
364 exprVar *var = couenneProb_ -> Var (i);
365
366 // we only want enabled variables
367 if (var -> Multiplicity () <= 0)
368 continue;
369
370 switch (objType) {
371
372 case CouenneObject::EXPR_OBJ:
373
374 // if this variable is associated with a nonlinear function
375 if (var -> isInteger () ||
376 ((var -> Type () == AUX) &&
377 (var -> Image () -> Linearity () > LINEAR))) {
378
379 /*if ((var -> Image () -> code () == COU_EXPRMUL) &&
380 (var -> Image () -> ArgList () [0] -> Index () >= 0) &&
381 (var -> Image () -> ArgList () [1] -> Index () >= 0) &&
382 (fabs (var -> lb ()) < COUENNE_EPS) &&
383 (fabs (var -> ub ()) < COUENNE_EPS))
384
385 // it's a complementarity constraint object!
386 objects [nobj] = new CouenneComplObject (couenneProb_, var, this, journalist ());
387 else*/
388 objects [nobj] = new CouenneObject (couenneCg, couenneProb_, var, this, journalist ());
389
390 objects [nobj++] -> setPriority (var -> isInteger () ? intObjPriority : contObjPriority);
391 //objects [nobj++] -> setPriority (contObjPriority + var -> rank ());
392 }
393
394 break;
395
396 case CouenneObject::VAR_OBJ:
397
398 // branching objects on variables
399 if // comment three lines below for linear variables too
400 (var -> isInteger () ||
401 (couenneProb_ -> Dependence () [var -> Index ()] . size () > 0)) { // has indep
402 //|| ((var -> Type () == AUX) && // or, aux
403 // (var -> Image () -> Linearity () > LINEAR))) { // of nonlinear
404
405 int ind = var -> Index ();
406
407 objects [nobj] = new CouenneVarObject (couenneCg, couenneProb_, var, this, journalist (), varSelection);
408 objects [nobj++] -> setPriority (var -> isInteger () ? intObjPriority : contObjPriority);
409 //objects [nobj++] -> setPriority (contObjPriority + var -> rank ());
410 }
411
412 break;
413
414 default:
415 case CouenneObject::VT_OBJ:
416
417 // branching objects on variables
418 if // comment three lines below for linear variables too
419 (var -> isInteger () ||
420 (couenneProb_ -> Dependence () [var -> Index ()] . size () > 0)) { // has indep
421 //|| ((var -> Type () == AUX) && // or, aux
422 //(var -> Image () -> Linearity () > LINEAR))) { // of nonlinear
423
424 objects [nobj] = new CouenneVTObject (couenneCg, couenneProb_, var, this, journalist (), varSelection);
425 objects [nobj++] -> setPriority (var -> isInteger () ? intObjPriority : contObjPriority);
426 //objects [nobj++] -> setPriority (contObjPriority + var -> rank ());
427 }
428
429 break;
430 }
431 }
432
433 // // Experimental: orbital branching //////////////////////////////////////////////
434
435 // options () -> GetStringValue ("orbital_branching", s, "couenne.");
436
437 // if (s == "yes") {
438
439 // objects [nobj] = new CouenneOrbitObj (couenneCg, couenneProb_, NULL, this, journalist ());
440 // objects [nobj++] -> setPriority (contObjPriority);
441 // }
442
443 #ifdef COIN_HAS_NTY
444 if (couenneProb_ -> orbitalBranching ()) {
445
446 couenneProb_ -> ChangeBounds (couenneProb_ -> Lb (), couenneProb_ -> Ub (), couenneProb_ -> nVars ());
447 couenneProb_ -> Compute_Symmetry ();
448 }
449 #endif
450
451 //couenneProb_ -> Print_Orbits ();
452
453 // Add objects /////////////////////////////////
454
455 continuousSolver_ -> addObjects (nobj, objects);
456
457 //printf ("boncouennesetup: %d objects --> %d\n", nobj, continuousSolver_ -> numberObjects ());
458
459 for (int i = 0 ; i < nobj ; i++)
460 delete objects [i];
461
462 delete [] objects;
463
464 // Setup Fix Point bound tightener /////////////////////////////////////////////
465
466 options () -> GetIntegerValue ("fixpoint_bt", freq, "couenne.");
467
468 if (freq != 0) {
469
470 CuttingMethod cg;
471 cg.frequency = (freq > 0) ? freq : 1; // Do it always if freq < 0, check within generateCuts() against tree depth
472 cg.cgl = new CouenneFixPoint (couenneProb_, options ());
473 cg.id = "Couenne fixed point FBBT";
474 cutGenerators (). push_back (cg);
475 }
476
477 // Setup Convexifier generators ////////////////////////////////////////////////
478
479 options () -> GetIntegerValue ("convexification_cuts", freq, "couenne.");
480
481 if (freq != 0) {
482
483 CuttingMethod cg;
484 cg.frequency = freq;
485 cg.cgl = couenneCg;
486 cg.id = "Couenne convexifier cuts";
487 cutGenerators().push_back (cg);
488
489 // set cut gen pointer
490 //dynamic_cast <CouenneSolverInterface <OsiClpSolverInterface> *>
491 //(continuousSolver_)
492
493 // this is done on an explicitly declared CSI pointer, however
494 // CSI == continuousSolver_
495 }
496
497 // add other cut generators -- test for integer variables first
498 if (couenneCg -> Problem () -> nIntVars () > 0)
499 addMilpCutGenerators ();
500
501 CouennePtr_ = couenneCg;
502
503 // Add two-inequalities based bound tightening ///////////////////////////////////////////////////////
504
505 options () -> GetIntegerValue ("two_implied_bt", freq, "couenne.");
506
507 if (freq != 0) {
508
509 CouenneTwoImplied * couenne2I =
510 new CouenneTwoImplied (couenneProb_,
511 journalist (),
512 options ());
513 CuttingMethod cg;
514 cg.frequency = freq;
515 cg.cgl = couenne2I;
516 cg.id = "Couenne two-implied cuts";
517 cutGenerators (). push_back(cg);
518 }
519
520 // check branch variable selection for disjunctive cuts
521
522 // Setup heuristic to solve MINLP problems. /////////////////////////////////
523
524 std::string doHeuristic;
525 options () -> GetStringValue ("local_optimization_heuristic", doHeuristic, "couenne.");
526
527 // ----------------------------------------------------------------
528
529 //////////////////////////////////////////////////////////////
530
531 couenneCg -> Problem () -> setMaxCpuTime (getDoubleParameter (BabSetupBase::MaxTime));
532
533 ci -> extractLinearRelaxation (*continuousSolver_, *couenneCg, true, doHeuristic == "yes");
534
535 // In case there are no discrete variables, we have already a
536 // heuristic solution for which create a initialization heuristic
537 if (!(extraStuff -> infeasibleNode ()) &&
538 ci -> isProvenOptimal () &&
539 ci -> haveNlpSolution ()) {
540
541 /// setup initial heuristic (in principle it should only run once...)
542 InitHeuristic* initHeuristic = new InitHeuristic
543 (ci -> getObjValue (), ci -> getColSolution (), *couenneProb_);
544 HeuristicMethod h;
545 h.id = "Couenne Rounding NLP"; // same name as the real rounding one
546 h.heuristic = initHeuristic;
547 heuristics_.push_back(h);
548 }
549
550 if (extraStuff -> infeasibleNode ()){
551 journalist() -> Printf (J_SUMMARY, J_PROBLEM, "Linear relaxation infeasible, the problem is infeasible.\n");
552 retval = false;
553 }
554
555 // ----------------------------------------------------------------
556
557 //continuousSolver_ -> findIntegersAndSOS (false);
558 //addSos (); // only adds embedded SOS objects
559
560 if (doHeuristic == "yes") {
561
562 int numSolve;
563 options()->GetIntegerValue("log_num_local_optimization_per_level",numSolve,"couenne.");
564 NlpSolveHeuristic * nlpHeuristic = new NlpSolveHeuristic;
565 nlpHeuristic->setNlp(*ci,false);
566 nlpHeuristic->setCouenneProblem(couenneProb_);
567 nlpHeuristic->setMaxNlpInf(maxNlpInf_0);
568 nlpHeuristic->setNumberSolvePerLevel(numSolve);
569 HeuristicMethod h;
570 h.id = "Couenne Rounding NLP";
571 h.heuristic = nlpHeuristic;
572 heuristics_.push_back(h);
573 }
574
575 options () -> GetStringValue ("iterative_rounding_heuristic", doHeuristic, "couenne.");
576
577 if (doHeuristic == "yes") {
578 CouenneIterativeRounding * nlpHeuristic = new CouenneIterativeRounding(nonlinearSolver_, ci, couenneProb_, options());
579 HeuristicMethod h;
580 h.id = "Couenne Iterative Rounding";
581 h.heuristic = nlpHeuristic;
582 heuristics_.push_back(h);
583 }
584
585 options () -> GetStringValue ("feas_pump_heuristic", doHeuristic, "couenne.");
586
587 if (doHeuristic != "no") {
588
589 int numSolve;
590
591 CouenneFeasPump *nlpHeuristic = new CouenneFeasPump (couenneProb_, couenneCg, options ());
592
593 options () -> GetIntegerValue ("feas_pump_level", numSolve, "couenne.");
594
595 nlpHeuristic -> setNumberSolvePerLevel (numSolve);
596
597 nlpHeuristic -> nCalls () =
598 ("yes" == doHeuristic) ? -1 : // run it every time Cbc wants
599 ("once" == doHeuristic) ? 1 : -2; // second case means the answer was "only"
600
601 HeuristicMethod h;
602
603 h.id = "Couenne Feasibility Pump";
604 h.heuristic = nlpHeuristic;
605 heuristics_. push_back (h);
606 }
607
608 if (0) { // inactive as of yet -- segfaults
609
610 Ipopt::Index doHeuristicDiveFractional = false;
611 options()->GetEnumValue("heuristic_dive_fractional",doHeuristicDiveFractional,prefix_.c_str());
612 if(doHeuristicDiveFractional){
613 Bonmin::HeuristicDiveFractional* dive_fractional = new Bonmin::HeuristicDiveFractional(this);
614 HeuristicMethod h;
615 h.heuristic = dive_fractional;
616 h.id = "DiveFractional";
617 heuristics_.push_back(h);
618 }
619
620 Ipopt::Index doHeuristicDiveVectorLength = false;
621 options()->GetEnumValue("heuristic_dive_vectorLength",doHeuristicDiveVectorLength,prefix_.c_str());
622 if(doHeuristicDiveVectorLength){
623 Bonmin::HeuristicDiveVectorLength* dive_vectorLength = new Bonmin::HeuristicDiveVectorLength(this);
624 HeuristicMethod h;
625 h.heuristic = dive_vectorLength;
626 h.id = "DiveVectorLength";
627 heuristics_.push_back(h);
628 }
629
630 Ipopt::Index doHeuristicDiveMIPFractional = false;
631 if(!options()->GetEnumValue("heuristic_dive_MIP_fractional",doHeuristicDiveMIPFractional,prefix_.c_str())){
632 doHeuristicDiveMIPFractional = true;
633 std::string o_name = prefix_ + "heuristic_dive_MIP_fractional";
634 options_->SetStringValue(o_name.c_str(), "yes",true,true);
635 }
636 if(doHeuristicDiveMIPFractional){
637 Bonmin::HeuristicDiveMIPFractional* dive_MIP_fractional = new Bonmin::HeuristicDiveMIPFractional(this);
638 HeuristicMethod h;
639 h.heuristic = dive_MIP_fractional;
640 h.id = "DiveMIPFractional";
641 heuristics_.push_back(h);
642 }
643
644 Ipopt::Index doHeuristicDiveMIPVectorLength = false;
645 options()->GetEnumValue("heuristic_dive_MIP_vectorLength",doHeuristicDiveMIPVectorLength,prefix_.c_str());
646 if(doHeuristicDiveMIPVectorLength){
647 Bonmin::HeuristicDiveMIPVectorLength* dive_MIP_vectorLength = new Bonmin::HeuristicDiveMIPVectorLength(this);
648 HeuristicMethod h;
649 h.heuristic = dive_MIP_vectorLength;
650 h.id = "DiveMIPVectorLength";
651 heuristics_.push_back(h);
652 }
653 Ipopt::Index doHeuristicFPump = false;
654 if(!nonlinearSolver_->model()->hasGeneralInteger() && !options()->GetEnumValue("heuristic_feasibility_pump",doHeuristicFPump,prefix_.c_str())){
655 doHeuristicFPump = true;
656 std::string o_name = prefix_ + "heuristic_feasibility_pump";
657 options_->SetStringValue(o_name.c_str(), "yes",true,true);
658 }
659 if(doHeuristicFPump){
660 Bonmin::HeuristicFPump* feasibility_pump = new Bonmin::HeuristicFPump(this);
661 HeuristicMethod h;
662 h.heuristic = feasibility_pump;
663 h.id = "FPump";
664 heuristics_.push_back(h);
665 }
666
667 Ipopt::Index doFixAndSolve = false;
668 options()->GetEnumValue("fix_and_solve_heuristic",doFixAndSolve,prefix_.c_str());
669 if(doFixAndSolve){
670 Bonmin::FixAndSolveHeuristic* fix_and_solve = new Bonmin::FixAndSolveHeuristic(this);
671 HeuristicMethod h;
672 h.heuristic = fix_and_solve;
673 h.id = "Fix and Solve";
674 heuristics_.push_back(h);
675 }
676
677 Ipopt::Index doDummyPump = false;
678 options()->GetEnumValue("dummy_pump_heuristic",doDummyPump,prefix_.c_str());
679 if(doDummyPump){
680 Bonmin::DummyPump* fix_and_solve = new Bonmin::DummyPump(this);
681 HeuristicMethod h;
682 h.heuristic = fix_and_solve;
683 h.id = "Dummy pump";
684 heuristics_.push_back(h);
685 }
686
687 Ipopt::Index doHeuristicRINS = false;
688 options()->GetEnumValue("heuristic_RINS",doHeuristicRINS,prefix_.c_str());
689 if(doHeuristicRINS){
690 Bonmin::HeuristicRINS* rins = new Bonmin::HeuristicRINS(this);
691 HeuristicMethod h;
692 h.heuristic = rins;
693 h.id = "RINS";
694 heuristics_.push_back(h);
695 }
696
697 Ipopt::Index doHeuristicLocalBranching = false;
698 options()->GetEnumValue("heuristic_local_branching",doHeuristicLocalBranching,prefix_.c_str());
699 if(doHeuristicLocalBranching){
700 Bonmin::HeuristicLocalBranching* local_branching = new Bonmin::HeuristicLocalBranching(this);
701 HeuristicMethod h;
702 h.heuristic = local_branching;
703 h.id = "LocalBranching";
704 heuristics_.push_back(h);
705 }
706
707 Ipopt::Index doHeuristicPumpForMinlp = false;
708 options()->GetEnumValue("pump_for_minlp",doHeuristicPumpForMinlp,prefix_.c_str());
709 if(doHeuristicPumpForMinlp){
710 Bonmin::PumpForMinlp * pump = new Bonmin::PumpForMinlp(this);
711 HeuristicMethod h;
712 h.heuristic = pump;
713 h.id = "Pump for MINLP";
714 heuristics_.push_back(h);
715 }
716
717 Ipopt::Index doHeuristicMilpRounding = false;
718 options()->GetEnumValue("MILP_rounding_heuristic",doHeuristicMilpRounding,prefix_.c_str());
719 if(doHeuristicMilpRounding){
720 Bonmin::MilpRounding * round = new Bonmin::MilpRounding(this);
721 HeuristicMethod h;
722 h.heuristic = round;
723 h.id = "MILP Rounding";
724 heuristics_.push_back(h);
725 }
726 }
727
728 // Add Branching rules ///////////////////////////////////////////////////////
729
730 switch (varSelection) {
731
732 case OSI_STRONG: { // strong branching
733 CouenneChooseStrong * chooseVariable = new CouenneChooseStrong
734 (*this, couenneProb_, journalist ());
735 chooseVariable->setTrustStrongForSolution(false);
736 chooseVariable->setTrustStrongForBound(false);
737 chooseVariable->setOnlyPseudoWhenTrusted(true);
738 branchingMethod_ = chooseVariable;
739 break;
740 }
741
742 case OSI_SIMPLE: // default choice
743 branchingMethod_ = new CouenneChooseVariable
744 (continuousSolver_, couenneProb_, journalist ());
745 break;
746
747 default:
748 std::cerr << "Unknown variable_selection for Couenne\n" << std::endl;
749 throw;
750 break;
751 }
752
753 // Node comparison method ///////////////////////////////////////////////////////////////////////////
754
755 int ival;
756 if (!options_->GetEnumValue("node_comparison", ival, "bonmin.")) {
757 // change default for Couenne
758 nodeComparisonMethod_ = bestBound;
759 }
760 else {
761 nodeComparisonMethod_ = NodeComparison(ival);
762 }
763
764 if (intParam_[NumCutPasses] < 2)
765 intParam_[NumCutPasses] = 2;
766
767 // Tell Cbc not to check again if a solution returned from
768 // heuristic is indeed feasible
769 intParam_ [BabSetupBase::SpecialOption] = 16 | 4;
770
771 // Add PSD cut handler ///////////////////////////////////////////////////////
772
773 options () -> GetIntegerValue ("sdp_cuts", freq, "couenne.");
774
775 if (freq != 0) {
776
777 CouenneSdpCuts * couenneSDP =
778 new CouenneSdpCuts (couenneProb_,
779 journalist (),
780 options ());
781 CuttingMethod cg;
782 cg.frequency = freq;
783 cg.cgl = couenneSDP;
784 cg.id = "Couenne SDP cuts";
785 cutGenerators (). push_back (cg);
786 }
787
788 // Add disjunctive cuts ///////////////////////////////////////////////////////
789
790 options () -> GetIntegerValue ("minlp_disj_cuts", freq, "couenne.");
791
792 if (freq != 0) {
793
794 CouenneDisjCuts * couenneDisj =
795 new CouenneDisjCuts (ci, this,
796 couenneCg,
797 branchingMethod_,
798 varSelection == OSI_STRONG, // if true, use strong branching candidates
799 journalist (),
800 options ());
801
802 CuttingMethod cg;
803 cg.frequency = freq;
804 cg.cgl = couenneDisj;
805 cg.id = "Couenne disjunctive cuts";
806 cutGenerators (). push_back(cg);
807 }
808
809 // Add cross-aux redundant cuts ///////////////////////////////////////////////////////
810
811 options () -> GetIntegerValue ("crossconv_cuts", freq, "couenne.");
812
813 if (freq != 0) {
814
815 CouenneCrossConv * couenneCross =
816 new CouenneCrossConv (couenneProb,
817 journalist (),
818 options ());
819
820 CuttingMethod cg;
821 cg.frequency = freq;
822 cg.cgl = couenneCross;
823 cg.id = "Couenne cross-aux cuts";
824 cutGenerators (). push_back(cg);
825 }
826
827 return retval;
828 }
829
registerOptions()830 void CouenneSetup::registerOptions ()
831 {registerAllOptions (roptions ());}
832
833
registerAllOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)834 void CouenneSetup::registerAllOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions) {
835
836 roptions -> SetRegisteringCategory ("Couenne options", Bonmin::RegisteredOptions::CouenneCategory);
837
838 BabSetupBase ::registerAllOptions (roptions);
839 Bonmin::BonCbcFullNodeInfo ::registerOptions (roptions);
840
841 /// Heuristics
842 Bonmin::LocalSolverBasedHeuristic ::registerOptions (roptions);
843 Bonmin::FixAndSolveHeuristic ::registerOptions (roptions);
844 Bonmin::DummyPump ::registerOptions (roptions);
845 Bonmin::MilpRounding ::registerOptions (roptions);
846 Bonmin::PumpForMinlp ::registerOptions (roptions);
847 Bonmin::HeuristicRINS ::registerOptions (roptions);
848 Bonmin::HeuristicLocalBranching ::registerOptions (roptions);
849 Bonmin::HeuristicFPump ::registerOptions (roptions);
850 Bonmin::HeuristicDiveFractional ::registerOptions (roptions);
851 Bonmin::HeuristicDiveVectorLength ::registerOptions (roptions);
852 Bonmin::HeuristicDiveMIPFractional ::registerOptions (roptions);
853 Bonmin::HeuristicDiveMIPVectorLength ::registerOptions (roptions);
854
855 roptions -> AddStringOption3 ("milp_solver",
856 "Choose the subsolver to solve MILP sub-problems in OA decompositions.",
857 "Cbc_D",
858 "Cbc_D","Coin Branch and Cut with its default",
859 "Cbc_Par", "Coin Branch and Cut with passed parameters",
860 "Cplex","Cplex",
861 " To use Cplex, a valid license is required and you should have compiled OsiCpx in COIN-OR (see Osi documentation).");
862
863 roptions -> setOptionExtraInfo ("milp_solver",64);
864
865 roptions -> AddStringOption2 ("milp_strategy",
866 "Choose a strategy for MILPs.",
867 "find_good_sol",
868 "find_good_sol","Stop sub milps when a solution improving the incumbent is found",
869 "solve_to_optimality", "Solve MILPs to optimality",
870 "");
871
872 roptions -> AddStringOption6 ("algorithm",
873 "Choice of the algorithm.",
874 "B-BB",
875 "B-BB","simple branch-and-bound algorithm,",
876 "B-OA","OA Decomposition algorithm,",
877 "B-QG","Quesada and Grossmann branch-and-cut algorithm,",
878 "B-Hyb","hybrid outer approximation based branch-and-cut,",
879 "B-Ecp","ecp cuts based branch-and-cut a la FilMINT.",
880 "B-iFP","Iterated Feasibility Pump for MINLP.",
881 "This will preset some of the options of bonmin depending on the algorithm choice."
882 );
883
884 CouenneProblem ::registerOptions (roptions);
885 CouenneCutGenerator ::registerOptions (roptions);
886 CouenneChooseStrong ::registerOptions (roptions);
887 CouenneChooseVariable ::registerOptions (roptions);
888 CouenneFixPoint ::registerOptions (roptions);
889 CouenneDisjCuts ::registerOptions (roptions);
890 CouenneCrossConv ::registerOptions (roptions);
891 CouenneSdpCuts ::registerOptions (roptions);
892 CouenneTwoImplied ::registerOptions (roptions);
893 NlpSolveHeuristic ::registerOptions (roptions);
894 CouenneFeasPump ::registerOptions (roptions);
895 CouenneIterativeRounding::registerOptions (roptions);
896
897 /// TODO: move later!
898 roptions -> AddStringOption2
899 ("local_branching_heuristic",
900 "Apply local branching heuristic",
901 "no",
902 "no","",
903 "yes","",
904 "A local-branching heuristic based is used to find feasible solutions.");
905
906
907 roptions -> AddNumberOption ("couenne_check",
908 "known value of a global optimum (for debug purposes only)",
909 COIN_DBL_MAX,
910 "Default value is +infinity.");
911
912 roptions -> AddStringOption2 ("display_stats",
913 "display statistics at the end of the run",
914 "no",
915 "yes", "",
916 "no", "");
917
918 roptions -> AddStringOption2 ("save_soltext",
919 "save pairs (index, value) of the solution at the end of the solve",
920 "no",
921 "yes", "",
922 "no", "");
923
924 roptions -> AddStringOption2 ("test_mode",
925 "set to true if this is Couenne unit test",
926 "no",
927 "yes", "",
928 "no", "");
929
930 roptions -> AddStringOption5 ("lp_solver",
931 "Linear Programming solver for the linearization",
932 "clp",
933 "clp", "Use the COIN-OR Open Source solver CLP (default)",
934 "cplex", "Use the commercial solver Cplex (license is needed)",
935 "gurobi", "Use the commercial solver Gurobi (license is needed)",
936 "soplex", "Use the freely available Soplex",
937 "xpress-mp", "Use the commercial solver Xpress MP (license is needed)"
938 );
939
940 #define addLevOption(optname,comment,default) roptions -> AddBoundedIntegerOption (optname, comment, -2, J_LAST_LEVEL-1, default, "")
941
942 addLevOption ("output_level", "Output level", J_WARNING);
943 addLevOption ("branching_print_level", "Output level for braching code in Couenne", J_NONE);
944 addLevOption ("boundtightening_print_level", "Output level for bound tightening code in Couenne", J_NONE);
945 addLevOption ("convexifying_print_level", "Output level for convexifying code in Couenne", J_NONE);
946 addLevOption ("problem_print_level", "Output level for problem manipulation code in Couenne", J_NONE);
947 addLevOption ("nlpheur_print_level", "Output level for NLP heuristic in Couenne", J_NONE);
948 addLevOption ("disjcuts_print_level", "Output level for disjunctive cuts in Couenne", J_NONE);
949 addLevOption ("reformulate_print_level", "Output level for reformulating problems in Couenne", J_NONE);
950
951 roptions -> AddNumberOption
952 ("feas_tolerance",
953 "Tolerance for constraints/auxiliary variables",
954 feas_tolerance_default,
955 "Default value is 1e-5.");
956
957 roptions -> AddStringOption2
958 ("feasibility_bt",
959 "Feasibility-based (cheap) bound tightening (FBBT)",
960 "yes",
961 "no","",
962 "yes","",
963 "A pre-processing technique to reduce the bounding box, before the generation of linearization cuts. "
964 "This is a quick and effective way to reduce the solution set, and it is highly recommended to keep it active."
965 );
966
967 // copied from BonminSetup::registerMilpCutGenerators(), in
968 // BonBonminSetup.cpp
969
970 struct cutOption_ {
971
972 const char *cgname;
973 int defaultFreq;
974
975 } cutOption [] = {
976 {(const char *) "Gomory_cuts", 0},
977 {(const char *) "probing_cuts", 0},
978 {(const char *) "cover_cuts", 0},
979 {(const char *) "mir_cuts", 0},
980 {(const char *) "2mir_cuts", 0},
981 {(const char *) "flow_covers_cuts", 0},
982 {(const char *) "lift_and_project_cuts", 0},
983 {(const char *) "reduce_split_cuts", 0},
984 {(const char *) "clique_cuts", 0},
985 {NULL, 0}};
986
987 for (int i=0; cutOption [i].cgname; i++) {
988
989 char descr [150];
990
991 sprintf (descr, "Frequency k (in terms of nodes) for generating %s cuts in branch-and-cut.",
992 cutOption [i].cgname);
993
994 roptions -> AddLowerBoundedIntegerOption
995 (cutOption [i].cgname,
996 descr,
997 -100, cutOption [i].defaultFreq,
998 "If k > 0, cuts are generated every k nodes, "
999 "if -99 < k < 0 cuts are generated every -k nodes but "
1000 "Cbc may decide to stop generating cuts, if not enough are generated at the root node, "
1001 "if k=-99 generate cuts only at the root node, if k=0 or 100 do not generate cuts.");
1002
1003 roptions->setOptionExtraInfo (cutOption [i].cgname, 5);
1004 }
1005 }
1006
1007
1008
1009 /** Add milp cut generators according to options.*/
addMilpCutGenerators()1010 void CouenneSetup::addMilpCutGenerators () {
1011
1012 enum extraInfo_ {CUTINFO_NONE, CUTINFO_MIG, CUTINFO_PROBING, CUTINFO_CLIQUE};
1013
1014 // extra data structure to avoid repeated code below
1015
1016 struct cutInfo {
1017
1018 const char *optname;
1019 CglCutGenerator *cglptr;
1020 const char *cglId;
1021 enum extraInfo_ extraInfo;
1022
1023 } cutList [] = {
1024 {(const char*)"Gomory_cuts",new CglGomory, (const char*)"Mixed Integer Gomory",CUTINFO_MIG},
1025 {(const char*)"probing_cuts",new CglProbing, (const char*) "Probing", CUTINFO_PROBING},
1026 {(const char*)"mir_cuts",new CglMixedIntegerRounding2, (const char*) "Mixed Integer Rounding",
1027 CUTINFO_NONE},
1028 {(const char*)"2mir_cuts", new CglTwomir, (const char*) "2-MIR", CUTINFO_NONE},
1029 {(const char*)"cover_cuts", new CglKnapsackCover, (const char*) "Cover", CUTINFO_NONE},
1030 {(const char*)"clique_cuts", new CglClique, (const char*) "Clique", CUTINFO_CLIQUE},
1031 {(const char*)"lift_and_project_cuts",new CglLandP,(const char*)"Lift and Project",CUTINFO_NONE},
1032 {(const char*)"reduce_split_cuts",new CglRedSplit,(const char*) "Reduce and Split",CUTINFO_NONE},
1033 {(const char*)"flow_covers_cuts",new CglFlowCover,(const char*) "Flow cover cuts", CUTINFO_NONE},
1034 {NULL, NULL, NULL, CUTINFO_NONE}};
1035
1036 int freq;
1037
1038 for (int i=0; cutList [i]. optname; i++) {
1039
1040 options_ -> GetIntegerValue (std::string (cutList [i]. optname), freq, "couenne.");
1041
1042 if (!freq) {
1043 delete cutList [i].cglptr;
1044 continue;
1045 }
1046
1047 CuttingMethod cg;
1048 cg.frequency = freq;
1049 cg.cgl = cutList [i].cglptr;
1050 cg.id = std::string (cutList [i]. cglId);
1051 cutGenerators_.push_back (cg);
1052
1053 // options for particular cases
1054 switch (cutList [i].extraInfo) {
1055
1056 case CUTINFO_MIG: {
1057 CglGomory *gc = dynamic_cast <CglGomory *> (cutList [i].cglptr);
1058
1059 if (!gc) break;
1060
1061 gc -> setLimitAtRoot(512);
1062 gc -> setLimit(50);
1063 }
1064 break;
1065
1066 case CUTINFO_PROBING: {
1067 CglProbing *pc = dynamic_cast <CglProbing *> (cutList [i].cglptr);
1068
1069 if (!pc) break;
1070
1071 pc->setUsingObjective(1);
1072 pc->setMaxPass(3);
1073 pc->setMaxPassRoot(3);
1074 // Number of unsatisfied variables to look at
1075 pc->setMaxProbe(10);
1076 pc->setMaxProbeRoot(50);
1077 // How far to follow the consequences
1078 pc->setMaxLook(10);
1079 pc->setMaxLookRoot(50);
1080 pc->setMaxLookRoot(10);
1081 // Only look at rows with fewer than this number of elements
1082 pc->setMaxElements(200);
1083 pc->setRowCuts(3);
1084 }
1085 break;
1086
1087 case CUTINFO_CLIQUE: {
1088 CglClique *clique = dynamic_cast <CglClique *> (cutList [i].cglptr);
1089
1090 if (!clique) break;
1091
1092 clique -> setStarCliqueReport(false);
1093 clique -> setRowCliqueReport(false);
1094 clique -> setMinViolation(0.1);
1095 }
1096 break;
1097
1098 //case CUTINFO_NONE:
1099 default:
1100 break;
1101 }
1102 }
1103
1104 double givenAllowFGap2 = 0.0;
1105 options_->GetNumericValue(std::string("allowable_fraction_gap"),
1106 givenAllowFGap2, "bonmin.");
1107 double upval = 1e50;
1108
1109 #ifdef FM_UP_BND
1110 printf("CutOff value:\n");
1111 scanf("%lf", &upval);
1112 #else /* not FM_UP_BND */
1113 options_->GetNumericValue(std::string("art_cutoff"), upval, "bonmin.");
1114 #endif /* FM_UP_BND */
1115
1116 if(upval < 1e50) {
1117 double newCO = (1-givenAllowFGap2) * upval;
1118 couenneProb_->setCutOff(newCO);
1119 printf("CutOff set to %f\n", newCO);
1120
1121 #ifdef FM_TRACE_OPTSOL
1122 if(couenneProb_->getRecordBestSol()->getHasSol()) {
1123 if(newCO < couenneProb_->getRecordBestSol()->getVal()) {
1124 couenneProb_->getRecordBestSol()->setVal(newCO);
1125 }
1126 }
1127 #endif
1128 }
1129 }
1130