QuadHandler.h

Go to the documentation of this file.

//
//     Minotaur -- It's only 1/2 bull
//
//     (C)opyright 2008 - 2025 The Minotaur Team.
//
 
#ifndef MINOTAURQUADRATICHANDLER_H
#define MINOTAURQUADRATICHANDLER_H
 
#include "Handler.h"
#include "LinBil.h"
#include "SimplexQuadCutGen.h"
 
namespace Minotaur
{
 
class LinearFunction;
class Timer;
typedef LinearFunction* LinearFunctionPtr;
typedef Engine* EnginePtr;
 
struct LinSqr {
  VariablePtr y;       
  VariablePtr x;       
  ConstraintPtr oeCon; 
  ConstraintPtr qcon;  
  LinSqr(VariablePtr y0, VariablePtr x0, ConstraintPtr con)
  {
    y = y0;
    x = x0;
    oeCon = ConstraintPtr();
    qcon = con;
  }
};
typedef LinSqr* LinSqrPtr;                 
typedef std::vector<LinSqrPtr> LinSqrVec;  
typedef LinSqrVec::iterator LinSqrVecIter; 
 
typedef std::map<VariablePtr, LinSqrPtr, CompareVariablePtr> LinSqrMap;
typedef LinSqrMap::iterator LinSqrMapIter; 
 
class QuadHandler : public Handler
{
public:
  QuadHandler(EnvPtr env, ProblemPtr problem);
 
  QuadHandler(EnvPtr env, ProblemPtr problem, ProblemPtr orig_p);
 
  ~QuadHandler();
 
  // base class method
  void addConstraint(ConstraintPtr newcon);
 
  double addDefaultBounds(VariablePtr x, BoundType lu);
 
  // Implement Handler::getBranches().
  Branches getBranches(BrCandPtr cand, DoubleVector& x, RelaxationPtr rel,
                       SolutionPoolPtr s_pool);
 
  // base class method
  void getBranchingCandidates(RelaxationPtr rel, const DoubleVector& x,
                              ModVector& mods, BrVarCandSet& cands,
                              BrCandVector& gencands, bool& is_inf);
 
  // base class method
  ModificationPtr getBrMod(BrCandPtr cand, DoubleVector& x, RelaxationPtr rel,
                           BranchDirection dir);
 
  // base class method
  std::string getName() const;
 
  // base class method.
  bool isFeasible(ConstSolutionPtr sol, RelaxationPtr relaxation,
                  bool& should_prune, double& inf_meas);
 
  // base class method.
  SolveStatus presolve(PreModQ* pre_mods, bool* changed, Solution** sol);
 
  // base class method. Tightens bounds.
  bool presolveNode(RelaxationPtr p, NodePtr node, SolutionPoolPtr s_pool,
                    ModVector& p_mods, ModVector& r_mods);
 
  // implement Handler::postSolveRootNode
  bool postSolveRootNode(RelaxationPtr rel, SolutionPoolPtr s_pool,
                         ConstSolutionPtr sol, ModVector& p_mods,
                         ModVector& r_mods);
 
  void fillmap4auxVars(std::map<std::pair<int, int>, int>& map4auxVars);
 
  // implement Handler::fixNodeErr
  int fixNodeErr(RelaxationPtr rel, ConstSolutionPtr sol,
                 SolutionPoolPtr s_pool, bool& sol_found);
 
  // base class method. Adds linear inequalities
  void relaxInitFull(RelaxationPtr rel, SolutionPool* sp, bool* is_inf);
 
  // Does nothing.
  void relaxInitInc(RelaxationPtr rel, SolutionPool* sp, bool* is_inf);
 
  // Does nothing.
  void relaxNodeFull(NodePtr node, RelaxationPtr rel, bool* is_inf);
 
  // Does nothing.
  void relaxNodeInc(NodePtr node, RelaxationPtr rel, bool* is_inf);
 
  void removeCuts(RelaxationPtr rel, ConstSolutionPtr sol);
 
  // base class method. Adds linearlization cuts when available.
  void separate(ConstSolutionPtr sol, NodePtr node, RelaxationPtr rel,
                CutManager* cutman, SolutionPoolPtr s_pool, ModVector& p_mods,
                ModVector& r_mods, bool* sol_found, SeparationStatus* status);
 
  void setBTEngine(LPEnginePtr engine);
 
  void setCutEngine(LPEnginePtr engine);
 
  void setNLPEngine(EnginePtr engine);
 
  void simplePresolve(ProblemPtr p, SolutionPoolPtr spool, ModVector& t_mods,
                      SolveStatus& status);
  // base class method.
  void writeStats(std::ostream& out) const;
 
private:
  struct SepaStats {
    int iters;       
    int tangentcuts; 
    int optcuts;     
    int optrem;      
    double time;     
  };
 
  struct PresolveStats {
    int conDel; 
    int iters;    
    double time;  
    double timeN; 
    int vBnd;     
    int nMods;    
  };
 
  struct NLPStats {
    bool flag;       
    UInt nlp;        
    UInt opt;        
    UInt inf;        
    UInt iter_limit; 
  };
 
  struct BoundTighteningStats {
    int niters; 
    // VariableSet qvars; ///> The variables with quadratic terms
    // int nqlb;          ///> Number of quadratic variables with finite lb
    // int nqub;          ///> Number of quadratic variables with finite ub
    // int nqlbs;         ///> Number of quadratic variables whose lb was
    //                   ///> found by simple tightening
    // int nqubs;         ///> Number of quadratic variables whose ub was
    //                   ///> found by simple tightening
    // int vBnds;         ///> Number of times bounds tightened by
    //                   ///> simple tightening
    // int cBnds;         ///> Number of times cons tightened by
    //                   ///> simple tightening
    // int nqlbq;         ///> Number of quadratic variables whose lb was
    //                   ///> found by quad tightening
    // int nqubq;         ///> Number of quadratic variables whose ub was
    //                   ///> found by quad tightening
    // int vBndq;         ///> Number of times bounds tightened by
    //                   ///> quad tightening
    // int cBndq;         ///> Number of times cons tightened by
    //                   ///> quad tightening
    // int nqlbl;         ///> Number of quadratic variables whose lb was
    //                   ///> found by lp tightening
    // int nqubl;         ///> Number of quadratic variables whose ub was
    //                   ///> found by lp tightening
    // int vBndl;         ///> Number of times bounds tightened by
    //                   ///> lp tightening
    int nLP;       
    int dlb;       
    int dub;       
    double timeLP; 
    // double avg_range;  ///> Average range of bounds of quadratic variables
    // double sd_range;   ///> Standard deviation of range
    // double body_diag;  ///> The length of body diagonal of hypercube formed
    // by
    //                   ///> the range of quadratic variables
  };
 
  double aTol_;
 
  BoundTighteningStats bStats_;
 
  double bTol_;
 
  double defaultLb_;
 
  double defaultUb_;
 
  EnvPtr env_;
 
  LoggerPtr logger_;
 
  LPEnginePtr bte_;
 
  LPEnginePtr cute_;
 
  EnginePtr nlpe_;
 
  NLPStats nlpStats_;
 
  static const std::string me_;
 
  ProblemPtr orig_;
 
  ProblemPtr p_;
 
  PresolveStats pStats_;
 
  bool doQT_;
 
  ConstraintVector optCuts_;
 
  double rTol_;
 
  SimplexQuadCutGenPtr simplexCut_;
 
  SepaStats sStats_;
 
  const Timer* timer_;
 
  LinBilSet x0x1Funs_;
 
  LinSqrMap x2Funs_;
 
  void addCut_(VariablePtr x, VariablePtr y, double xl, double yl, double xval,
               double yval, RelaxationPtr rel, bool& ifcuts);
 
  ConstraintPtr addTangent_(VariablePtr x, VariablePtr y, double pt,
                            RelaxationPtr rel);
 
  double calcUpperUnivar_(double a, double b, double lx, double ux);
 
  bool calcVarBnd_(VariablePtr v, double coef, double lb, double ub, bool* c1);
 
  bool calcVarBnd_(RelaxationPtr rel, VariablePtr v, double coef, double lb,
                   double ub, bool* c1, ModVector& p_mods, ModVector& r_mods);
 
  bool calcVarBnd_(VariablePtr v1, VariablePtr v2, double coef, double lb,
                   double ub, bool* c1, bool* c2);
 
  bool calcVarBnd_(RelaxationPtr rel, VariablePtr v1, VariablePtr v2,
                   double coef, double lb, double ub, bool* c1, bool* c2,
                   ModVector& p_mods, ModVector& r_mods);
 
  bool calcVarBnd_(VariablePtr v, double a, double b, double ly, double uy,
                   bool* c1);
 
  bool calcVarBnd_(RelaxationPtr rel, VariablePtr v, double a, double b,
                   double ly, double uy, bool* c1, ModVector& p_mods,
                   ModVector& r_mods);
 
  void coeffImprov_();
 
  void dupRows_(bool* changed);
 
  void findLinPt_(double xval, double yval, double& xl, double& yl);
 
  double getBndByLP_(bool& is_inf);
 
  void getLfBnds_(LinearFunctionPtr lf, double& implLb, double& implUb,
                  DoubleVector& fwdLb, DoubleVector& fwdUb, UInt& count_inf_lb,
                  UInt& count_inf_ub);
 
  LinearFunctionPtr getNewBilLf_(VariablePtr x0, double lb0, double ub0,
                                 VariablePtr x1, double lb1, double ub1,
                                 VariablePtr y, int type, double& rhs);
 
  LinearFunctionPtr getNewSqLf_(VariablePtr x, VariablePtr y, double lb,
                                double ub, double& r);
 
  void getQfBnds_(QuadraticFunctionPtr qf, double& implLb, double& implUb,
                  DoubleVector& fwdLb, DoubleVector& fwdUb, UInt& count_inf_lb,
                  UInt& count_inf_ub);
 
  bool getQfLfBnds_(LinearFunctionPtr lf, QuadraticFunctionPtr qf,
                    double& implLb, double& implUb, DoubleVector& fwdLb,
                    DoubleVector& fwdUb, UInt& count_inf_lb, UInt& count_inf_ub,
                    VarVector& qvars);
 
  bool getQfLfBnds_(RelaxationPtr rel, LinearFunctionPtr lf,
                    QuadraticFunctionPtr qf, double& implLb, double& implUb,
                    DoubleVector& fwdLb, DoubleVector& fwdUb,
                    UInt& count_inf_lb, UInt& count_inf_ub, VarVector& qvars);
 
  double getSumExcept1_(DoubleVector::iterator b, DoubleVector::iterator e,
                        DoubleVector::iterator curr, BoundType bt, double bound,
                        UInt inf_count);
 
  void getTermBnds_(VariablePtr v, double coef, double& lb, double& ub);
 
  void getTermBnds_(VariablePtr v1, VariablePtr v2, double coef, double& lb,
                    double& ub);
 
  void getTermBnds_(VariablePtr v, double a, double b, double& lb, double& ub);
 
  bool isActive_(ConstraintPtr c, ConstSolutionPtr sol);
 
  bool isAtBnds_(ConstVariablePtr x, double xval);
 
  bool isFeasible_(const double* x, double objval, double& inf_meas);
 
  bool isFeasibleToRelaxation_(RelaxationPtr rel, const double* x);
 
  void linearize_(LinSqrMapIter lx2);
 
  bool linearize_(LinBilSetIter linbil, bool isx0Binary, bool isx1Binary);
 
  bool propBilBnds_(LinBil* lx0x1, bool* changed);
 
  bool propBilBnds_(LinBil* lx0x1, RelaxationPtr rel, bool mod_rel,
                    bool* changed, ModVector& p_mods, ModVector& r_mods);
 
  bool propSqrBnds_(LinSqrMapIter lx2, bool* changed);
 
  bool propSqrBnds_(LinSqrMapIter lx2, RelaxationPtr rel, bool mod_rel,
                    bool* changed, ModVector& p_mods, ModVector& r_mods);
 
  void relax_(RelaxationPtr rel, bool* is_inf);
 
  void removeCut_(RelaxationPtr rel, ConstraintPtr c);
 
  void resetBoundsinOrig_(DoubleVector& varlb, DoubleVector& varub);
 
  void resetStats_();
 
  void setItmpFromSol_(const double* x);
 
  bool tightenLP_(RelaxationPtr rel, double bestSol, bool* changed,
                  ModVector& p_mods, ModVector& r_mods);
 
  bool tightenQuad_(bool* changed);
 
  bool tightenQuad_(RelaxationPtr rel, double bestSol, bool* changed,
                    ModVector& p_mods, ModVector& r_mods);
 
  bool tightenSimple_(bool* changed);
 
  void updateBoundsinOrig_(RelaxationPtr rel, const double* x,
                           DoubleVector& varlb, DoubleVector& varub);
 
  bool treatDupRows_(ConstraintPtr c1, ConstraintPtr c2, double mult,
                     bool* changed);
 
  int updatePBounds_(VariablePtr v, double lb, double ub, bool* changed);
 
  int updatePBounds_(ProblemPtr p, VariablePtr v, double lb, double ub,
                     ModVector& mods);
 
  int updatePBounds_(VariablePtr v, double lb, double ub, RelaxationPtr rel,
                     bool mod_rel, bool* changed, ModVector& p_mods,
                     ModVector& r_mods);
  void updateUb_(SolutionPoolPtr s_pool, double nlpval, bool check_feas,
                 bool& sol_found);
 
  void upBilCon_(LinBil* lx0x1, RelaxationPtr rel, ModVector& r_mods);
 
  void upSqCon_(LinSqrPtr ls, RelaxationPtr rel, ModVector& r_mods);
 
  bool varBndsFromCons_(bool* changed);
};
 
typedef QuadHandler* QuadHandlerPtr;
} // namespace Minotaur
#endif