CouenneProblem.hpp

Go to the documentation of this file.

/* $Id: CouenneProblem.hpp 1255 2018-08-27 22:56:09Z pbelotti $
 *
 * Name:    CouenneProblem.hpp
 * Author:  Pietro Belotti, Lehigh University
 *          Andreas Waechter, IBM
 * Purpose: define the class CouenneProblem
 *
 * (C) Carnegie-Mellon University, 2006-11.
 * This file is licensed under the Eclipse Public License (EPL)
 */

#ifndef COUENNE_PROBLEM_HPP
#define COUENNE_PROBLEM_HPP

#define FM_TRACE_OPTSOL
#define FM_CHECKNLP2

#include <vector>
#include <map>
#include <string.h>

#include "CouenneConfig.h"

#include "CouenneTypes.hpp"
#include "CouenneExpression.hpp"

#include "CouenneJournalist.hpp"
#include "CouenneDomain.hpp"

namespace Ipopt {
  template <class T> class SmartPtr;
  class OptionsList;
  class Journalist;
}

namespace Bonmin {
  class RegisteredOptions;
  class BabInfo;
  class OsiTMINLPInterface;
  class BabSetupBase;
}

struct ASL;
struct expr;

class CglTreeInfo;
class CbcModel;
class OsiObject;
class CoinWarmStart;

class Nauty;

  class Node{
    int index;
    double coeff;
    double lb;
    double ub;
    int color;
    int code;
    int sign;
  public:
    void node(int, double, double, double, int, int);
    inline void color_vertex (register int k) {color = k;}
    inline int get_index () const {return index;}
    inline double get_coeff () const {return coeff;}
    inline double get_lb () const {return lb;}
    inline double get_ub () const {return ub;}
    inline int get_color () const {return color;}
    inline int get_code () const {return code;}
    inline int get_sign () const {return sign;}
    inline void bounds(register double a, register double b){ lb = a; ub = b;}
  };

#define COUENNE_EPS_SYMM 1e-8

  struct myclass0 {
    inline bool operator() (register const Node &a, register const Node &b) {

      return ((               a.get_code  () <  b.get_code  ())                     ||
              ((              a.get_code  () == b.get_code  ()                      &&
                ((            a.get_coeff () <  b.get_coeff ()  - COUENNE_EPS_SYMM) ||
                 ((     fabs (a.get_coeff () -  b.get_coeff ()) < COUENNE_EPS_SYMM) &&
                  ((          a.get_lb    () <  b.get_lb    ()  - COUENNE_EPS_SYMM) ||
                   ((   fabs (a.get_lb    () -  b.get_lb    ()) < COUENNE_EPS_SYMM) &&
                    ((        a.get_ub    () <  b.get_ub    ()  - COUENNE_EPS_SYMM) ||
                     (( fabs (a.get_ub    () -  b.get_ub    ()) < COUENNE_EPS_SYMM) &&
                      ((      a.get_index () <  b.get_index ())))))))))));

    //   bool is_less = 0;
    //   if(a.get_code() < b.get_code() )
    //  is_less = 1;
    //   else {
    //  if(a.get_code() == b.get_code() ) {
    //    if(a.get_coeff() < b.get_coeff() )
    //      is_less = 1;
    //    else{
    //      if(a.get_coeff() ==  b.get_coeff() ) {
    //        if(a.get_lb() < b.get_lb())
    //          is_less = 1;
    //        else{
    //          if(a.get_lb() == b.get_lb()) {
    //            if(a.get_ub() < b.get_ub())
    //              is_less = 1;
    //            else{
    //              if(a.get_ub() == b.get_ub()) {                  
    //                if(a.get_index() < b.get_index())
    //                  is_less = 1;
    //              }
    //            }
    //          }
    //        }
    //      }
    //    }
    //  }
    //   }
    // return is_less;

    }
  } ;
    
      
  struct myclass {
    inline bool operator() (register const  Node &a, register const Node &b) {
      return (a.get_index() < b.get_index() );
    }
  };

struct less_than_str {
  inline bool operator() (register const  char *a, register const char *b) const
  {return strcmp (a, b) < 0;}
};


namespace Couenne {

  enum TrilinDecompType {rAI, treeDecomp, bi_tri, tri_bi};

  class exprVar;
  class exprAux;
  class DepGraph;
  class CouenneObject;
  class CouenneCutGenerator;
  class quadElem;
  class LinMap;
  class QuadMap;
  class CouenneConstraint;
  class CouenneObjective;
  class GlobalCutOff;
  class CouenneBTPerfIndicator;
  class CouenneRecordBestSol;
  class CouenneSdpCuts;

  typedef Ipopt::SmartPtr<Ipopt::Journalist> JnlstPtr;
  typedef Ipopt::SmartPtr<const Ipopt::Journalist> ConstJnlstPtr;

  struct compExpr;

// default tolerance for checking feasibility (and integrality) of NLP solutions
const CouNumber feas_tolerance_default = 1e-5;

class CouenneProblem {

  friend class exprMul;

  enum fixType {UNFIXED, FIXED, CONTINUOUS};

 public:

  enum multiSep {MulSepNone, MulSepSimple, MulSepTight};

  // min depth for strong branching output
  int minDepthPrint_;

  // min number of nodes for strong branching output
  int minNodePrint_;

  // indicate if strong branching output should be printed
  bool doPrint_;

 protected:

  std::string problemName_;

  std::vector <exprVar           *> variables_;   
  std::vector <CouenneObjective  *> objectives_;  
  std::vector <CouenneConstraint *> constraints_; 

  std::vector <expression *> commonexprs_; 

  mutable Domain domain_; 

  std::set <exprAux *, compExpr> *auxSet_;

  mutable int curnvars_;

  int nIntVars_;

  mutable CouNumber *optimum_;

  CouNumber bestObj_;

  bool *commuted_;

  int *numbering_;

  int ndefined_;

  DepGraph *graph_;

  int nOrigVars_;

  int nOrigCons_;

  int nOrigIntVars_;

  mutable GlobalCutOff* pcutoff_;

  mutable bool created_pcutoff_;

  bool doFBBT_;  
  bool doRCBT_;  
  bool doOBBT_;  
  bool doABT_;   

  int logObbtLev_;   
  int logAbtLev_;    

  JnlstPtr jnlst_;

  CouNumber opt_window_;

  bool useQuadratic_;

  CouNumber feas_tolerance_;

  std::vector <std::set <int> > dependence_;

  std::vector <CouenneObject *> objects_;

  mutable int *integerRank_;

  mutable std::vector <int> numberInRank_;

  double maxCpuTime_;

  Bonmin::BabSetupBase *bonBase_;

  ASL *asl_;

  int *unusedOriginalsIndices_;

  int nUnusedOriginals_;

  // to speedup sorting operations in strong branching
  int lastPrioSort_;

  // to record best solution found
  CouenneRecordBestSol *recBSol;

  enum multiSep multilinSep_;

  int max_fbbt_iter_;

  mutable bool fbbtReachedIterLimit_;

  bool orbitalBranching_;

  bool checkAuxBounds_;

  enum TrilinDecompType trilinDecompType_;

  double constObjVal_;

  CouenneBTPerfIndicator *FBBTperfIndicator_;

  CouenneBTPerfIndicator *OBBTperfIndicator_;

  std::map <const char *, std::vector <CouenneConstraint *> *, less_than_str> ConstraintClass_;

  CouenneSdpCuts *sdpCutGen_;
  
 public:

  CouenneProblem  (ASL * = NULL,
                   Bonmin::BabSetupBase *base = NULL,
                   JnlstPtr jnlst = NULL);  
  CouenneProblem  (const CouenneProblem &); 
  ~CouenneProblem ();                       

  void initOptions (Ipopt::SmartPtr <Ipopt::OptionsList> options);

  CouenneProblem *clone () const
  {return new CouenneProblem (*this);}

  int nObjs     () const {return (int) objectives_.   size ();} 
  int nCons     () const {return (int) constraints_.  size ();} 
  int nOrigCons () const {return nOrigCons_;}                   

  inline int nOrigVars    () const {return nOrigVars_;}                
  inline int nDefVars     () const {return ndefined_;}                 
  inline int nOrigIntVars () const {return nOrigIntVars_;}             
  inline int nIntVars     () const {return nIntVars_;}                 
  inline int nVars        () const {return (int) variables_. size ();} 
  
  void setNDefVars (int ndefined__) {ndefined_ = ndefined__;}

  // Symmetry Info

  std::vector<int>  *Find_Orbit(int) const;
  mutable std::vector<Node> node_info;
  mutable Nauty *nauty_info;

  myclass0  node_sort; 
  myclass index_sort;

  void sym_setup();
  void Compute_Symmetry() const;
  void Print_Orbits() const;
  void ChangeBounds (const double * , const double *, int ) const;
  inline bool compare (register Node &a, register Node &b) const;
  Nauty *getNtyInfo () {return nauty_info;}

  // bool node_sort (  Node  a, Node  b);
  // bool index_sort (  Node  a, Node  b);

  void setupSymmetry ();
  
  inline int evalOrder (int i) const
  {return numbering_ [i];}

  inline int *evalVector ()
  {return numbering_;}

  // get elements from vectors
  inline CouenneConstraint *Con (int i) const {return constraints_ [i];} 
  inline CouenneObjective  *Obj (int i) const {return objectives_  [i];} 

  inline exprVar *Var   (int i) const 
  {return variables_ [i];}

  inline std::vector <exprVar *> &Variables () 
  {return variables_;}

  inline std::set <exprAux *, compExpr> *& AuxSet () 
  {return auxSet_;}

  inline DepGraph *getDepGraph () 
  {return graph_;}

  inline Domain *domain () const
  {return &domain_;}
  
  inline std::vector <expression *>& commonExprs() { return commonexprs_; }

  // Get and set current variable and bounds
  inline CouNumber   &X     (int i) const {return domain_.x   (i);} 
  inline CouNumber   &Lb    (int i) const {return domain_.lb  (i);} 
  inline CouNumber   &Ub    (int i) const {return domain_.ub  (i);} 

  // get and set current variable and bounds
  inline CouNumber  *X     () const {return domain_.x  ();} 
  inline CouNumber  *Lb    () const {return domain_.lb ();} 
  inline CouNumber  *Ub    () const {return domain_.ub ();} 

  // get optimal solution and objective value
  CouNumber  *&bestSol () const {return optimum_;} 
  CouNumber    bestObj () const {return bestObj_;} 

  bool *&Commuted () 
  {return commuted_;}

  void addObjective     (expression *, const std::string & = "min");

  // Add (non linear) "=", ">=", "<=", and range constraints
  void addEQConstraint  (expression *, expression * = NULL); 
  void addGEConstraint  (expression *, expression * = NULL); 
  void addLEConstraint  (expression *, expression * = NULL); 
  void addRNGConstraint (expression *, expression * = NULL, 
                                       expression * = NULL); 

  void setObjective (int indObj = 0, expression * = NULL, const std::string & = "min");

  expression *addVariable (bool isint = false, Domain *d = NULL);

  exprAux *addAuxiliary (expression *);

  void reformulate (CouenneCutGenerator * = NULL);

  bool standardize ();

  void print (std::ostream & = std::cout);

#ifdef COIN_HAS_ASL
  int readnl (const struct ASL *);

  expression *nl2e (struct expr *, const ASL *asl);
#endif

  // bound tightening parameters
  bool doFBBT () const {return (doFBBT_ && (max_fbbt_iter_ != 0));} 
  bool doRCBT () const {return doRCBT_;}                            
  bool doOBBT () const {return doOBBT_;}                            
  bool doABT  () const {return doABT_;}                             

  int  logObbtLev () const {return logObbtLev_;} 
  int  logAbtLev  () const {return logAbtLev_;}  

  void writeAMPL (const std::string &fname, bool aux);

  void writeGAMS (const std::string &fname);

  void writeLP (const std::string &fname);

  //void initAuxs (const CouNumber *, const CouNumber *, const CouNumber *);
  void initAuxs () const;

  void getAuxs (CouNumber *) const;

  bool boundTightening (t_chg_bounds *,
                        const CglTreeInfo info, 
                        Bonmin::BabInfo * = NULL) const;

  bool btCore (t_chg_bounds *chg_bds) const;

  int obbt (const CouenneCutGenerator *cg,
            const OsiSolverInterface &csi,
            OsiCuts &cs,
            const CglTreeInfo &info,
            Bonmin::BabInfo * babInfo,
            t_chg_bounds *chg_bds);

  bool aggressiveBT (Bonmin::OsiTMINLPInterface *nlp,
                     t_chg_bounds *, 
                     const CglTreeInfo &info,
                     Bonmin::BabInfo * = NULL) const;

  int redCostBT (const OsiSolverInterface *psi,
                 t_chg_bounds *chg_bds) const;

  int tightenBounds (t_chg_bounds *) const;

  int impliedBounds (t_chg_bounds *) const;

  void fillQuadIndices ();

  void fillObjCoeff (double *&);

  void auxiliarize (exprVar *, exprVar * = NULL);

  void setCutOff (CouNumber cutoff, const CouNumber *sol = NULL) const;

  void resetCutOff (CouNumber value = COUENNE_INFINITY) const;

  CouNumber getCutOff () const;

  CouNumber *getCutOffSol () const;

  void installCutOff () const;

  ConstJnlstPtr Jnlst () const;

  bool checkNLP (const double *solution, double &obj, bool recompute = false) const;

  int getIntegerCandidate (const double *xFrac, double *xInt, double *lb, double *ub) const;

  bool readOptimum (std::string *fname = NULL);

  static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions);

  exprAux *linStandardize (bool addAux, 
                           CouNumber c0, 
                           LinMap  &lmap,
                           QuadMap &qmap);

  int splitAux (CouNumber, expression *, expression *&, bool *, enum expression::auxSign &);

  void indcoe2vector (int *indexL,
                      CouNumber *coeff,
                      std::vector <std::pair <exprVar *, CouNumber> > &lcoeff);

  void indcoe2vector (int *indexI,
                      int *indexJ,
                      CouNumber *coeff,
                      std::vector <quadElem> &qcoeff);

  void decomposeTerm (expression *term,
                      CouNumber initCoe,
                      CouNumber &c0,
                      LinMap  &lmap,
                      QuadMap &qmap);

  const std::string &problemName () const
  {return problemName_;}
  
  void setProblemName(std::string& problemName__)
  { problemName_ = problemName__; }

  const std::vector <std::set <int> > &Dependence () const
  {return dependence_;}

  const std::vector <CouenneObject *> &Objects () const
  {return objects_;}

  int findSOS (CbcModel *CbcModelPtr,
               OsiSolverInterface *solver, 
               OsiObject ** objects);

  inline void setMaxCpuTime (double time)
  {maxCpuTime_ = time;}

  inline double getMaxCpuTime () const
  {return maxCpuTime_;}

  void setBase (Bonmin::BabSetupBase *base);

  void createUnusedOriginals ();

  void restoreUnusedOriginals (CouNumber * = NULL) const;

  int *unusedOriginalsIndices () 
  {return unusedOriginalsIndices_;}

  int nUnusedOriginals ()
  {return nUnusedOriginals_;}

  enum multiSep MultilinSep () const
  {return multilinSep_;}

  bool fbbtReachedIterLimit () const
  {return fbbtReachedIterLimit_;}

  bool orbitalBranching () const
  {return orbitalBranching_;}

  void setCheckAuxBounds (bool value) 
  {checkAuxBounds_ = value;}

  bool checkAuxBounds () const
  {return checkAuxBounds_;}

  enum TrilinDecompType getTrilinDecompType ()
  {return trilinDecompType_;}

  Bonmin::BabSetupBase *bonBase () const {return bonBase_;}

  inline double constObjVal () const {return constObjVal_;}

  CouenneSdpCuts *getSdpCutGen () {return sdpCutGen_;}

protected:

  int fake_tighten (char direction,  
                    int index,       
                    const double *X, 
                    CouNumber *olb,  
                    CouNumber *oub,  
                    t_chg_bounds *chg_bds,
                    t_chg_bounds *f_chg) const;

  int obbtInner (OsiSolverInterface *, 
                 OsiCuts &,
                 t_chg_bounds *, 
                 Bonmin::BabInfo *) const;

  int obbt_iter (OsiSolverInterface *csi, 
                 t_chg_bounds *chg_bds, 
                 const CoinWarmStart *warmstart, 
                 Bonmin::BabInfo *babInfo,
                 double *objcoe,
                 int sense, 
                 int index) const;

  int call_iter (OsiSolverInterface *csi, 
                 t_chg_bounds *chg_bds, 
                 const CoinWarmStart *warmstart, 
                 Bonmin::BabInfo *babInfo,
                 double *objcoe,
                 enum nodeType type,
                 int sense) const;

  void analyzeSparsity (CouNumber, 
                        LinMap &,
                        QuadMap &);

  void flattenMul (expression *mul, 
                   CouNumber &coe, 
                   std::map <int, CouNumber> &indices);

  void realign ();

  void fillDependence (Bonmin::BabSetupBase *base, CouenneCutGenerator * = NULL);

  void fillIntegerRank () const;

  int testIntFix (int index, 
                  CouNumber xFrac, 
                  enum fixType *fixed,
                  CouNumber *xInt,
                  CouNumber *dualL, CouNumber *dualR,
                  CouNumber *olb,   CouNumber *oub,
                  bool patient) const;

public:

  inline int getLastPrioSort() const 
  {return lastPrioSort_;}

  void setLastPrioSort (int givenLastPS);

  inline CouenneRecordBestSol *getRecordBestSol() const 
  {return recBSol;}

  double getFeasTol() {return feas_tolerance_;}

  double checkObj(const CouNumber *sol, const double &precision) const;

  bool checkInt(const CouNumber *sol,
                const int from, const int upto, 
                const std::vector<int> listInt,
                const bool origVarOnly, 
                const bool stopAtFirstViol,
                const double precision, double &maxViol) const;

  bool checkBounds(const CouNumber *sol,
                   const bool stopAtFirstViol,
                   const double precision, double &maxViol) const;

  bool checkAux(const CouNumber *sol,
                const bool stopAtFirstViol,
                const double precision, double &maxViol) const;

  bool checkCons(const CouNumber *sol,
                 const bool stopAtFirstViol,
                 const double precision, double &maxViol) const;




  bool checkNLP2 (const double *solution,
                  const double obj, 
                  const bool careAboutObj,
                  const bool stopAtFirstViol,
                  const bool checkAll,
                  const double precision) const;

  bool checkNLP0 (const double *solution,
                 double &obj,
                 bool recompute_obj         = false,
                 const bool careAboutObj    = false,
                 const bool stopAtFirstViol = true,
                 const bool checkAll        = false,
                 const double precision     = -1) const; // if -1 then use feas_tolerance_

  std::vector <CouenneConstraint *> *ConstraintClass (const char *str) {return ConstraintClass_ [str];}
};

}

#endif