1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the HiGHS linear optimization suite */ 4 /* */ 5 /* Written and engineered 2008-2021 at the University of Edinburgh */ 6 /* */ 7 /* Available as open-source under the MIT License */ 8 /* */ 9 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 10 #ifndef HIGHS_LP_RELAXATION_H_ 11 #define HIGHS_LP_RELAXATION_H_ 12 13 #include <memory> 14 15 #include "Highs.h" 16 #include "mip/HighsMipSolver.h" 17 18 class HighsDomain; 19 class HighsCutSet; 20 class HighsPseudocost; 21 22 class HighsLpRelaxation { 23 public: 24 enum class Status { 25 NotSet, 26 Optimal, 27 Infeasible, 28 UnscaledDualFeasible, 29 UnscaledPrimalFeasible, 30 UnscaledInfeasible, 31 Error, 32 }; 33 34 private: 35 const HighsMipSolver& mipsolver; 36 Highs lpsolver; 37 std::vector<int> lp2cutpoolindex; 38 std::vector<std::pair<int, double>> fractionalints; 39 std::vector<double> dualproofvals; 40 std::vector<int> dualproofinds; 41 std::vector<double> dualproofbuffer; 42 double dualproofrhs; 43 bool hasdualproof; 44 double objective; 45 std::shared_ptr<const HighsBasis> basischeckpoint; 46 bool currentbasisstored; 47 size_t numlpiters; 48 Status status; 49 50 void storeDualInfProof(); 51 52 void storeDualUBProof(); 53 54 bool checkDualProof() const; 55 56 public: 57 HighsLpRelaxation(const HighsMipSolver& mip); 58 59 HighsLpRelaxation(const HighsLpRelaxation& other); 60 getCutIndex(int lpindex)61 int getCutIndex(int lpindex) const { 62 return lp2cutpoolindex[lpindex - mipsolver.numRow()]; 63 } 64 getStatus()65 Status getStatus() const { return status; } 66 getNumLpIterations()67 size_t getNumLpIterations() const { return numlpiters; } 68 integerFeasible()69 bool integerFeasible() const { 70 if ((status == Status::Optimal || 71 status == Status::UnscaledPrimalFeasible) && 72 fractionalints.empty()) 73 return true; 74 75 return false; 76 } 77 78 double computeBestEstimate(const HighsPseudocost& ps) const; 79 scaledOptimal(Status status)80 static bool scaledOptimal(Status status) { 81 switch (status) { 82 case Status::Optimal: 83 case Status::UnscaledDualFeasible: 84 case Status::UnscaledPrimalFeasible: 85 case Status::UnscaledInfeasible: 86 return true; 87 default: 88 return false; 89 } 90 } 91 unscaledPrimalFeasible(Status status)92 static bool unscaledPrimalFeasible(Status status) { 93 switch (status) { 94 case Status::Optimal: 95 case Status::UnscaledPrimalFeasible: 96 return true; 97 default: 98 return false; 99 } 100 } 101 unscaledDualFeasible(Status status)102 static bool unscaledDualFeasible(Status status) { 103 switch (status) { 104 case Status::Optimal: 105 case Status::UnscaledDualFeasible: 106 return true; 107 default: 108 return false; 109 } 110 } 111 112 void recoverBasis(); 113 114 void setObjectiveLimit(double objlim = HIGHS_CONST_INF) { 115 // lpsolver.setHighsOptionValue("dual_objective_value_upper_bound", objlim); 116 } 117 storeBasis()118 void storeBasis() { 119 if (!currentbasisstored) { 120 basischeckpoint = std::make_shared<HighsBasis>(lpsolver.getBasis()); 121 currentbasisstored = true; 122 } 123 } 124 getStoredBasis()125 std::shared_ptr<const HighsBasis> getStoredBasis() const { 126 return basischeckpoint; 127 } 128 setStoredBasis(std::shared_ptr<const HighsBasis> basis)129 void setStoredBasis(std::shared_ptr<const HighsBasis> basis) { 130 basischeckpoint = basis; 131 currentbasisstored = false; 132 } 133 getMipSolver()134 const HighsMipSolver& getMipSolver() const { return mipsolver; } 135 getNumModelRows()136 int getNumModelRows() const { return mipsolver.numRow(); } 137 getNumLpRows()138 int getNumLpRows() const { return lpsolver.getNumRows(); } 139 140 void addCuts(HighsCutSet& cutset); 141 142 void removeCuts(int ndelcuts, std::vector<int>& deletemask); 143 144 void removeCuts(); 145 146 void flushDomain(HighsDomain& domain, bool continuous = false); 147 rowLower(int row)148 double rowLower(int row) const { return lpsolver.getLp().rowLower_[row]; } 149 rowUpper(int row)150 double rowUpper(int row) const { return lpsolver.getLp().rowUpper_[row]; } 151 getDualProof(const int * & inds,const double * & vals,double & rhs,int & len)152 void getDualProof(const int*& inds, const double*& vals, double& rhs, 153 int& len) { 154 inds = dualproofinds.data(); 155 vals = dualproofvals.data(); 156 rhs = dualproofrhs; 157 len = dualproofinds.size(); 158 } 159 160 bool computeDualProof(const HighsDomain& globaldomain, double upperbound, 161 std::vector<int>& inds, std::vector<double>& vals, 162 double& rhs) const; 163 164 bool computeDualInfProof(const HighsDomain& globaldomain, 165 std::vector<int>& inds, std::vector<double>& vals, 166 double& rhs); 167 168 Status resolveLp(); 169 170 Status run(bool resolve_on_error = true); 171 getLpSolver()172 Highs& getLpSolver() { return lpsolver; } getLpSolver()173 const Highs& getLpSolver() const { return lpsolver; } 174 getFractionalIntegers()175 const std::vector<std::pair<int, double>>& getFractionalIntegers() const { 176 return fractionalints; 177 } 178 getFractionalIntegers()179 std::vector<std::pair<int, double>>& getFractionalIntegers() { 180 return fractionalints; 181 } 182 getObjective()183 double getObjective() const { return objective; } 184 185 void setIterationLimit(int limit = HIGHS_CONST_I_INF) { 186 lpsolver.setHighsOptionValue("simplex_iteration_limit", limit); 187 } 188 }; 189 190 #endif