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 #include <string.h>
00021
00022 #include "CouenneConfig.h"
00023
00024 #include "CouenneTypes.hpp"
00025 #include "CouenneExpression.hpp"
00026
00027 #include "CouenneJournalist.hpp"
00028 #include "CouenneDomain.hpp"
00029
00030 namespace Ipopt {
00031 template <class T> class SmartPtr;
00032 class OptionsList;
00033 class Journalist;
00034 }
00035
00036 namespace Bonmin {
00037 class RegisteredOptions;
00038 class BabInfo;
00039 class OsiTMINLPInterface;
00040 class BabSetupBase;
00041 }
00042
00043 struct ASL;
00044 struct expr;
00045
00046 class CglTreeInfo;
00047 class CbcModel;
00048 class OsiObject;
00049 class CoinWarmStart;
00050
00051 class Nauty;
00052
00053 class Node{
00054 int index;
00055 double coeff;
00056 double lb;
00057 double ub;
00058 int color;
00059 int code;
00060 int sign;
00061 public:
00062 void node(int, double, double, double, int, int);
00063 inline void color_vertex (register int k) {color = k;}
00064 inline int get_index () const {return index;}
00065 inline double get_coeff () const {return coeff;}
00066 inline double get_lb () const {return lb;}
00067 inline double get_ub () const {return ub;}
00068 inline int get_color () const {return color;}
00069 inline int get_code () const {return code;}
00070 inline int get_sign () const {return sign;}
00071 inline void bounds(register double a, register double b){ lb = a; ub = b;}
00072 };
00073
00074 #define COUENNE_EPS_SYMM 1e-8
00075
00076 struct myclass0 {
00077 inline bool operator() (register const Node &a, register const Node &b) {
00078
00079 return (( a.get_code () < b.get_code ()) ||
00080 (( a.get_code () == b.get_code () &&
00081 (( a.get_coeff () < b.get_coeff () - COUENNE_EPS_SYMM) ||
00082 (( fabs (a.get_coeff () - b.get_coeff ()) < COUENNE_EPS_SYMM) &&
00083 (( a.get_lb () < b.get_lb () - COUENNE_EPS_SYMM) ||
00084 (( fabs (a.get_lb () - b.get_lb ()) < COUENNE_EPS_SYMM) &&
00085 (( a.get_ub () < b.get_ub () - COUENNE_EPS_SYMM) ||
00086 (( fabs (a.get_ub () - b.get_ub ()) < COUENNE_EPS_SYMM) &&
00087 (( a.get_index () < b.get_index ())))))))))));
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
00122 struct myclass {
00123 inline bool operator() (register const Node &a, register const Node &b) {
00124 return (a.get_index() < b.get_index() );
00125 }
00126 };
00127
00128 struct less_than_str {
00129 inline bool operator() (register const char *a, register const char *b) const
00130 {return strcmp (a, b) < 0;}
00131 };
00132
00133
00134 namespace Couenne {
00135
00136 enum TrilinDecompType {rAI, treeDecomp, bi_tri, tri_bi};
00137
00138 class exprVar;
00139 class exprAux;
00140 class DepGraph;
00141 class CouenneObject;
00142 class CouenneCutGenerator;
00143 class quadElem;
00144 class LinMap;
00145 class QuadMap;
00146 class CouenneConstraint;
00147 class CouenneObjective;
00148 class GlobalCutOff;
00149 class CouenneBTPerfIndicator;
00150 class CouenneRecordBestSol;
00151 class CouenneSdpCuts;
00152
00153 typedef Ipopt::SmartPtr<Ipopt::Journalist> JnlstPtr;
00154 typedef Ipopt::SmartPtr<const Ipopt::Journalist> ConstJnlstPtr;
00155
00156 struct compExpr;
00157
00158
00159 const CouNumber feas_tolerance_default = 1e-5;
00160
00169 class CouenneProblem {
00170
00171 friend class exprMul;
00172
00174 enum fixType {UNFIXED, FIXED, CONTINUOUS};
00175
00176 public:
00177
00179 enum multiSep {MulSepNone, MulSepSimple, MulSepTight};
00180
00181
00182 int minDepthPrint_;
00183
00184
00185 int minNodePrint_;
00186
00187
00188 bool doPrint_;
00189
00190 protected:
00191
00193 std::string problemName_;
00194
00195 std::vector <exprVar *> variables_;
00196 std::vector <CouenneObjective *> objectives_;
00197 std::vector <CouenneConstraint *> constraints_;
00198
00200 std::vector <expression *> commonexprs_;
00201
00202 mutable Domain domain_;
00203
00206 std::set <exprAux *, compExpr> *auxSet_;
00207
00209 mutable int curnvars_;
00210
00212 int nIntVars_;
00213
00215 mutable CouNumber *optimum_;
00216
00218 CouNumber bestObj_;
00219
00221 bool *commuted_;
00222
00225 int *numbering_;
00226
00228 int ndefined_;
00229
00234 DepGraph *graph_;
00235
00237 int nOrigVars_;
00238
00241 int nOrigCons_;
00242
00244 int nOrigIntVars_;
00245
00247 mutable GlobalCutOff* pcutoff_;
00248
00250 mutable bool created_pcutoff_;
00251
00252 bool doFBBT_;
00253 bool doRCBT_;
00254 bool doOBBT_;
00255 bool doABT_;
00256
00257 int logObbtLev_;
00258 int logAbtLev_;
00259
00261 JnlstPtr jnlst_;
00262
00264 CouNumber opt_window_;
00265
00267 bool useQuadratic_;
00268
00270 CouNumber feas_tolerance_;
00271
00275 std::vector <std::set <int> > dependence_;
00276
00280 std::vector <CouenneObject *> objects_;
00281
00284 mutable int *integerRank_;
00285
00287 mutable std::vector <int> numberInRank_;
00288
00290 double maxCpuTime_;
00291
00293 Bonmin::BabSetupBase *bonBase_;
00294
00296 ASL *asl_;
00297
00301 int *unusedOriginalsIndices_;
00302
00304 int nUnusedOriginals_;
00305
00306
00307 int lastPrioSort_;
00308
00309
00310 CouenneRecordBestSol *recBSol;
00311
00313 enum multiSep multilinSep_;
00314
00316 int max_fbbt_iter_;
00317
00320 mutable bool fbbtReachedIterLimit_;
00321
00323 bool orbitalBranching_;
00324
00329 bool checkAuxBounds_;
00330
00332 enum TrilinDecompType trilinDecompType_;
00333
00335 double constObjVal_;
00336
00339 CouenneBTPerfIndicator *perfIndicator_;
00340
00346 std::map <const char *, std::vector <CouenneConstraint *> *, less_than_str> ConstraintClass_;
00347
00351 CouenneSdpCuts *sdpCutGen_;
00352
00353 public:
00354
00355 CouenneProblem (ASL * = NULL,
00356 Bonmin::BabSetupBase *base = NULL,
00357 JnlstPtr jnlst = NULL);
00358 CouenneProblem (const CouenneProblem &);
00359 ~CouenneProblem ();
00360
00362 void initOptions (Ipopt::SmartPtr <Ipopt::OptionsList> options);
00363
00365 CouenneProblem *clone () const
00366 {return new CouenneProblem (*this);}
00367
00368 int nObjs () const {return (int) objectives_. size ();}
00369 int nCons () const {return (int) constraints_. size ();}
00370 int nOrigCons () const {return nOrigCons_;}
00371
00372 inline int nOrigVars () const {return nOrigVars_;}
00373 inline int nDefVars () const {return ndefined_;}
00374 inline int nOrigIntVars () const {return nOrigIntVars_;}
00375 inline int nIntVars () const {return nIntVars_;}
00376 inline int nVars () const {return (int) variables_. size ();}
00377
00378 void setNDefVars (int ndefined__) {ndefined_ = ndefined__;}
00379
00380
00381
00382 std::vector<int> *Find_Orbit(int) const;
00383 mutable std::vector<Node> node_info;
00384 mutable Nauty *nauty_info;
00385
00386 myclass0 node_sort;
00387 myclass index_sort;
00388
00389 void sym_setup();
00390 void Compute_Symmetry() const;
00391 void Print_Orbits() const;
00392 void ChangeBounds (const double * , const double *, int ) const;
00393 inline bool compare (register Node &a, register Node &b) const;
00394 Nauty *getNtyInfo () {return nauty_info;}
00395
00396
00397
00398
00400 void setupSymmetry ();
00401
00403 inline int evalOrder (int i) const
00404 {return numbering_ [i];}
00405
00407 inline int *evalVector ()
00408 {return numbering_;}
00409
00410
00411 inline CouenneConstraint *Con (int i) const {return constraints_ [i];}
00412 inline CouenneObjective *Obj (int i) const {return objectives_ [i];}
00413
00415 inline exprVar *Var (int i) const
00416 {return variables_ [i];}
00417
00419 inline std::vector <exprVar *> &Variables ()
00420 {return variables_;}
00421
00423 inline std::set <exprAux *, compExpr> *& AuxSet ()
00424 {return auxSet_;}
00425
00427 inline DepGraph *getDepGraph ()
00428 {return graph_;}
00429
00431 inline Domain *domain () const
00432 {return &domain_;}
00433
00434 inline std::vector <expression *>& commonExprs() { return commonexprs_; }
00435
00436
00437 inline CouNumber &X (int i) const {return domain_.x (i);}
00438 inline CouNumber &Lb (int i) const {return domain_.lb (i);}
00439 inline CouNumber &Ub (int i) const {return domain_.ub (i);}
00440
00441
00442 inline CouNumber *X () const {return domain_.x ();}
00443 inline CouNumber *Lb () const {return domain_.lb ();}
00444 inline CouNumber *Ub () const {return domain_.ub ();}
00445
00446
00447 CouNumber *&bestSol () const {return optimum_;}
00448 CouNumber bestObj () const {return bestObj_;}
00449
00451 bool *&Commuted ()
00452 {return commuted_;}
00453
00455 void addObjective (expression *, const std::string & = "min");
00456
00457
00458 void addEQConstraint (expression *, expression * = NULL);
00459 void addGEConstraint (expression *, expression * = NULL);
00460 void addLEConstraint (expression *, expression * = NULL);
00461 void addRNGConstraint (expression *, expression * = NULL,
00462 expression * = NULL);
00463
00465 void setObjective (int indObj = 0, expression * = NULL, const std::string & = "min");
00466
00471 expression *addVariable (bool isint = false, Domain *d = NULL);
00472
00475 exprAux *addAuxiliary (expression *);
00476
00478 void reformulate (CouenneCutGenerator * = NULL);
00479
00483 bool standardize ();
00484
00487 void print (std::ostream & = std::cout);
00488
00489 #ifdef COIN_HAS_ASL
00491 int readnl (const struct ASL *);
00492
00494 expression *nl2e (struct expr *, const ASL *asl);
00495 #endif
00496
00497
00498 bool doFBBT () const {return (doFBBT_ && (max_fbbt_iter_ != 0));}
00499 bool doRCBT () const {return doRCBT_;}
00500 bool doOBBT () const {return doOBBT_;}
00501 bool doABT () const {return doABT_;}
00502
00503 int logObbtLev () const {return logObbtLev_;}
00504 int logAbtLev () const {return logAbtLev_;}
00505
00518 void writeAMPL (const std::string &fname, bool aux);
00519
00523 void writeGAMS (const std::string &fname);
00524
00529 void writeLP (const std::string &fname);
00530
00533
00534 void initAuxs () const;
00535
00537 void getAuxs (CouNumber *) const;
00538
00540 bool boundTightening (t_chg_bounds *,
00541 const CglTreeInfo info,
00542 Bonmin::BabInfo * = NULL) const;
00543
00545 bool btCore (t_chg_bounds *chg_bds) const;
00546
00548 int obbt (const CouenneCutGenerator *cg,
00549 const OsiSolverInterface &csi,
00550 OsiCuts &cs,
00551 const CglTreeInfo &info,
00552 Bonmin::BabInfo * babInfo,
00553 t_chg_bounds *chg_bds);
00554
00558 bool aggressiveBT (Bonmin::OsiTMINLPInterface *nlp,
00559 t_chg_bounds *,
00560 const CglTreeInfo &info,
00561 Bonmin::BabInfo * = NULL) const;
00562
00565 int redCostBT (const OsiSolverInterface *psi,
00566 t_chg_bounds *chg_bds) const;
00567
00570 int tightenBounds (t_chg_bounds *) const;
00571
00573 int impliedBounds (t_chg_bounds *) const;
00574
00576 void fillQuadIndices ();
00577
00579 void fillObjCoeff (double *&);
00580
00583 void auxiliarize (exprVar *, exprVar * = NULL);
00584
00586 void setCutOff (CouNumber cutoff, const CouNumber *sol = NULL) const;
00587
00589 void resetCutOff (CouNumber value = COUENNE_INFINITY) const;
00590
00592 CouNumber getCutOff () const;
00593
00595 CouNumber *getCutOffSol () const;
00596
00598 void installCutOff () const;
00599
00601 ConstJnlstPtr Jnlst () const;
00602
00604 bool checkNLP (const double *solution, double &obj, bool recompute = false) const;
00605
00608 int getIntegerCandidate (const double *xFrac, double *xInt, double *lb, double *ub) const;
00609
00611 bool readOptimum (std::string *fname = NULL);
00612
00614 static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions);
00615
00617 exprAux *linStandardize (bool addAux,
00618 CouNumber c0,
00619 LinMap &lmap,
00620 QuadMap &qmap);
00621
00624 int splitAux (CouNumber, expression *, expression *&, bool *, enum expression::auxSign &);
00625
00627 void indcoe2vector (int *indexL,
00628 CouNumber *coeff,
00629 std::vector <std::pair <exprVar *, CouNumber> > &lcoeff);
00630
00632 void indcoe2vector (int *indexI,
00633 int *indexJ,
00634 CouNumber *coeff,
00635 std::vector <quadElem> &qcoeff);
00636
00647 void decomposeTerm (expression *term,
00648 CouNumber initCoe,
00649 CouNumber &c0,
00650 LinMap &lmap,
00651 QuadMap &qmap);
00652
00654 const std::string &problemName () const
00655 {return problemName_;}
00656
00657 void setProblemName(std::string& problemName__)
00658 { problemName_ = problemName__; }
00659
00661 const std::vector <std::set <int> > &Dependence () const
00662 {return dependence_;}
00663
00665 const std::vector <CouenneObject *> &Objects () const
00666 {return objects_;}
00667
00669 int findSOS (CbcModel *CbcModelPtr,
00670 OsiSolverInterface *solver,
00671 OsiObject ** objects);
00672
00674 inline void setMaxCpuTime (double time)
00675 {maxCpuTime_ = time;}
00676
00678 inline double getMaxCpuTime () const
00679 {return maxCpuTime_;}
00680
00682 void setBase (Bonmin::BabSetupBase *base);
00683
00688 void createUnusedOriginals ();
00689
00693 void restoreUnusedOriginals (CouNumber * = NULL) const;
00694
00696 int *unusedOriginalsIndices ()
00697 {return unusedOriginalsIndices_;}
00698
00700 int nUnusedOriginals ()
00701 {return nUnusedOriginals_;}
00702
00704 enum multiSep MultilinSep () const
00705 {return multilinSep_;}
00706
00708 bool fbbtReachedIterLimit () const
00709 {return fbbtReachedIterLimit_;}
00710
00712 bool orbitalBranching () const
00713 {return orbitalBranching_;}
00714
00718 void setCheckAuxBounds (bool value)
00719 {checkAuxBounds_ = value;}
00720
00723 bool checkAuxBounds () const
00724 {return checkAuxBounds_;}
00725
00727 enum TrilinDecompType getTrilinDecompType ()
00728 {return trilinDecompType_;}
00729
00731 Bonmin::BabSetupBase *bonBase () const {return bonBase_;}
00732
00734 inline double constObjVal () const {return constObjVal_;}
00735
00737 CouenneSdpCuts *getSdpCutGen () {return sdpCutGen_;}
00738
00739 protected:
00740
00746 int fake_tighten (char direction,
00747 int index,
00748 const double *X,
00749 CouNumber *olb,
00750 CouNumber *oub,
00751 t_chg_bounds *chg_bds,
00752 t_chg_bounds *f_chg) const;
00753
00755 int obbtInner (OsiSolverInterface *,
00756 OsiCuts &,
00757 t_chg_bounds *,
00758 Bonmin::BabInfo *) const;
00759
00760 int obbt_iter (OsiSolverInterface *csi,
00761 t_chg_bounds *chg_bds,
00762 const CoinWarmStart *warmstart,
00763 Bonmin::BabInfo *babInfo,
00764 double *objcoe,
00765 int sense,
00766 int index) const;
00767
00768 int call_iter (OsiSolverInterface *csi,
00769 t_chg_bounds *chg_bds,
00770 const CoinWarmStart *warmstart,
00771 Bonmin::BabInfo *babInfo,
00772 double *objcoe,
00773 enum nodeType type,
00774 int sense) const;
00775
00779 void analyzeSparsity (CouNumber,
00780 LinMap &,
00781 QuadMap &);
00782
00785 void flattenMul (expression *mul,
00786 CouNumber &coe,
00787 std::map <int, CouNumber> &indices);
00788
00790 void realign ();
00791
00793 void fillDependence (Bonmin::BabSetupBase *base, CouenneCutGenerator * = NULL);
00794
00796 void fillIntegerRank () const;
00797
00799 int testIntFix (int index,
00800 CouNumber xFrac,
00801 enum fixType *fixed,
00802 CouNumber *xInt,
00803 CouNumber *dualL, CouNumber *dualR,
00804 CouNumber *olb, CouNumber *oub,
00805 bool patient) const;
00806
00807 public:
00808
00810 inline int getLastPrioSort() const
00811 {return lastPrioSort_;}
00812
00814 void setLastPrioSort (int givenLastPS);
00815
00817 inline CouenneRecordBestSol *getRecordBestSol() const
00818 {return recBSol;}
00819
00821 double getFeasTol() {return feas_tolerance_;}
00822
00824 double checkObj(const CouNumber *sol, const double &precision) const;
00825
00829 bool checkInt(const CouNumber *sol,
00830 const int from, const int upto,
00831 const std::vector<int> listInt,
00832 const bool origVarOnly,
00833 const bool stopAtFirstViol,
00834 const double precision, double &maxViol) const;
00835
00837 bool checkBounds(const CouNumber *sol,
00838 const bool stopAtFirstViol,
00839 const double precision, double &maxViol) const;
00840
00842 bool checkAux(const CouNumber *sol,
00843 const bool stopAtFirstViol,
00844 const double precision, double &maxViol) const;
00845
00847 bool checkCons(const CouNumber *sol,
00848 const bool stopAtFirstViol,
00849 const double precision, double &maxViol) const;
00850
00863
00867
00872
00875 bool checkNLP2 (const double *solution,
00876 const double obj,
00877 const bool careAboutObj,
00878 const bool stopAtFirstViol,
00879 const bool checkAll,
00880 const double precision) const;
00881
00883 bool checkNLP0 (const double *solution,
00884 double &obj,
00885 bool recompute_obj = false,
00886 const bool careAboutObj = false,
00887 const bool stopAtFirstViol = true,
00888 const bool checkAll = false,
00889 const double precision = -1) const;
00890
00896 std::vector <CouenneConstraint *> *ConstraintClass (const char *str) {return ConstraintClass_ [str];}
00897 };
00898
00899 }
00900
00901 #endif