00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef COUENNE_PROBLEM_HPP
00013 #define COUENNE_PROBLEM_HPP
00014
00015 #define FM_TRACE_OPTSOL
00016 #define FM_CHECKNLP2
00017
00018 #include <vector>
00019 #include <map>
00020
00021 #include "CouenneConfig.h"
00022
00023 #include "CouenneTypes.hpp"
00024 #include "CouenneExpression.hpp"
00025
00026 #include "CouenneJournalist.hpp"
00027 #include "CouenneDomain.hpp"
00028
00029 namespace Ipopt {
00030 template <class T> class SmartPtr;
00031 class OptionsList;
00032 class Journalist;
00033 }
00034
00035 namespace Bonmin {
00036 class RegisteredOptions;
00037 class BabInfo;
00038 class OsiTMINLPInterface;
00039 class BabSetupBase;
00040 }
00041
00042 struct ASL;
00043 struct expr;
00044
00045 class CglTreeInfo;
00046 class CbcModel;
00047 class OsiObject;
00048 class CoinWarmStart;
00049
00050 class Nauty;
00051
00052 class Node{
00053 int index;
00054 double coeff;
00055 double lb;
00056 double ub;
00057 int color;
00058 int code;
00059 int sign;
00060 public:
00061 void node(int, double, double, double, int, int);
00062 inline void color_vertex (register int k) {color = k;}
00063 inline int get_index () const {return index;}
00064 inline double get_coeff () const {return coeff;}
00065 inline double get_lb () const {return lb;}
00066 inline double get_ub () const {return ub;}
00067 inline int get_color () const {return color;}
00068 inline int get_code () const {return code;}
00069 inline int get_sign () const {return sign;}
00070 inline void bounds(register double a, register double b){ lb = a; ub = b;}
00071 };
00072
00073 #define COUENNE_EPS_SYMM 1e-8
00074
00075 struct myclass0 {
00076 inline bool operator() (register const Node &a, register const Node &b) {
00077
00078 return (( a.get_code () < b.get_code ()) ||
00079 (( a.get_code () == b.get_code () &&
00080 (( a.get_coeff () < b.get_coeff () - COUENNE_EPS_SYMM) ||
00081 ((fabs (a.get_coeff () - b.get_coeff ()) < COUENNE_EPS_SYMM) &&
00082 (( a.get_lb () < b.get_lb () - COUENNE_EPS_SYMM) ||
00083 ((fabs (a.get_lb () - b.get_lb ()) < COUENNE_EPS_SYMM) &&
00084 (( a.get_ub () < b.get_ub () - COUENNE_EPS_SYMM) ||
00085 ((fabs (a.get_ub () - b.get_ub ()) < COUENNE_EPS_SYMM) &&
00086 (( a.get_index () < b.get_index ())))))))))));
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117 }
00118 } ;
00119
00120
00121 struct myclass {
00122 inline bool operator() (register const Node &a, register const Node &b) {
00123 return (a.get_index() < b.get_index() );
00124 }
00125 };
00126
00127
00128 namespace Couenne {
00129
00130 enum TrilinDecompType {rAI, treeDecomp, bi_tri, tri_bi};
00131
00132 class exprVar;
00133 class exprAux;
00134 class DepGraph;
00135 class CouenneObject;
00136 class CouenneCutGenerator;
00137 class quadElem;
00138 class LinMap;
00139 class QuadMap;
00140 class CouenneConstraint;
00141 class CouenneObjective;
00142 class GlobalCutOff;
00143
00144
00145 class CouenneRecordBestSol;
00146
00147 typedef Ipopt::SmartPtr<Ipopt::Journalist> JnlstPtr;
00148 typedef Ipopt::SmartPtr<const Ipopt::Journalist> ConstJnlstPtr;
00149
00150 struct compExpr;
00151
00152
00153 const CouNumber feas_tolerance_default = 1e-5;
00154
00163 class CouenneProblem {
00164
00165 friend class exprMul;
00166
00168 enum fixType {UNFIXED, FIXED, CONTINUOUS};
00169
00170 public:
00171
00173 enum multiSep {MulSepNone, MulSepSimple, MulSepTight};
00174
00175
00176 int minDepthPrint_;
00177
00178
00179 int minNodePrint_;
00180
00181
00182 bool doPrint_;
00183
00184 protected:
00185
00187 std::string problemName_;
00188
00189 std::vector <exprVar *> variables_;
00190 std::vector <CouenneObjective *> objectives_;
00191 std::vector <CouenneConstraint *> constraints_;
00192
00194 std::vector <expression *> commonexprs_;
00195
00196 mutable Domain domain_;
00197
00200 std::set <exprAux *, compExpr> *auxSet_;
00201
00203 mutable int curnvars_;
00204
00206 int nIntVars_;
00207
00209 mutable CouNumber *optimum_;
00210
00212 CouNumber bestObj_;
00213
00215 int *quadIndex_;
00216
00218 bool *commuted_;
00219
00222 int *numbering_;
00223
00225 int ndefined_;
00226
00231 DepGraph *graph_;
00232
00234 int nOrigVars_;
00235
00238 int nOrigCons_;
00239
00241 int nOrigIntVars_;
00242
00244 mutable GlobalCutOff* pcutoff_;
00245
00247 mutable bool created_pcutoff_;
00248
00249 bool doFBBT_;
00250 bool doRCBT_;
00251 bool doOBBT_;
00252 bool doABT_;
00253
00254 int logObbtLev_;
00255 int logAbtLev_;
00256
00258 JnlstPtr jnlst_;
00259
00261 CouNumber opt_window_;
00262
00264 bool useQuadratic_;
00265
00267 CouNumber feas_tolerance_;
00268
00272 std::vector <std::set <int> > dependence_;
00273
00277 std::vector <CouenneObject *> objects_;
00278
00281 mutable int *integerRank_;
00282
00284 mutable std::vector <int> numberInRank_;
00285
00287 double maxCpuTime_;
00288
00290 Bonmin::BabSetupBase *bonBase_;
00291
00293 ASL *asl_;
00294
00298 int *unusedOriginalsIndices_;
00299
00301 int nUnusedOriginals_;
00302
00303
00304 int lastPrioSort_;
00305
00306
00307 CouenneRecordBestSol *recBSol;
00308
00310 enum multiSep multilinSep_;
00311
00313 int max_fbbt_iter_;
00314
00317 mutable bool fbbtReachedIterLimit_;
00318
00320 bool orbitalBranching_;
00321
00326 bool checkAuxBounds_;
00327
00329 enum TrilinDecompType trilinDecompType_;
00330
00332 double constObjVal_;
00333
00334 public:
00335
00336 CouenneProblem (ASL * = NULL,
00337 Bonmin::BabSetupBase *base = NULL,
00338 JnlstPtr jnlst = NULL);
00339 CouenneProblem (const CouenneProblem &);
00340 ~CouenneProblem ();
00341
00343 void initOptions (Ipopt::SmartPtr <Ipopt::OptionsList> options);
00344
00346 CouenneProblem *clone () const
00347 {return new CouenneProblem (*this);}
00348
00349 int nObjs () const {return (int) objectives_. size ();}
00350 int nCons () const {return (int) constraints_. size ();}
00351 int nOrigCons () const {return nOrigCons_;}
00352
00353 inline int nOrigVars () const {return nOrigVars_;}
00354 inline int nDefVars () const {return ndefined_;}
00355 inline int nOrigIntVars () const {return nOrigIntVars_;}
00356 inline int nIntVars () const {return nIntVars_;}
00357 inline int nVars () const {return (int) variables_. size ();}
00358
00359 void setNDefVars (int ndefined__) {ndefined_ = ndefined__;}
00360
00361
00362
00363 std::vector<int> *Find_Orbit(int) const;
00364 mutable std::vector<Node> node_info;
00365 mutable Nauty *nauty_info;
00366
00367 myclass0 node_sort;
00368 myclass index_sort;
00369
00370 void sym_setup();
00371 void Compute_Symmetry() const;
00372 void Print_Orbits() const;
00373 void ChangeBounds (const double * , const double *, int ) const;
00374 inline bool compare (register Node &a, register Node &b) const;
00375 Nauty *getNtyInfo () {return nauty_info;}
00376
00377
00378
00379
00381 void setupSymmetry ();
00382
00384 inline int evalOrder (int i) const
00385 {return numbering_ [i];}
00386
00388 inline int *evalVector ()
00389 {return numbering_;}
00390
00391
00392 inline CouenneConstraint *Con (int i) const {return constraints_ [i];}
00393 inline CouenneObjective *Obj (int i) const {return objectives_ [i];}
00394
00396 inline exprVar *Var (int i) const
00397 {return variables_ [i];}
00398
00400 inline std::vector <exprVar *> &Variables ()
00401 {return variables_;}
00402
00404 inline std::set <exprAux *, compExpr> *& AuxSet ()
00405 {return auxSet_;}
00406
00408 inline DepGraph *getDepGraph ()
00409 {return graph_;}
00410
00412 inline Domain *domain () const
00413 {return &domain_;}
00414
00415 inline std::vector <expression *>& commonExprs() { return commonexprs_; }
00416
00417
00418 inline CouNumber &X (int i) const {return domain_.x (i);}
00419 inline CouNumber &Lb (int i) const {return domain_.lb (i);}
00420 inline CouNumber &Ub (int i) const {return domain_.ub (i);}
00421
00422
00423 inline CouNumber *X () const {return domain_.x ();}
00424 inline CouNumber *Lb () const {return domain_.lb ();}
00425 inline CouNumber *Ub () const {return domain_.ub ();}
00426
00427
00428 CouNumber *&bestSol () const {return optimum_;}
00429 CouNumber bestObj () const {return bestObj_;}
00430
00432 bool *&Commuted ()
00433 {return commuted_;}
00434
00436 void addObjective (expression *, const std::string & = "min");
00437
00438
00439 void addEQConstraint (expression *, expression * = NULL);
00440 void addGEConstraint (expression *, expression * = NULL);
00441 void addLEConstraint (expression *, expression * = NULL);
00442 void addRNGConstraint (expression *, expression * = NULL,
00443 expression * = NULL);
00444
00446 void setObjective (int indObj = 0, expression * = NULL, const std::string & = "min");
00447
00452 expression *addVariable (bool isint = false, Domain *d = NULL);
00453
00456 exprAux *addAuxiliary (expression *);
00457
00459 void reformulate (CouenneCutGenerator * = NULL);
00460
00464 bool standardize ();
00465
00468 void print (std::ostream & = std::cout);
00469
00470 #ifdef COIN_HAS_ASL
00472 int readnl (const struct ASL *);
00473
00475 expression *nl2e (struct expr *, const ASL *asl);
00476 #endif
00477
00478
00479 bool doFBBT () const {return doFBBT_;}
00480 bool doRCBT () const {return doRCBT_;}
00481 bool doOBBT () const {return doOBBT_;}
00482 bool doABT () const {return doABT_;}
00483
00484 int logObbtLev () const {return logObbtLev_;}
00485 int logAbtLev () const {return logAbtLev_;}
00486
00499 void writeAMPL (const std::string &fname, bool aux);
00500
00504 void writeGAMS (const std::string &fname);
00505
00508
00509 void initAuxs () const;
00510
00512 void getAuxs (CouNumber *) const;
00513
00515 bool boundTightening (t_chg_bounds *,
00516 Bonmin::BabInfo * = NULL) const;
00517
00519 bool btCore (t_chg_bounds *chg_bds) const;
00520
00522 int obbt (const CouenneCutGenerator *cg,
00523 const OsiSolverInterface &csi,
00524 OsiCuts &cs,
00525 const CglTreeInfo &info,
00526 Bonmin::BabInfo * babInfo,
00527 t_chg_bounds *chg_bds);
00528
00532 bool aggressiveBT (Bonmin::OsiTMINLPInterface *nlp,
00533 t_chg_bounds *,
00534 const CglTreeInfo &info,
00535 Bonmin::BabInfo * = NULL) const;
00536
00539 int redCostBT (const OsiSolverInterface *psi,
00540 t_chg_bounds *chg_bds) const;
00541
00544 int tightenBounds (t_chg_bounds *) const;
00545
00547 int impliedBounds (t_chg_bounds *) const;
00548
00550 void fillQuadIndices ();
00551
00553 void fillObjCoeff (double *&);
00554
00557 void auxiliarize (exprVar *, exprVar * = NULL);
00558
00560 void setCutOff (CouNumber cutoff, const CouNumber *sol = NULL) const;
00561
00563 void resetCutOff (CouNumber value = COUENNE_INFINITY) const;
00564
00566 CouNumber getCutOff () const;
00567
00569 CouNumber *getCutOffSol () const;
00570
00572 void installCutOff () const;
00573
00575 ConstJnlstPtr Jnlst () const;
00576
00578 bool checkNLP (const double *solution, double &obj, bool recompute = false) const;
00579
00582 int getIntegerCandidate (const double *xFrac, double *xInt, double *lb, double *ub) const;
00583
00585 bool readOptimum (std::string *fname = NULL);
00586
00588 static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions);
00589
00591 exprAux *linStandardize (bool addAux,
00592 CouNumber c0,
00593 LinMap &lmap,
00594 QuadMap &qmap);
00595
00598 int splitAux (CouNumber, expression *, expression *&, bool *, enum expression::auxSign &);
00599
00601 void indcoe2vector (int *indexL,
00602 CouNumber *coeff,
00603 std::vector <std::pair <exprVar *, CouNumber> > &lcoeff);
00604
00606 void indcoe2vector (int *indexI,
00607 int *indexJ,
00608 CouNumber *coeff,
00609 std::vector <quadElem> &qcoeff);
00610
00621 void decomposeTerm (expression *term,
00622 CouNumber initCoe,
00623 CouNumber &c0,
00624 LinMap &lmap,
00625 QuadMap &qmap);
00626
00628 const std::string &problemName () const
00629 {return problemName_;}
00630
00631 void setProblemName(std::string& problemName__)
00632 { problemName_ = problemName__; }
00633
00635 const std::vector <std::set <int> > &Dependence () const
00636 {return dependence_;}
00637
00639 const std::vector <CouenneObject *> &Objects () const
00640 {return objects_;}
00641
00643 int findSOS (CbcModel *CbcModelPtr,
00644 OsiSolverInterface *solver,
00645 OsiObject ** objects);
00646
00648 inline void setMaxCpuTime (double time)
00649 {maxCpuTime_ = time;}
00650
00652 inline double getMaxCpuTime () const
00653 {return maxCpuTime_;}
00654
00656 void setBase (Bonmin::BabSetupBase *base);
00657
00662 void createUnusedOriginals ();
00663
00667 void restoreUnusedOriginals (CouNumber * = NULL) const;
00668
00670 int *unusedOriginalsIndices ()
00671 {return unusedOriginalsIndices_;}
00672
00674 int nUnusedOriginals ()
00675 {return nUnusedOriginals_;}
00676
00678 enum multiSep MultilinSep () const
00679 {return multilinSep_;}
00680
00682 bool fbbtReachedIterLimit () const
00683 {return fbbtReachedIterLimit_;}
00684
00686 bool orbitalBranching () const
00687 {return orbitalBranching_;}
00688
00692 void setCheckAuxBounds (bool value)
00693 {checkAuxBounds_ = value;}
00694
00697 bool checkAuxBounds () const
00698 {return checkAuxBounds_;}
00699
00701 enum TrilinDecompType getTrilinDecompType ()
00702 {return trilinDecompType_;}
00703
00705 Bonmin::BabSetupBase *bonBase () const {return bonBase_;}
00706
00708 inline double constObjVal () const {return constObjVal_;}
00709
00710 protected:
00711
00717 int fake_tighten (char direction,
00718 int index,
00719 const double *X,
00720 CouNumber *olb,
00721 CouNumber *oub,
00722 t_chg_bounds *chg_bds,
00723 t_chg_bounds *f_chg) const;
00724
00726 int obbtInner (OsiSolverInterface *,
00727 OsiCuts &,
00728 t_chg_bounds *,
00729 Bonmin::BabInfo *) const;
00730
00731 int obbt_iter (OsiSolverInterface *csi,
00732 t_chg_bounds *chg_bds,
00733 const CoinWarmStart *warmstart,
00734 Bonmin::BabInfo *babInfo,
00735 double *objcoe,
00736 int sense,
00737 int index) const;
00738
00739 int call_iter (OsiSolverInterface *csi,
00740 t_chg_bounds *chg_bds,
00741 const CoinWarmStart *warmstart,
00742 Bonmin::BabInfo *babInfo,
00743 double *objcoe,
00744 enum nodeType type,
00745 int sense) const;
00746
00750 void analyzeSparsity (CouNumber,
00751 LinMap &,
00752 QuadMap &);
00753
00756 void flattenMul (expression *mul,
00757 CouNumber &coe,
00758 std::map <int, CouNumber> &indices);
00759
00761 void realign ();
00762
00764 void fillDependence (Bonmin::BabSetupBase *base, CouenneCutGenerator * = NULL);
00765
00767 void fillIntegerRank () const;
00768
00770 int testIntFix (int index,
00771 CouNumber xFrac,
00772 enum fixType *fixed,
00773 CouNumber *xInt,
00774 CouNumber *dualL, CouNumber *dualR,
00775 CouNumber *olb, CouNumber *oub,
00776 bool patient) const;
00777
00778 public:
00779
00781 inline int getLastPrioSort() const
00782 {return lastPrioSort_;}
00783
00785 void setLastPrioSort (int givenLastPS);
00786
00788 inline CouenneRecordBestSol *getRecordBestSol() const
00789 {return recBSol;}
00790
00792 double getFeasTol() {return feas_tolerance_;}
00793
00795 double checkObj(const CouNumber *sol, const double &precision) const;
00796
00800 bool checkInt(const CouNumber *sol,
00801 const int from, const int upto,
00802 const std::vector<int> listInt,
00803 const bool origVarOnly,
00804 const bool stopAtFirstViol,
00805 const double precision, double &maxViol) const;
00806
00808 bool checkBounds(const CouNumber *sol,
00809 const bool stopAtFirstViol,
00810 const double precision, double &maxViol) const;
00811
00813 bool checkAux(const CouNumber *sol,
00814 const bool stopAtFirstViol,
00815 const double precision, double &maxViol) const;
00816
00818 bool checkCons(const CouNumber *sol,
00819 const bool stopAtFirstViol,
00820 const double precision, double &maxViol) const;
00821
00834
00838
00843
00846 bool checkNLP2(const double *solution,
00847 const double obj, const bool careAboutObj,
00848 const bool stopAtFirstViol,
00849 const bool checkAll,
00850 const double precision) const;
00851 };
00852
00853 }
00854
00855 #endif