Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
highs_solver.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_MATH_OPT_SOLVERS_HIGHS_SOLVER_H_
15#define OR_TOOLS_MATH_OPT_SOLVERS_HIGHS_SOLVER_H_
16
17#include <cmath>
18#include <cstdint>
19#include <memory>
20#include <optional>
21#include <utility>
22#include <vector>
23
24#include "Highs.h"
25#include "absl/container/flat_hash_map.h"
26#include "absl/status/status.h"
27#include "absl/status/statusor.h"
28#include "lp_data/HConst.h"
29#include "lp_data/HighsInfo.h"
41
43
44class HighsSolver : public SolverInterface {
45 public:
46 static absl::StatusOr<std::unique_ptr<SolverInterface>> New(
47 const ModelProto& model, const InitArgs& init_args);
48
49 absl::StatusOr<SolveResultProto> Solve(
50 const SolveParametersProto& parameters,
51 const ModelSolveParametersProto& model_parameters,
52 MessageCallback message_cb,
53 const CallbackRegistrationProto& callback_registration, Callback cb,
54 const SolveInterrupter* interrupter) override;
55 absl::StatusOr<bool> Update(const ModelUpdateProto& model_update) override;
56 absl::StatusOr<ComputeInfeasibleSubsystemResultProto>
58 MessageCallback message_cb,
59 const SolveInterrupter* interrupter) override;
60
61 private:
62 struct SolutionClaims {
63 bool highs_returned_primal_feasible_solution = false;
64 bool highs_returned_dual_feasible_solution = false;
65 bool highs_returned_primal_ray = false;
66 bool highs_returned_dual_ray = false;
67 };
68 struct SolutionsAndClaims {
69 std::vector<SolutionProto> solutions;
70 // TODO(b/271104776): add rays.
71 SolutionClaims solution_claims;
72 };
73
74 // Tracks the upper and lower bounds for either a variable or linear
75 // constraint in the HiGHS model.
76 //
77 // Note that HiGHS does not allow bounds to cross. If a bound would cross, it
78 // is set to zero in the actual HiGHS model and its true values are tracked
79 // here (they may uncross before solve time on a model update).
80 struct IndexAndBound {
81 // The position of the variable/linear constraint in the HiGHS model. Note
82 // that this is distinct from the MathOpt id.
83 int index;
84 double lb;
85 double ub;
86
87 // TODO(b/271595607): we won't need to track this once a bug in HiGHS is
88 // fixed. Always false for constraints.
89 bool is_integer;
90
91 bool bounds_cross() const { return lb > ub; }
92
93 // If we don't round the bounds for integer variables, HiGHS can give
94 // garbage results, see go/paste/4836036214521856 for details. See also
95 // b/271595607.
96 double rounded_lb() const { return is_integer ? std::ceil(lb) : lb; }
97 double rounded_ub() const { return is_integer ? std::floor(ub) : ub; }
98 bool rounded_bounds_cross() const { return rounded_lb() > rounded_ub(); }
99
100 IndexAndBound(int index, double lb, double ub, bool is_integer)
101 : index(index), lb(lb), ub(ub), is_integer(is_integer) {}
102 };
103 HighsSolver(std::unique_ptr<Highs> highs,
104 absl::flat_hash_map<int64_t, IndexAndBound> variable_data,
105 absl::flat_hash_map<int64_t, IndexAndBound> lin_con_data)
106 : highs_(std::move(highs)),
107 variable_data_(std::move(variable_data)),
108 lin_con_data_(std::move(lin_con_data)) {}
109
110 absl::StatusOr<bool> PrimalRayReturned() const;
111 absl::StatusOr<bool> DualRayReturned() const;
112
113 // Will append solutions and rays to result_out. No other modifications are
114 // made to result_out. Requires that highs_->getInfo is validated.
115 absl::StatusOr<SolutionsAndClaims> ExtractSolutionAndRays(
116 const ModelSolveParametersProto& model_params);
117
118 static absl::StatusOr<FeasibilityStatusProto> PrimalFeasibilityStatus(
119 SolutionClaims solution_claims);
120 static absl::StatusOr<FeasibilityStatusProto> DualFeasibilityStatus(
121 const HighsInfo& highs_info, bool is_integer,
122 SolutionClaims solution_claims);
123 static absl::StatusOr<TerminationProto> MakeTermination(
124 HighsModelStatus highs_model_status, const HighsInfo& highs_info,
125 bool is_integer, bool had_node_limit, bool had_solution_limit,
126 bool is_maximize, SolutionClaims solution_claims);
127
128 // Returns the current basis if it is available and MathOpt can represent it
129 // (all kNonBasic values can be made more precise, see b/272767311).
130 absl::StatusOr<std::optional<BasisProto>> ExtractBasis();
131
132 template <typename T>
133 absl::Status EnsureOneEntryPerVariable(const std::vector<T>& vec) {
134 if (vec.size() != variable_data_.size()) {
136 << "expected one entry per variable, but model had "
137 << variable_data_.size() << " variables and found " << vec.size()
138 << " elements";
139 }
140 return absl::OkStatus();
141 }
142
143 template <typename T>
144 absl::Status EnsureOneEntryPerLinearConstraint(const std::vector<T>& vec) {
145 if (vec.size() != lin_con_data_.size()) {
147 << "expected one entry per linear constraint, but model had "
148 << lin_con_data_.size() << " linear constraints and found "
149 << vec.size() << " elements";
150 }
151 return absl::OkStatus();
152 }
153
154 // Returns a SolveResult for when HiGHS returns the model status
155 // HighsModelStatus::kModelEmpty. This happens on models that have no
156 // variables, but may still have (potentially infeasible) linear constraints
157 // and an objective offset.
158 //
159 // Assumes that there are no inverted linear constraint bounds.
160 static SolveResultProto ResultForHighsModelStatusModelEmpty(
161 bool is_maximize, double objective_offset,
162 const absl::flat_hash_map<int64_t, IndexAndBound>& lin_con_data);
163
164 InvertedBounds ListInvertedBounds();
165
166 std::unique_ptr<Highs> highs_;
167
168 // Key is the mathopt id, value.index is the variable index in HiGHS.
169 absl::flat_hash_map<int64_t, IndexAndBound> variable_data_;
170
171 // Key is the mathopt id, value.index is the linear constraint index in HiGHS.
172 absl::flat_hash_map<int64_t, IndexAndBound> lin_con_data_;
173};
174
175} // namespace operations_research::math_opt
176
177#endif // OR_TOOLS_MATH_OPT_SOLVERS_HIGHS_SOLVER_H_
static absl::StatusOr< std::unique_ptr< SolverInterface > > New(const ModelProto &model, const InitArgs &init_args)
absl::StatusOr< SolveResultProto > Solve(const SolveParametersProto &parameters, const ModelSolveParametersProto &model_parameters, MessageCallback message_cb, const CallbackRegistrationProto &callback_registration, Callback cb, const SolveInterrupter *interrupter) override
absl::StatusOr< ComputeInfeasibleSubsystemResultProto > ComputeInfeasibleSubsystem(const SolveParametersProto &parameters, MessageCallback message_cb, const SolveInterrupter *interrupter) override
absl::StatusOr< bool > Update(const ModelUpdateProto &model_update) override
std::function< void(const std::vector< std::string > &)> MessageCallback
std::function< absl::StatusOr< CallbackResultProto >( const CallbackDataProto &)> Callback
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
StatusBuilder InvalidArgumentErrorBuilder()