# CouenneProblem.hpp

Go to the documentation of this file.

    00001 /* $Id: CouenneProblem.hpp 1083 2014-11-20 17:29:43Z pbelotti $
    00002  *
    00003  * Name:    CouenneProblem.hpp
    00004  * Author:  Pietro Belotti, Lehigh University
    00005  *          Andreas Waechter, IBM
    00006  * Purpose: define the class CouenneProblem
    00007  *
    00008  * (C) Carnegie-Mellon University, 2006-11.
    00009  * This file is licensed under the Eclipse Public License (EPL)
    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     //   bool is_less = 0;
    00090     //   if(a.get_code() < b.get_code() )
    00091     //  is_less = 1;
    00092     //   else {
    00093     //  if(a.get_code() == b.get_code() ) {
    00094     //    if(a.get_coeff() < b.get_coeff() )
    00095     //      is_less = 1;
    00096     //    else{
    00097     //      if(a.get_coeff() ==  b.get_coeff() ) {
    00098     //        if(a.get_lb() < b.get_lb())
    00099     //          is_less = 1;
    00100     //        else{
    00101     //          if(a.get_lb() == b.get_lb()) {
    00102     //            if(a.get_ub() < b.get_ub())
    00103     //              is_less = 1;
    00104     //            else{
    00105     //              if(a.get_ub() == b.get_ub()) {
    00106     //                if(a.get_index() < b.get_index())
    00107     //                  is_less = 1;
    00108     //              }
    00109     //            }
    00110     //          }
    00111     //        }
    00112     //      }
    00113     //    }
    00114     //  }
    00115     //   }
    00116     // return is_less;
    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 // default tolerance for checking feasibility (and integrality) of NLP solutions
    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   // min depth for strong branching output
    00182   int minDepthPrint_;
    00183
    00184   // min number of nodes for strong branching output
    00185   int minNodePrint_;
    00186
    00187   // indicate if strong branching output should be printed
    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   // to speedup sorting operations in strong branching
    00307   int lastPrioSort_;
    00308
    00309   // to record best solution found
    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   // Symmetry Info
    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   // bool node_sort (  Node  a, Node  b);
    00397   // bool index_sort (  Node  a, Node  b);
    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   // get elements from vectors
    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   // Get and set current variable and bounds
    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   // get and set current variable and bounds
    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   // get optimal solution and objective value
    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   // Add (non linear) "=", ">=", "<=", and range constraints
    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   // bound tightening parameters
    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   //void initAuxs (const CouNumber *, const CouNumber *, const CouNumber *);
    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; // if -1 then use feas_tolerance_
    00890
    00896   std::vector <CouenneConstraint *> *ConstraintClass (const char *str) {return ConstraintClass_ [str];}
    00897 };
    00898
    00899 }
    00900
    00901 #endif

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines