00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef COUENNE_PROBLEM_HPP
00013 #define COUENNE_PROBLEM_HPP
00014
00015 #include <vector>
00016 #include <map>
00017
00018 #include "CouenneConfig.h"
00019
00020 #include "CouenneTypes.hpp"
00021 #include "CouenneExpression.hpp"
00022
00023 #include "CouenneJournalist.hpp"
00024 #include "CouenneDomain.hpp"
00025
00026 namespace Ipopt {
00027 template <class T> class SmartPtr;
00028 class OptionsList;
00029 class Journalist;
00030 }
00031
00032 namespace Bonmin {
00033 class RegisteredOptions;
00034 class BabInfo;
00035 class OsiTMINLPInterface;
00036 class BabSetupBase;
00037 }
00038
00039 struct ASL;
00040 struct expr;
00041
00042 class CglTreeInfo;
00043 class CbcModel;
00044 class OsiObject;
00045 class CoinWarmStart;
00046
00047 class Nauty;
00048
00049 class Node{
00050 int index;
00051 double coeff;
00052 double lb;
00053 double ub;
00054 int color;
00055 int code;
00056 int sign;
00057 public:
00058 void node(int, double, double, double, int, int);
00059 inline void color_vertex (register int k) {color = k;}
00060 inline int get_index () const {return index;}
00061 inline double get_coeff () const {return coeff;}
00062 inline double get_lb () const {return lb;}
00063 inline double get_ub () const {return ub;}
00064 inline int get_color () const {return color;}
00065 inline int get_code () const {return code;}
00066 inline int get_sign () const {return sign;}
00067 inline void bounds(register double a, register double b){ lb = a; ub = b;}
00068 };
00069
00070 struct myclass0 {
00071 inline bool operator() (register const Node &a, register const Node &b) {
00072
00073 bool is_less = 0;
00074
00075 if(a.get_code() < b.get_code() )
00076 is_less = 1;
00077 else {
00078 if(a.get_code() == b.get_code() ) {
00079 if(a.get_coeff() < b.get_coeff() )
00080 is_less = 1;
00081 else{
00082 if(a.get_coeff() == b.get_coeff() ) {
00083 if(a.get_lb() < b.get_lb())
00084 is_less = 1;
00085 else{
00086 if(a.get_lb() == b.get_lb()) {
00087 if(a.get_ub() < b.get_ub())
00088 is_less = 1;
00089 else{
00090 if(a.get_ub() == b.get_ub()) {
00091
00092 if(a.get_index() < b.get_index())
00093 is_less = 1;
00094 }
00095 }
00096 }
00097 }
00098 }
00099 }
00100 }
00101 }
00102 return is_less;
00103 }
00104 } ;
00105
00106
00107 struct myclass {
00108 inline bool operator() (register const Node &a, register const Node &b) {
00109 return (a.get_index() < b.get_index() );
00110 }
00111 };
00112
00113
00114 namespace Couenne {
00115
00116 enum TrilinDecompType {rAI, treeDecomp, bi_tri, tri_bi};
00117
00118 class exprVar;
00119 class exprAux;
00120 class DepGraph;
00121 class CouenneObject;
00122 class CouenneCutGenerator;
00123 class quadElem;
00124 class LinMap;
00125 class QuadMap;
00126 class CouenneConstraint;
00127 class CouenneObjective;
00128 class GlobalCutOff;
00129
00130
00131 class CouenneRecordBestSol;
00132
00133 typedef Ipopt::SmartPtr<Ipopt::Journalist> JnlstPtr;
00134 typedef Ipopt::SmartPtr<const Ipopt::Journalist> ConstJnlstPtr;
00135
00136 struct compExpr;
00137
00138
00139 const CouNumber feas_tolerance_default = 1e-5;
00140
00149 class CouenneProblem {
00150
00151 friend class exprMul;
00152
00154 enum fixType {UNFIXED, FIXED, CONTINUOUS};
00155
00156 public:
00157
00159 enum multiSep {MulSepNone, MulSepSimple, MulSepTight};
00160
00161
00162 int minDepthPrint_;
00163
00164
00165 int minNodePrint_;
00166
00167
00168 bool doPrint_;
00169
00170 protected:
00171
00173 std::string problemName_;
00174
00175 std::vector <exprVar *> variables_;
00176 std::vector <CouenneObjective *> objectives_;
00177 std::vector <CouenneConstraint *> constraints_;
00178
00180 std::vector <expression *> commonexprs_;
00181
00182 mutable Domain domain_;
00183
00186 std::set <exprAux *, compExpr> *auxSet_;
00187
00189 mutable int curnvars_;
00190
00192 int nIntVars_;
00193
00195 mutable CouNumber *optimum_;
00196
00198 CouNumber bestObj_;
00199
00201 int *quadIndex_;
00202
00204 bool *commuted_;
00205
00208 int *numbering_;
00209
00211 int ndefined_;
00212
00217 DepGraph *graph_;
00218
00220 int nOrigVars_;
00221
00224 int nOrigCons_;
00225
00227 int nOrigIntVars_;
00228
00230 mutable GlobalCutOff* pcutoff_;
00231
00233 mutable bool created_pcutoff_;
00234
00235 bool doFBBT_;
00236 bool doRCBT_;
00237 bool doOBBT_;
00238 bool doABT_;
00239
00240 int logObbtLev_;
00241 int logAbtLev_;
00242
00244 JnlstPtr jnlst_;
00245
00247 CouNumber opt_window_;
00248
00250 bool useQuadratic_;
00251
00253 CouNumber feas_tolerance_;
00254
00258 std::vector <std::set <int> > dependence_;
00259
00263 std::vector <CouenneObject *> objects_;
00264
00267 mutable int *integerRank_;
00268
00270 mutable std::vector <int> numberInRank_;
00271
00273 double maxCpuTime_;
00274
00276 Bonmin::BabSetupBase *bonBase_;
00277
00279 ASL *asl_;
00280
00284 int *unusedOriginalsIndices_;
00285
00287 int nUnusedOriginals_;
00288
00289
00290 int lastPrioSort_;
00291
00292
00293 struct Couenne::CouenneRecordBestSol *recBSol;
00294
00296 enum multiSep multilinSep_;
00297
00299 int max_fbbt_iter_;
00300
00303 mutable bool fbbtReachedIterLimit_;
00304
00306 bool orbitalBranching_;
00307
00312 bool checkAuxBounds_;
00313
00315 enum TrilinDecompType trilinDecompType_;
00316
00317 public:
00318
00319 CouenneProblem (ASL * = NULL,
00320 Bonmin::BabSetupBase *base = NULL,
00321 JnlstPtr jnlst = NULL);
00322 CouenneProblem (const CouenneProblem &);
00323 ~CouenneProblem ();
00324
00326 void initOptions (Ipopt::SmartPtr <Ipopt::OptionsList> options);
00327
00329 CouenneProblem *clone () const
00330 {return new CouenneProblem (*this);}
00331
00332 int nObjs () const {return (int) objectives_. size ();}
00333 int nCons () const {return (int) constraints_. size ();}
00334 int nOrigCons () const {return nOrigCons_;}
00335
00336 inline int nOrigVars () const {return nOrigVars_;}
00337 inline int nDefVars () const {return ndefined_;}
00338 inline int nOrigIntVars () const {return nOrigIntVars_;}
00339 inline int nIntVars () const {return nIntVars_;}
00340 inline int nVars () const {return (int) variables_. size ();}
00341
00342 void setNDefVars (int ndefined__) {ndefined_ = ndefined__;}
00343
00344
00345
00346 std::vector<int> *Find_Orbit(int) const;
00347 mutable std::vector<Node> node_info;
00348 mutable Nauty *nauty_info;
00349
00350 myclass0 node_sort;
00351 myclass index_sort;
00352
00353 void sym_setup();
00354 void Compute_Symmetry() const;
00355 void Print_Orbits() const;
00356 void ChangeBounds (const double * , const double *, int ) const;
00357 inline bool compare (register Node &a, register Node &b) const;
00358 Nauty *getNtyInfo () {return nauty_info;}
00359
00360
00361
00362
00364 void setupSymmetry ();
00365
00367 inline int evalOrder (int i) const
00368 {return numbering_ [i];}
00369
00371 inline int *evalVector ()
00372 {return numbering_;}
00373
00374
00375 inline CouenneConstraint *Con (int i) const {return constraints_ [i];}
00376 inline CouenneObjective *Obj (int i) const {return objectives_ [i];}
00377
00379 inline exprVar *Var (int i) const
00380 {return variables_ [i];}
00381
00383 inline std::vector <exprVar *> &Variables ()
00384 {return variables_;}
00385
00387 inline std::set <exprAux *, compExpr> *& AuxSet ()
00388 {return auxSet_;}
00389
00391 inline DepGraph *getDepGraph ()
00392 {return graph_;}
00393
00395 inline Domain *domain () const
00396 {return &domain_;}
00397
00398 inline std::vector <expression *>& commonExprs() { return commonexprs_; }
00399
00400
00401 inline CouNumber &X (int i) const {return domain_.x (i);}
00402 inline CouNumber &Lb (int i) const {return domain_.lb (i);}
00403 inline CouNumber &Ub (int i) const {return domain_.ub (i);}
00404
00405
00406 inline CouNumber *X () const {return domain_.x ();}
00407 inline CouNumber *Lb () const {return domain_.lb ();}
00408 inline CouNumber *Ub () const {return domain_.ub ();}
00409
00410
00411 CouNumber *&bestSol () const {return optimum_;}
00412 CouNumber bestObj () const {return bestObj_;}
00413
00415 bool *&Commuted ()
00416 {return commuted_;}
00417
00419 void addObjective (expression *, const std::string & = "min");
00420
00421
00422 void addEQConstraint (expression *, expression * = NULL);
00423 void addGEConstraint (expression *, expression * = NULL);
00424 void addLEConstraint (expression *, expression * = NULL);
00425 void addRNGConstraint (expression *, expression * = NULL,
00426 expression * = NULL);
00427
00429 void setObjective (int indObj = 0, expression * = NULL, const std::string & = "min");
00430
00435 expression *addVariable (bool isint = false, Domain *d = NULL);
00436
00439 exprAux *addAuxiliary (expression *);
00440
00442 void reformulate (CouenneCutGenerator * = NULL);
00443
00447 bool standardize ();
00448
00451 void print (std::ostream & = std::cout);
00452
00453 #ifdef COIN_HAS_ASL
00455 int readnl (const struct ASL *);
00456
00458 expression *nl2e (struct expr *, const ASL *asl);
00459 #endif
00460
00461
00462 bool doFBBT () const {return doFBBT_;}
00463 bool doRCBT () const {return doRCBT_;}
00464 bool doOBBT () const {return doOBBT_;}
00465 bool doABT () const {return doABT_;}
00466
00467 int logObbtLev () const {return logObbtLev_;}
00468 int logAbtLev () const {return logAbtLev_;}
00469
00482 void writeAMPL (const std::string &fname, bool aux);
00483
00487 void writeGAMS (const std::string &fname);
00488
00491
00492 void initAuxs () const;
00493
00495 void getAuxs (CouNumber *) const;
00496
00498 bool boundTightening (t_chg_bounds *,
00499 Bonmin::BabInfo * = NULL) const;
00500
00502 bool btCore (t_chg_bounds *chg_bds) const;
00503
00505 int obbt (const CouenneCutGenerator *cg,
00506 const OsiSolverInterface &csi,
00507 OsiCuts &cs,
00508 const CglTreeInfo &info,
00509 Bonmin::BabInfo * babInfo,
00510 t_chg_bounds *chg_bds);
00511
00515 bool aggressiveBT (Bonmin::OsiTMINLPInterface *nlp,
00516 t_chg_bounds *,
00517 const CglTreeInfo &info,
00518 Bonmin::BabInfo * = NULL) const;
00519
00522 int redCostBT (const OsiSolverInterface *psi,
00523 t_chg_bounds *chg_bds) const;
00524
00527 int tightenBounds (t_chg_bounds *) const;
00528
00530 int impliedBounds (t_chg_bounds *) const;
00531
00533 void fillQuadIndices ();
00534
00536 void fillObjCoeff (double *&);
00537
00540 void auxiliarize (exprVar *, exprVar * = NULL);
00541
00543 void setCutOff (CouNumber cutoff, const CouNumber *sol = NULL) const;
00544
00546 void resetCutOff (CouNumber value = COUENNE_INFINITY) const;
00547
00549 CouNumber getCutOff () const;
00550
00552 CouNumber *getCutOffSol () const;
00553
00555 void installCutOff () const;
00556
00558 ConstJnlstPtr Jnlst () const;
00559
00561 bool checkNLP (const double *solution, double &obj, bool recompute = false) const;
00562
00565 int getIntegerCandidate (const double *xFrac, double *xInt, double *lb, double *ub) const;
00566
00568 bool readOptimum (std::string *fname = NULL);
00569
00571 static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions);
00572
00574 exprAux *linStandardize (bool addAux,
00575 CouNumber c0,
00576 LinMap &lmap,
00577 QuadMap &qmap);
00578
00581 int splitAux (CouNumber, expression *, expression *&, bool *, enum expression::auxSign &);
00582
00584 void indcoe2vector (int *indexL,
00585 CouNumber *coeff,
00586 std::vector <std::pair <exprVar *, CouNumber> > &lcoeff);
00587
00589 void indcoe2vector (int *indexI,
00590 int *indexJ,
00591 CouNumber *coeff,
00592 std::vector <quadElem> &qcoeff);
00593
00604 void decomposeTerm (expression *term,
00605 CouNumber initCoe,
00606 CouNumber &c0,
00607 LinMap &lmap,
00608 QuadMap &qmap);
00609
00611 const std::string &problemName () const
00612 {return problemName_;}
00613
00614 void setProblemName(std::string& problemName__)
00615 { problemName_ = problemName__; }
00616
00618 const std::vector <std::set <int> > &Dependence () const
00619 {return dependence_;}
00620
00622 const std::vector <CouenneObject *> &Objects () const
00623 {return objects_;}
00624
00626 int findSOS (CbcModel *CbcModelPtr,
00627 OsiSolverInterface *solver,
00628 OsiObject ** objects);
00629
00631 inline void setMaxCpuTime (double time)
00632 {maxCpuTime_ = time;}
00633
00635 inline double getMaxCpuTime () const
00636 {return maxCpuTime_;}
00637
00639 void setBase (Bonmin::BabSetupBase *base);
00640
00645 void createUnusedOriginals ();
00646
00650 void restoreUnusedOriginals (CouNumber * = NULL) const;
00651
00653 int *unusedOriginalsIndices ()
00654 {return unusedOriginalsIndices_;}
00655
00657 int nUnusedOriginals ()
00658 {return nUnusedOriginals_;}
00659
00661 enum multiSep MultilinSep () const
00662 {return multilinSep_;}
00663
00665 bool fbbtReachedIterLimit () const
00666 {return fbbtReachedIterLimit_;}
00667
00669 bool orbitalBranching () const
00670 {return orbitalBranching_;}
00671
00675 void setCheckAuxBounds (bool value)
00676 {checkAuxBounds_ = value;}
00677
00680 bool checkAuxBounds () const
00681 {return checkAuxBounds_;}
00682
00684 enum TrilinDecompType getTrilinDecompType ()
00685 {return trilinDecompType_;}
00686
00688 Bonmin::BabSetupBase *bonBase () const {return bonBase_;}
00689
00690 protected:
00691
00697 int fake_tighten (char direction,
00698 int index,
00699 const double *X,
00700 CouNumber *olb,
00701 CouNumber *oub,
00702 t_chg_bounds *chg_bds,
00703 t_chg_bounds *f_chg) const;
00704
00706 int obbtInner (OsiSolverInterface *,
00707 OsiCuts &,
00708 t_chg_bounds *,
00709 Bonmin::BabInfo *) const;
00710
00711 int obbt_iter (OsiSolverInterface *csi,
00712 t_chg_bounds *chg_bds,
00713 const CoinWarmStart *warmstart,
00714 Bonmin::BabInfo *babInfo,
00715 double *objcoe,
00716 int sense,
00717 int index) const;
00718
00719 int call_iter (OsiSolverInterface *csi,
00720 t_chg_bounds *chg_bds,
00721 const CoinWarmStart *warmstart,
00722 Bonmin::BabInfo *babInfo,
00723 double *objcoe,
00724 enum nodeType type,
00725 int sense) const;
00726
00730 void analyzeSparsity (CouNumber,
00731 LinMap &,
00732 QuadMap &);
00733
00736 void flattenMul (expression *mul,
00737 CouNumber &coe,
00738 std::map <int, CouNumber> &indices);
00739
00741 void realign ();
00742
00744 void fillDependence (Bonmin::BabSetupBase *base, CouenneCutGenerator * = NULL);
00745
00747 void fillIntegerRank () const;
00748
00750 int testIntFix (int index,
00751 CouNumber xFrac,
00752 enum fixType *fixed,
00753 CouNumber *xInt,
00754 CouNumber *dualL, CouNumber *dualR,
00755 CouNumber *olb, CouNumber *oub,
00756 bool patient) const;
00757
00758 public:
00759
00761 inline int getLastPrioSort() const
00762 {return lastPrioSort_;};
00763
00765 void setLastPrioSort (int givenLastPS);
00766
00768 inline CouenneRecordBestSol *getRecordBestSol() const
00769 {return recBSol;};
00770
00772 double getFeasTol() {return feas_tolerance_;};
00773
00775 double checkObj(const CouNumber *sol, const double &precision) const;
00776
00780 bool checkInt(const CouNumber *sol,
00781 const int from, const int upto,
00782 const std::vector<int> listInt,
00783 const bool origVarOnly,
00784 const bool stopAtFirstViol,
00785 const double precision, double &maxViol) const;
00786
00788 bool checkBounds(const CouNumber *sol,
00789 const bool stopAtFirstViol,
00790 const double precision, double &maxViol) const;
00791
00793 bool checkAux(const CouNumber *sol,
00794 const bool stopAtFirstViol,
00795 const double precision, double &maxViol) const;
00796
00798 bool checkCons(const CouNumber *sol,
00799 const bool stopAtFirstViol,
00800 const double precision, double &maxViol) const;
00801
00814
00818
00823
00826 bool checkNLP2(const double *solution,
00827 const double obj, const bool careAboutObj,
00828 const bool stopAtFirstViol,
00829 const bool checkAll,
00830 const double precision) const;
00831 };
00832
00833 }
00834
00835 #endif