1 /* $Id$ 2 * 3 * Name: CouenneProblem.hpp 4 * Author: Pietro Belotti, Lehigh University 5 * Andreas Waechter, IBM 6 * Purpose: define the class CouenneProblem 7 * 8 * (C) Carnegie-Mellon University, 2006-11. 9 * This file is licensed under the Eclipse Public License (EPL) 10 */ 11 12 #ifndef COUENNE_PROBLEM_HPP 13 #define COUENNE_PROBLEM_HPP 14 15 #define FM_TRACE_OPTSOL 16 #define FM_CHECKNLP2 17 18 #include <vector> 19 #include <map> 20 #include <string.h> 21 22 #include "CouenneConfig.h" 23 24 #include "CouenneTypes.hpp" 25 #include "CouenneExpression.hpp" 26 27 #include "CouenneJournalist.hpp" 28 #include "CouenneDomain.hpp" 29 30 namespace Ipopt { 31 template <class T> class SmartPtr; 32 class OptionsList; 33 class Journalist; 34 } 35 36 namespace Bonmin { 37 class RegisteredOptions; 38 class BabInfo; 39 class OsiTMINLPInterface; 40 class BabSetupBase; 41 } 42 43 struct ASL; 44 struct expr; 45 46 class CglTreeInfo; 47 class CbcModel; 48 class OsiObject; 49 class CoinWarmStart; 50 51 class Nauty; 52 53 class Node{ 54 int index; 55 double coeff; 56 double lb; 57 double ub; 58 int color; 59 int code; 60 int sign; 61 public: 62 void node(int, double, double, double, int, int); color_vertex(register int k)63 inline void color_vertex (register int k) {color = k;} get_index() const64 inline int get_index () const {return index;} get_coeff() const65 inline double get_coeff () const {return coeff;} get_lb() const66 inline double get_lb () const {return lb;} get_ub() const67 inline double get_ub () const {return ub;} get_color() const68 inline int get_color () const {return color;} get_code() const69 inline int get_code () const {return code;} get_sign() const70 inline int get_sign () const {return sign;} bounds(register double a,register double b)71 inline void bounds(register double a, register double b){ lb = a; ub = b;} 72 }; 73 74 #define COUENNE_EPS_SYMM 1e-8 75 76 struct myclass0 { operator ()myclass077 inline bool operator() (register const Node &a, register const Node &b) { 78 79 return (( a.get_code () < b.get_code ()) || 80 (( a.get_code () == b.get_code () && 81 (( a.get_coeff () < b.get_coeff () - COUENNE_EPS_SYMM) || 82 (( fabs (a.get_coeff () - b.get_coeff ()) < COUENNE_EPS_SYMM) && 83 (( a.get_lb () < b.get_lb () - COUENNE_EPS_SYMM) || 84 (( fabs (a.get_lb () - b.get_lb ()) < COUENNE_EPS_SYMM) && 85 (( a.get_ub () < b.get_ub () - COUENNE_EPS_SYMM) || 86 (( fabs (a.get_ub () - b.get_ub ()) < COUENNE_EPS_SYMM) && 87 (( a.get_index () < b.get_index ()))))))))))); 88 89 // bool is_less = 0; 90 // if(a.get_code() < b.get_code() ) 91 // is_less = 1; 92 // else { 93 // if(a.get_code() == b.get_code() ) { 94 // if(a.get_coeff() < b.get_coeff() ) 95 // is_less = 1; 96 // else{ 97 // if(a.get_coeff() == b.get_coeff() ) { 98 // if(a.get_lb() < b.get_lb()) 99 // is_less = 1; 100 // else{ 101 // if(a.get_lb() == b.get_lb()) { 102 // if(a.get_ub() < b.get_ub()) 103 // is_less = 1; 104 // else{ 105 // if(a.get_ub() == b.get_ub()) { 106 // if(a.get_index() < b.get_index()) 107 // is_less = 1; 108 // } 109 // } 110 // } 111 // } 112 // } 113 // } 114 // } 115 // } 116 // return is_less; 117 118 } 119 } ; 120 121 122 struct myclass { operator ()myclass123 inline bool operator() (register const Node &a, register const Node &b) { 124 return (a.get_index() < b.get_index() ); 125 } 126 }; 127 128 struct less_than_str { operator ()less_than_str129 inline bool operator() (register const char *a, register const char *b) const 130 {return strcmp (a, b) < 0;} 131 }; 132 133 134 namespace Couenne { 135 136 enum TrilinDecompType {rAI, treeDecomp, bi_tri, tri_bi}; 137 138 class exprVar; 139 class exprAux; 140 class DepGraph; 141 class CouenneObject; 142 class CouenneCutGenerator; 143 class quadElem; 144 class LinMap; 145 class QuadMap; 146 class CouenneConstraint; 147 class CouenneObjective; 148 class GlobalCutOff; 149 class CouenneBTPerfIndicator; 150 class CouenneRecordBestSol; 151 class CouenneSdpCuts; 152 153 typedef Ipopt::SmartPtr<Ipopt::Journalist> JnlstPtr; 154 typedef Ipopt::SmartPtr<const Ipopt::Journalist> ConstJnlstPtr; 155 156 struct compExpr; 157 158 // default tolerance for checking feasibility (and integrality) of NLP solutions 159 const CouNumber feas_tolerance_default = 1e-5; 160 161 /** Class for MINLP problems with symbolic information 162 * 163 * It is read from an AMPL .nl file and contains variables, AMPL's 164 * "defined variables" (aka common expressions), objective(s), and 165 * constraints in the form of expression's. Changes throughout the 166 * program occur in standardization. 167 */ 168 169 class CouenneProblem { 170 171 friend class exprMul; 172 173 /// structure to record fixed, non-fixed, and continuous variables 174 enum fixType {UNFIXED, FIXED, CONTINUOUS}; 175 176 public: 177 178 /// Type of multilinear separation 179 enum multiSep {MulSepNone, MulSepSimple, MulSepTight}; 180 181 // min depth for strong branching output 182 int minDepthPrint_; 183 184 // min number of nodes for strong branching output 185 int minNodePrint_; 186 187 // indicate if strong branching output should be printed 188 bool doPrint_; 189 190 protected: 191 192 /// problem name 193 std::string problemName_; 194 195 std::vector <exprVar *> variables_; ///< Variables (original, auxiliary, and defined) 196 std::vector <CouenneObjective *> objectives_; ///< Objectives 197 std::vector <CouenneConstraint *> constraints_; ///< Constraints 198 199 /// AMPL's common expressions (read from AMPL through structures cexps and cexps1) 200 std::vector <expression *> commonexprs_; 201 202 mutable Domain domain_; ///< current point and bounds; 203 204 /// Expression map for comparison in standardization and to count 205 /// occurrences of an auxiliary 206 std::set <exprAux *, compExpr> *auxSet_; 207 208 /// Number of elements in the x_, lb_, ub_ arrays 209 mutable int curnvars_; 210 211 /// Number of discrete variables 212 int nIntVars_; 213 214 /// Best solution known to be loaded from file -- for testing purposes 215 mutable CouNumber *optimum_; 216 217 /// Best known objective function 218 CouNumber bestObj_; 219 220 /// Variables that have commuted to auxiliary 221 bool *commuted_; 222 223 /// numbering of variables. No variable xi with associated pi(i) 224 /// greater than pi(j) should be evaluated before variable xj 225 int *numbering_; 226 227 /// Number of "defined variables" (aka "common expressions") 228 int ndefined_; 229 230 /// Dependence (acyclic) graph: shows dependence of all auxiliary 231 /// variables on one another and on original variables. Used to 232 /// create a numbering of all variables for evaluation and bound 233 /// tightening (reverse order for implied bounds) 234 DepGraph *graph_; 235 236 /// Number of original variables 237 int nOrigVars_; 238 239 /// Number of original constraints (disregarding those that turned 240 /// into auxiliary variable definition) 241 int nOrigCons_; 242 243 /// Number of original integer variables 244 int nOrigIntVars_; 245 246 /// Pointer to a global cutoff object 247 mutable GlobalCutOff* pcutoff_; 248 249 /// flag indicating if this class is creator of global cutoff object 250 mutable bool created_pcutoff_; 251 252 bool doFBBT_; ///< do Feasibility-based bound tightening 253 bool doRCBT_; ///< do reduced cost bound tightening 254 bool doOBBT_; ///< do Optimality-based bound tightening 255 bool doABT_; ///< do Aggressive bound tightening 256 257 int logObbtLev_; ///< frequency of Optimality-based bound tightening 258 int logAbtLev_; ///< frequency of Aggressive bound tightening 259 260 /// SmartPointer to the Journalist 261 JnlstPtr jnlst_; 262 263 /// window around known optimum (for testing purposes) 264 CouNumber opt_window_; 265 266 /// Use quadratic expressions? 267 bool useQuadratic_; 268 269 /// feasibility tolerance (to be used in checkNLP) 270 CouNumber feas_tolerance_; 271 272 /// inverse dependence structure: for each variable x give set of 273 /// auxiliary variables (or better, their indices) whose expression 274 /// depends on x 275 std::vector <std::set <int> > dependence_; 276 277 /// vector of pointer to CouenneObjects. Used by CouenneVarObjects 278 /// when finding all objects related to (having as argument) a 279 /// single variable 280 std::vector <CouenneObject *> objects_; 281 282 /// each element is true if variable is integer and, if auxiliary, 283 /// depends on no integer 284 mutable int *integerRank_; 285 286 /// numberInRank_ [i] is the number of integer variables in rank i 287 mutable std::vector <int> numberInRank_; 288 289 /// maximum cpu time 290 double maxCpuTime_; 291 292 /// options 293 Bonmin::BabSetupBase *bonBase_; 294 295 /// AMPL structure pointer (temporary --- looking forward to embedding into OS...) 296 ASL *asl_; 297 298 /// some originals may be unused due to their zero multiplicity 299 /// (that happens when they are duplicates). This array keeps track 300 /// of their indices and is sorted by evaluation order 301 int *unusedOriginalsIndices_; 302 303 /// number of unused originals 304 int nUnusedOriginals_; 305 306 // to speedup sorting operations in strong branching 307 int lastPrioSort_; 308 309 // to record best solution found 310 CouenneRecordBestSol *recBSol; 311 312 /// Type of Multilinear separation 313 enum multiSep multilinSep_; 314 315 /// number of FBBT iterations 316 int max_fbbt_iter_; 317 318 /// true if FBBT exited for iteration limits as opposed to inability 319 /// to further tighten bounds 320 mutable bool fbbtReachedIterLimit_; 321 322 /// use orbital branching? 323 bool orbitalBranching_; 324 325 /// check bounds on auxiliary variables when verifying MINLP 326 /// feasibility of a solution. Usually this is not needed, unless 327 /// some manipulation on auxiliary variables is done before 328 /// Branch-and-Bound 329 bool checkAuxBounds_; 330 331 /// return type of decomposition of quadrilinear terms 332 enum TrilinDecompType trilinDecompType_; 333 334 /// constant value of the objective if no variable is declared in it 335 double constObjVal_; 336 337 /// Performance indicator for FBBT -- to be moved away from 338 /// CouenneProblem when we do it with FBBT 339 CouenneBTPerfIndicator *FBBTperfIndicator_; 340 341 /// Performance indicator for OBBT -- to be moved away from 342 /// CouenneProblem 343 CouenneBTPerfIndicator *OBBTperfIndicator_; 344 345 /// Return particular constraint class. Classes: 346 /// 347 /// 1) "convex": convex constraints; 348 /// 2) "PSDcon": constraints of the form X \succeq 0 349 /// 3) "normal": regular constraints 350 std::map <const char *, std::vector <CouenneConstraint *> *, less_than_str> ConstraintClass_; 351 352 /// Temporary pointer to SDP cut generator. A little dirty as it is 353 /// generated DURING standardization, but necessary to avoid 354 /// meddling with different spaces 355 CouenneSdpCuts *sdpCutGen_; 356 357 public: 358 359 CouenneProblem (ASL * = NULL, 360 Bonmin::BabSetupBase *base = NULL, 361 JnlstPtr jnlst = NULL); ///< Constructor 362 CouenneProblem (const CouenneProblem &); ///< Copy constructor 363 ~CouenneProblem (); ///< Destructor 364 365 /// initializes parameters like doOBBT 366 void initOptions (Ipopt::SmartPtr <Ipopt::OptionsList> options); 367 368 /// Clone method (for use within CouenneCutGenerator::clone) clone() const369 CouenneProblem *clone () const 370 {return new CouenneProblem (*this);} 371 nObjs() const372 int nObjs () const {return (int) objectives_. size ();} ///< Get number of objectives nCons() const373 int nCons () const {return (int) constraints_. size ();} ///< Get number of constraints nOrigCons() const374 int nOrigCons () const {return nOrigCons_;} ///< Get number of original constraints 375 nOrigVars() const376 inline int nOrigVars () const {return nOrigVars_;} ///< Number of orig. variables nDefVars() const377 inline int nDefVars () const {return ndefined_;} ///< Number of def'd variables nOrigIntVars() const378 inline int nOrigIntVars () const {return nOrigIntVars_;} ///< Number of original integers nIntVars() const379 inline int nIntVars () const {return nIntVars_;} ///< Number of integer variables nVars() const380 inline int nVars () const {return (int) variables_. size ();} ///< Total number of variables 381 setNDefVars(int ndefined__)382 void setNDefVars (int ndefined__) {ndefined_ = ndefined__;} 383 384 // Symmetry Info 385 386 std::vector<int> *Find_Orbit(int) const; 387 mutable std::vector<Node> node_info; 388 mutable Nauty *nauty_info; 389 390 myclass0 node_sort; 391 myclass index_sort; 392 393 void sym_setup(); 394 void Compute_Symmetry() const; 395 void Print_Orbits() const; 396 void ChangeBounds (const double * , const double *, int ) const; 397 inline bool compare (register Node &a, register Node &b) const; getNtyInfo()398 Nauty *getNtyInfo () {return nauty_info;} 399 400 // bool node_sort ( Node a, Node b); 401 // bool index_sort ( Node a, Node b); 402 403 /// empty if no NTY, symmetry data structure setup otherwise 404 void setupSymmetry (); 405 406 /// get evaluation order index evalOrder(int i) const407 inline int evalOrder (int i) const 408 {return numbering_ [i];} 409 410 /// get evaluation order vector (numbering_) evalVector()411 inline int *evalVector () 412 {return numbering_;} 413 414 // get elements from vectors Con(int i) const415 inline CouenneConstraint *Con (int i) const {return constraints_ [i];} ///< i-th constraint Obj(int i) const416 inline CouenneObjective *Obj (int i) const {return objectives_ [i];} ///< i-th objective 417 418 /// Return pointer to i-th variable Var(int i) const419 inline exprVar *Var (int i) const 420 {return variables_ [i];} 421 422 /// Return vector of variables (symbolic representation) Variables()423 inline std::vector <exprVar *> &Variables () 424 {return variables_;} 425 426 /// Return pointer to set for comparisons AuxSet()427 inline std::set <exprAux *, compExpr> *& AuxSet () 428 {return auxSet_;} 429 430 /// Return pointer to dependence graph getDepGraph()431 inline DepGraph *getDepGraph () 432 {return graph_;} 433 434 /// return current point & bounds domain() const435 inline Domain *domain () const 436 {return &domain_;} 437 commonExprs()438 inline std::vector <expression *>& commonExprs() { return commonexprs_; } 439 440 // Get and set current variable and bounds X(int i) const441 inline CouNumber &X (int i) const {return domain_.x (i);} ///< \f$x_i\f$ Lb(int i) const442 inline CouNumber &Lb (int i) const {return domain_.lb (i);} ///< lower bound on \f$x_i\f$ Ub(int i) const443 inline CouNumber &Ub (int i) const {return domain_.ub (i);} ///< upper bound on \f$x_i\f$ 444 445 // get and set current variable and bounds X() const446 inline CouNumber *X () const {return domain_.x ();} ///< Return vector of variables Lb() const447 inline CouNumber *Lb () const {return domain_.lb ();} ///< Return vector of lower bounds Ub() const448 inline CouNumber *Ub () const {return domain_.ub ();} ///< Return vector of upper bounds 449 450 // get optimal solution and objective value bestSol() const451 CouNumber *&bestSol () const {return optimum_;} ///< Best known solution (read from file) bestObj() const452 CouNumber bestObj () const {return bestObj_;} ///< Objective of best known solution 453 454 /// Get vector of commuted variables Commuted()455 bool *&Commuted () 456 {return commuted_;} 457 458 /// Add (non linear) objective function 459 void addObjective (expression *, const std::string & = "min"); 460 461 // Add (non linear) "=", ">=", "<=", and range constraints 462 void addEQConstraint (expression *, expression * = NULL); ///< Add equality constraint \f$ h(x) = b\f$ 463 void addGEConstraint (expression *, expression * = NULL); ///< Add \f$\ge\f$ constraint, \f$h(x)\ge b\f$ 464 void addLEConstraint (expression *, expression * = NULL); ///< Add \f$\le\f$ constraint, \f$h(x)\le b\f$ 465 void addRNGConstraint (expression *, expression * = NULL, 466 expression * = NULL); ///< Add range constraint, \f$a\le h(x)\le b\f$ 467 468 /// Add (non linear) objective function 469 void setObjective (int indObj = 0, expression * = NULL, const std::string & = "min"); 470 471 /// Add original variable. 472 /// 473 /// @param isint if true, this variable is integer, otherwise it is 474 /// continuous 475 expression *addVariable (bool isint = false, Domain *d = NULL); 476 477 /// Add auxiliary variable and associate it with expression given as 478 /// argument (used in standardization) 479 exprAux *addAuxiliary (expression *); 480 481 /// preprocess problem in order to extract linear relaxations etc. 482 void reformulate (CouenneCutGenerator * = NULL); 483 484 /// Break problem's nonlinear constraints in simple expressions to 485 /// be convexified later. Return true if problem looks feasible, 486 /// false if proven infeasible. 487 bool standardize (); 488 489 /// Display current representation of problem: objective, linear and 490 /// nonlinear constraints, and auxiliary variables. 491 void print (std::ostream & = std::cout); 492 493 #ifdef COIN_HAS_ASL 494 /// Read problem from .nl file using the Ampl Solver Library (ASL) 495 int readnl (const struct ASL *); 496 497 /// Generate a Couenne expression from an ASL expression 498 expression *nl2e (struct expr *, const ASL *asl); 499 #endif 500 501 // bound tightening parameters doFBBT() const502 bool doFBBT () const {return (doFBBT_ && (max_fbbt_iter_ != 0));} ///< shall we do Feasibility Based Bound Tightening? doRCBT() const503 bool doRCBT () const {return doRCBT_;} ///< shall we do reduced cost Bound Tightening? doOBBT() const504 bool doOBBT () const {return doOBBT_;} ///< shall we do Optimality Based Bound Tightening? doABT() const505 bool doABT () const {return doABT_;} ///< shall we do Aggressive Bound Tightening? 506 logObbtLev() const507 int logObbtLev () const {return logObbtLev_;} ///< How often shall we do OBBT? logAbtLev() const508 int logAbtLev () const {return logAbtLev_;} ///< How often shall we do ABT? 509 510 /// Write nonlinear problem to a .mod file (with lots of defined 511 /// variables) 512 /// 513 /// @param fname Name of the .mod file to be written 514 /// 515 /// @param aux controls the use of auxiliaries. If true, a problem 516 /// is written with auxiliary variables written with their 517 /// associated expression, i.e. \f$w_i = h_i(x,y,w)\f$ and bounds 518 /// \f$l_i \le w_i \le u_i\f$, while if false these constraints are 519 /// written in the form \f$l_i \le h_i (x,y) \le u_i\f$. 520 /// 521 /// Note: if used before standardization, writes original AMPL formulation 522 void writeAMPL (const std::string &fname, bool aux); 523 524 /// Write nonlinear problem to a .gms file 525 /// 526 /// @param fname Name of the .gams file to be written. 527 void writeGAMS (const std::string &fname); 528 529 /// Write nonlinear problem to a .lp file. Note: only works with 530 /// MIQCQPs (and MISOCPs in the future) 531 /// 532 ///@param fname Name of the .lp file to be written 533 void writeLP (const std::string &fname); 534 535 /// Initialize auxiliary variables and their bounds from original 536 /// variables 537 //void initAuxs (const CouNumber *, const CouNumber *, const CouNumber *); 538 void initAuxs () const; 539 540 /// Get auxiliary variables from original variables 541 void getAuxs (CouNumber *) const; 542 543 /// tighten bounds using propagation, implied bounds and reduced costs 544 bool boundTightening (t_chg_bounds *, 545 const CglTreeInfo info, 546 Bonmin::BabInfo * = NULL) const; 547 548 /// core of the bound tightening procedure 549 bool btCore (t_chg_bounds *chg_bds) const; 550 551 /// Optimality Based Bound Tightening 552 int obbt (const CouenneCutGenerator *cg, 553 const OsiSolverInterface &csi, 554 OsiCuts &cs, 555 const CglTreeInfo &info, 556 Bonmin::BabInfo * babInfo, 557 t_chg_bounds *chg_bds); 558 559 /// aggressive bound tightening. Fake bounds in order to cut 560 /// portions of the solution space by fathoming on 561 /// bounds/infeasibility 562 bool aggressiveBT (Bonmin::OsiTMINLPInterface *nlp, 563 t_chg_bounds *, 564 const CglTreeInfo &info, 565 Bonmin::BabInfo * = NULL) const; 566 567 /// procedure to strengthen variable bounds. Return false if problem 568 /// turns out to be infeasible with given bounds, true otherwise. 569 int redCostBT (const OsiSolverInterface *psi, 570 t_chg_bounds *chg_bds) const; 571 572 /// "Forward" bound tightening, that is, propagate bound of variable 573 /// \f$x\f$ in an expression \f$w = f(x)\f$ to the bounds of \f$w\f$. 574 int tightenBounds (t_chg_bounds *) const; 575 576 /// "Backward" bound tightening, aka implied bounds. 577 int impliedBounds (t_chg_bounds *) const; 578 579 /// Look for quadratic terms to be used with SDP cuts 580 void fillQuadIndices (); 581 582 /// Fill vector with coefficients of objective function 583 void fillObjCoeff (double *&); 584 585 /// Replace all occurrences of original variable with new aux given 586 /// as argument 587 void auxiliarize (exprVar *, exprVar * = NULL); 588 589 /// Set cutoff 590 void setCutOff (CouNumber cutoff, const CouNumber *sol = NULL) const; 591 592 /// Reset cutoff 593 void resetCutOff (CouNumber value = COUENNE_INFINITY) const; 594 595 /// Get cutoff 596 CouNumber getCutOff () const; 597 598 /// Get cutoff solution 599 CouNumber *getCutOffSol () const; 600 601 /// Make cutoff known to the problem 602 void installCutOff () const; 603 604 /// Provide Journalist 605 ConstJnlstPtr Jnlst () const; 606 607 /// Check if solution is MINLP feasible 608 bool checkNLP (const double *solution, double &obj, bool recompute = false) const; 609 610 /// generate integer NLP point Y starting from fractional solution 611 /// using bound tightening 612 int getIntegerCandidate (const double *xFrac, double *xInt, double *lb, double *ub) const; 613 614 /// Read best known solution from file given in argument 615 bool readOptimum (std::string *fname = NULL); 616 617 /// Add list of options to be read from file 618 static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions); 619 620 /// standardization of linear exprOp's 621 exprAux *linStandardize (bool addAux, 622 CouNumber c0, 623 LinMap &lmap, 624 QuadMap &qmap); 625 626 /// split a constraint w - f(x) = c into w's index (it is returned) 627 /// and rest = f(x) + c 628 int splitAux (CouNumber, expression *, expression *&, bool *, enum expression::auxSign &); 629 630 /// translates pair (indices, coefficients) into vector with pointers to variables 631 void indcoe2vector (int *indexL, 632 CouNumber *coeff, 633 std::vector <std::pair <exprVar *, CouNumber> > &lcoeff); 634 635 /// translates triplet (indicesI, indicesJ, coefficients) into vector with pointers to variables 636 void indcoe2vector (int *indexI, 637 int *indexJ, 638 CouNumber *coeff, 639 std::vector <quadElem> &qcoeff); 640 641 /// given (expression *) element of sum, returns (coe,ind0,ind1) 642 /// depending on element: 643 /// 644 /// 1) a * x_i ^ 2 ---> (a,i,?) return COU_EXPRPOW 645 /// 2) a * x_i ---> (a,i,?) return COU_EXPRVAR 646 /// 3) a * x_i * x_j ---> (a,i,j) return COU_EXPRMUL 647 /// 4) a ---> (a,?,?) return COU_EXPRCONST 648 /// 649 /// x_i and/or x_j may come from standardizing other (linear or 650 /// quadratic operator) sub-expressions 651 void decomposeTerm (expression *term, 652 CouNumber initCoe, 653 CouNumber &c0, 654 LinMap &lmap, 655 QuadMap &qmap); 656 657 /// return problem name problemName() const658 const std::string &problemName () const 659 {return problemName_;} 660 setProblemName(std::string & problemName__)661 void setProblemName(std::string& problemName__) 662 { problemName_ = problemName__; } 663 664 /// return inverse dependence structure Dependence() const665 const std::vector <std::set <int> > &Dependence () const 666 {return dependence_;} 667 668 /// return object vector Objects() const669 const std::vector <CouenneObject *> &Objects () const 670 {return objects_;} 671 672 /// find SOS constraints in problem 673 int findSOS (CbcModel *CbcModelPtr, 674 OsiSolverInterface *solver, 675 OsiObject ** objects); 676 677 /// set maximum CPU time setMaxCpuTime(double time)678 inline void setMaxCpuTime (double time) 679 {maxCpuTime_ = time;} 680 681 /// return maximum CPU time getMaxCpuTime() const682 inline double getMaxCpuTime () const 683 {return maxCpuTime_;} 684 685 /// save CouenneBase 686 void setBase (Bonmin::BabSetupBase *base); 687 688 /// Some originals may be unused due to their zero multiplicity 689 /// (that happens when they are duplicates). This procedure creates 690 /// a structure for quickly checking and restoring their value after 691 /// solving. 692 void createUnusedOriginals (); 693 694 /// Some originals may be unused due to their zero multiplicity (that 695 /// happens when they are duplicates). This procedure restores their 696 /// value after solving 697 void restoreUnusedOriginals (CouNumber * = NULL) const; 698 699 /// return indices of neglected redundant variables unusedOriginalsIndices()700 int *unusedOriginalsIndices () 701 {return unusedOriginalsIndices_;} 702 703 /// number of unused originals nUnusedOriginals()704 int nUnusedOriginals () 705 {return nUnusedOriginals_;} 706 707 /// return type of separator for multilinear terms MultilinSep() const708 enum multiSep MultilinSep () const 709 {return multilinSep_;} 710 711 /// true if latest call to FBBT terminated due to iteration limit reached fbbtReachedIterLimit() const712 bool fbbtReachedIterLimit () const 713 {return fbbtReachedIterLimit_;} 714 715 /// return true if orbital branching activated orbitalBranching() const716 bool orbitalBranching () const 717 {return orbitalBranching_;} 718 719 /// set the value for checkAuxBounds. When true, all MINLP feasible 720 /// solutions will additionally be tested for feasibility with 721 /// respect to auxiliary variable bounds. This is normally not needed. setCheckAuxBounds(bool value)722 void setCheckAuxBounds (bool value) 723 {checkAuxBounds_ = value;} 724 725 /// return true if bounds of auxiliary variables have to be satisfied 726 /// whenever a solution is tested for MINLP feasibiliry checkAuxBounds() const727 bool checkAuxBounds () const 728 {return checkAuxBounds_;} 729 730 /// return type of decomposition of quadrilinear terms getTrilinDecompType()731 enum TrilinDecompType getTrilinDecompType () 732 {return trilinDecompType_;} 733 734 /// options bonBase() const735 Bonmin::BabSetupBase *bonBase () const {return bonBase_;} 736 737 /// returns constant objective value if it contains no variables constObjVal() const738 inline double constObjVal () const {return constObjVal_;} 739 740 /// Returns pointer to sdp cut generator getSdpCutGen()741 CouenneSdpCuts *getSdpCutGen () {return sdpCutGen_;} 742 743 protected: 744 745 /// single fake tightening. Return 746 /// 747 /// -1 if infeasible 748 /// 0 if no improvement 749 /// +1 if improved 750 int fake_tighten (char direction, ///< 0: left, 1: right 751 int index, ///< index of the variable tested 752 const double *X, ///< point round which tightening is done 753 CouNumber *olb, ///< cur. lower bound 754 CouNumber *oub, ///< cur. upper bound 755 t_chg_bounds *chg_bds, 756 t_chg_bounds *f_chg) const; 757 758 /// Optimality Based Bound Tightening -- inner loop 759 int obbtInner (OsiSolverInterface *, 760 OsiCuts &, 761 t_chg_bounds *, 762 Bonmin::BabInfo *) const; 763 764 int obbt_iter (OsiSolverInterface *csi, 765 t_chg_bounds *chg_bds, 766 const CoinWarmStart *warmstart, 767 Bonmin::BabInfo *babInfo, 768 double *objcoe, 769 int sense, 770 int index) const; 771 772 int call_iter (OsiSolverInterface *csi, 773 t_chg_bounds *chg_bds, 774 const CoinWarmStart *warmstart, 775 Bonmin::BabInfo *babInfo, 776 double *objcoe, 777 enum nodeType type, 778 int sense) const; 779 780 /// analyze sparsity of potential exprQuad/exprGroup and change 781 /// linear/quadratic maps accordingly, if necessary by adding new 782 /// auxiliary variables and including them in the linear map 783 void analyzeSparsity (CouNumber, 784 LinMap &, 785 QuadMap &); 786 787 /// re-organizes multiplication and stores indices (and exponents) of 788 /// its variables 789 void flattenMul (expression *mul, 790 CouNumber &coe, 791 std::map <int, CouNumber> &indices); 792 793 /// clear all spurious variables pointers not referring to the variables_ vector 794 void realign (); 795 796 /// fill dependence_ structure 797 void fillDependence (Bonmin::BabSetupBase *base, CouenneCutGenerator * = NULL); 798 799 /// fill freeIntegers_ array 800 void fillIntegerRank () const; 801 802 /// Test fixing of an integer variable (used in getIntegerCandidate()) 803 int testIntFix (int index, 804 CouNumber xFrac, 805 enum fixType *fixed, 806 CouNumber *xInt, 807 CouNumber *dualL, CouNumber *dualR, 808 CouNumber *olb, CouNumber *oub, 809 bool patient) const; 810 811 public: 812 813 /// getLastPrioSort() const814 inline int getLastPrioSort() const 815 {return lastPrioSort_;} 816 817 /// 818 void setLastPrioSort (int givenLastPS); 819 820 /// returns recorded best solution getRecordBestSol() const821 inline CouenneRecordBestSol *getRecordBestSol() const 822 {return recBSol;} 823 824 /// returns feasibility tolerance getFeasTol()825 double getFeasTol() {return feas_tolerance_;} 826 827 /// Recompute objective value for sol 828 double checkObj(const CouNumber *sol, const double &precision) const; 829 830 /// check integrality of vars in sol with index between from and upto 831 /// (original vars only if origVarOnly == true); 832 /// return true if all integer vars are within precision of an integer value 833 bool checkInt(const CouNumber *sol, 834 const int from, const int upto, 835 const std::vector<int> listInt, 836 const bool origVarOnly, 837 const bool stopAtFirstViol, 838 const double precision, double &maxViol) const; 839 840 /// Check bounds; returns true iff feasible for given precision 841 bool checkBounds(const CouNumber *sol, 842 const bool stopAtFirstViol, 843 const double precision, double &maxViol) const; 844 845 /// returns true iff value of all auxiliaries are within bounds 846 bool checkAux(const CouNumber *sol, 847 const bool stopAtFirstViol, 848 const double precision, double &maxViol) const; 849 850 /// returns true iff value of all auxiliaries are within bounds 851 bool checkCons(const CouNumber *sol, 852 const bool stopAtFirstViol, 853 const double precision, double &maxViol) const; 854 855 /// Return true if either solution or recomputed_solution obtained 856 /// using getAuxs() from the original variables in solution is feasible 857 /// within precision (the solution with minimum violation is then stored 858 /// in recBSol->modSol, as well as its value and violation); 859 /// return false otherwise. 860 /// If stopAtFirstViol == true, recBSol->modSol is meaningless upon return. 861 /// If stopAtFirstViol == false, recBSol->modSol contains the solution 862 /// with minimum violation, although this violation might be larger than 863 /// precision. 864 /// This is useful for cases where the current solution must be considered 865 /// valid (e.g., because Cbc is going to accept it anyway), although it 866 /// violates precision requirements. 867 868 /// Value of obj matters only if careAboutObj == true; 869 /// the code then tries to balance violation of constraints and 870 /// value of objective. 871 872 /// if checkAll = false, check only integrality/bounds for 873 /// original vars and constraints; consider only recomputed_sol 874 /// if checkAll == true, check also integrality/bounds on auxs; 875 /// consider both recomputed_sol and solution 876 877 /// if careAboutObj is set to true, then stopAtFirstViol must be set to 878 /// false too. 879 bool checkNLP2 (const double *solution, 880 const double obj, 881 const bool careAboutObj, 882 const bool stopAtFirstViol, 883 const bool checkAll, 884 const double precision) const; 885 886 /// And finally a method to get both 887 bool checkNLP0 (const double *solution, 888 double &obj, 889 bool recompute_obj = false, 890 const bool careAboutObj = false, 891 const bool stopAtFirstViol = true, 892 const bool checkAll = false, 893 const double precision = -1) const; // if -1 then use feas_tolerance_ 894 895 /// return particular constraint class. Classes: 896 /// 897 /// 1) "convex": convex constraints; 898 /// 2) "PSDcon": constraints of the form X \succeq 0 899 /// 3) "normal": regular constraints ConstraintClass(const char * str)900 std::vector <CouenneConstraint *> *ConstraintClass (const char *str) {return ConstraintClass_ [str];} 901 }; 902 903 } 904 905 #endif 906