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