kPowHandler.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 "CGraph.h"
#include "Handler.h"
 
namespace Minotaur {
 
class LinearFunction;
class Timer;
class LPEngine;
typedef LPEngine *LPEnginePtr;
typedef LinearFunction *LinearFunctionPtr;
typedef Engine *EnginePtr;
 
struct LinkPow {
  VariablePtr y;        
  VariablePtr x;        
  double k;             
  ConstraintPtr oeCon;  
};
typedef LinkPow *LinkPowPtr;                  
typedef std::vector<LinkPowPtr> LinkPowVec;   
typedef LinkPowVec::iterator LinkPowVecIter;  
 
typedef std::map<VariablePtr, LinkPowPtr, CompareVariablePtr> LinkPowMap;
typedef LinkPowMap::iterator LinkPowMapIter;  
 
class kPowHandler : public Handler {
 public:
  // kPowHandler(EnvPtr env, ProblemPtr problem);
 
  kPowHandler(EnvPtr env, ProblemPtr problem, ProblemPtr orig_p);
 
  ~kPowHandler();
 
  // base class method
  void addConstraint(ConstraintPtr newcon);
 
  // 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);
 
  // 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 *, bool *is_inf);
 
  // Does nothing.
  void relaxInitInc(RelaxationPtr rel, SolutionPool *, 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);
 
  // 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 setNLPEngine(EnginePtr engine);
 
  // base class method.
  void writeStats(std::ostream &out) const;
 
 private:
  struct SepaStats {
    int iters;    
    int cuts;     
    double time;  
  };
 
  struct PresolveStats {
    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 kPow tightening
    // int nqubq;         ///> Number of Quadratic variables whose ub was
    //                   ///> found by kPow tightening
    // int vBndq;         ///> Number of times bounds tightened by
    //                   ///> kPow tightening
    // int cBndq;         ///> Number of times cons tightened by
    //                   ///> kPow 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_;
 
  EnginePtr nlpe_;
 
  NLPStats nlpStats_;
 
  static const std::string me_;
 
  ProblemPtr orig_;
 
  ProblemPtr p_;
 
  PresolveStats pStats_;
 
  bool doQT_;
 
  double rTol_;
 
  SepaStats sStats_;
 
  const Timer *timer_;
 
  LinkPowMap xkFuns_;
 
  void addCut_(VariablePtr x, VariablePtr y, double xl, double yl, double xval,
               double yval, RelaxationPtr rel, bool &ifcuts, double k);
 
  double addDefaultBounds_(VariablePtr x, BoundType lu);
 
  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 findLinPt_(double xval, double yval, double &xl, double &yl, double k);
 
  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 getNewKpowLf_(VariablePtr y, VariablePtr x, double k,
                                  double lb, double ub, double &rhs, int type);
 
  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 isAtBnds_(ConstVariablePtr x, double xval);
 
  bool isFeasibleToRelaxation_(RelaxationPtr rel, const double *x);
 
  bool propKPowBnds_(LinkPowMapIter lxk, bool *changed);
 
  bool propKPowBnds_(LinkPowMapIter lxk, RelaxationPtr rel, bool mod_rel,
                     bool *changed, ModVector &p_mods, ModVector &r_mods);
 
  void relax_(RelaxationPtr rel, bool *is_inf);
 
  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 tightenkPow_(bool *changed);
 
  bool tightenkPow_(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);
 
  int updatePBounds_(VariablePtr v, double lb, double ub, bool *changed);
 
  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 &sol_found);
 
  void upSqCon_(ConstraintPtr con, VariablePtr x, VariablePtr y, double k,
                RelaxationPtr rel, ModVector &r_mods);
 
  bool varBndsFromCons_(bool *changed);
};
 
typedef kPowHandler *kPowHandlerPtr;
}  // namespace Minotaur
#endif