Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
highs_proto_solver.cc
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
15
16#include <cassert>
17#include <cmath>
18#include <limits>
19#include <optional>
20#include <string>
21#include <vector>
22
23#include "Highs.h"
24#include "absl/status/status.h"
25#include "absl/status/statusor.h"
26#include "absl/strings/str_cat.h"
27#include "absl/strings/str_join.h"
28#include "absl/strings/str_split.h"
29#include "absl/strings/string_view.h"
30#include "absl/time/clock.h"
31#include "absl/time/time.h"
32#include "absl/types/optional.h"
33#include "google/protobuf/repeated_field.h"
34#include "lp_data/HConst.h"
35#include "lp_data/HighsInfo.h"
36#include "lp_data/HighsStatus.h"
37#include "ortools/base/timer.h"
41#include "util/HighsInt.h"
42
43namespace operations_research {
44
45absl::Status SetSolverSpecificParameters(const std::string& parameters,
46 Highs& highs);
47
48absl::StatusOr<MPSolutionResponse> HighsSolveProto(
50 MPSolutionResponse response;
51 const std::optional<LazyMutableCopy<MPModelProto>> optional_model =
52 GetMPModelOrPopulateResponse(request, &response);
53 if (!optional_model) return response;
54 const MPModelProto& model = **optional_model;
55
56 Highs highs;
57 // Set model name.
58 if (model.has_name() && !model.name().empty()) {
59 const std::string model_name = model.name();
60 highs.passModelName(model_name);
61 }
62
63 if (request->has_solver_specific_parameters()) {
64 const auto parameters_status = SetSolverSpecificParameters(
65 request->solver_specific_parameters(), highs);
66 if (!parameters_status.ok()) {
68 response.set_status_str(parameters_status.message());
69 return response;
70 }
71 }
72
73 if (request->solver_time_limit_seconds() > 0) {
74 HighsStatus status = highs.setOptionValue(
75 "time_limit", request->solver_time_limit_seconds());
76 if (status == HighsStatus::kError) {
78 response.set_status_str("time_limit");
79 return response;
80 }
81 }
82
83 const int variable_size = model.variable_size();
84 bool has_integer_variables = false;
85 {
86 std::vector<double> obj_coeffs(variable_size, 0);
87 std::vector<double> lb(variable_size);
88 std::vector<double> ub(variable_size);
89 std::vector<HighsVarType> integrality(variable_size);
90 for (int v = 0; v < variable_size; ++v) {
91 const MPVariableProto& variable = model.variable(v);
92 obj_coeffs[v] = variable.objective_coefficient();
93 lb[v] = variable.lower_bound();
94 ub[v] = variable.upper_bound();
95 integrality[v] =
96 variable.is_integer() &&
97 request->solver_type() ==
99 ? HighsVarType::kInteger
100 : HighsVarType::kContinuous;
101 if (integrality[v] == HighsVarType::kInteger) {
102 has_integer_variables = true;
103 }
104 }
105
106 highs.addVars(variable_size, lb.data(), ub.data());
107
108 // Mark integrality.
109 if (has_integer_variables) {
110 for (int v = 0; v < variable_size; ++v) {
111 highs.changeColIntegrality(v, integrality[v]);
112 }
113 }
114
115 // Objective coefficients.
116 for (int column = 0; column < variable_size; column++) {
117 highs.changeColCost(column, obj_coeffs[column]);
118 }
119
120 // Variable names.
121 for (int v = 0; v < variable_size; ++v) {
122 const MPVariableProto& variable = model.variable(v);
123 std::string varname_str = "";
124 if (!variable.name().empty()) {
125 varname_str = variable.name();
126 highs.passColName(v, varname_str);
127 }
128 }
129
130 // Hints.
131 int num_hints = model.solution_hint().var_index_size();
132 if (num_hints > 0) {
133 std::vector<HighsInt> hint_index(0, num_hints);
134 std::vector<double> hint_value(0, num_hints);
135 for (int i = 0; i < num_hints; ++i) {
136 hint_index[i] = model.solution_hint().var_index(i);
137 hint_value[i] = model.solution_hint().var_value(i);
138 }
139 const int* hint_indices = &hint_index[0];
140 const double* hint_values = &hint_value[0];
141 highs.setSolution((HighsInt)num_hints, hint_indices, hint_values);
142 }
143 }
144
145 {
146 for (int c = 0; c < model.constraint_size(); ++c) {
147 const MPConstraintProto& constraint = model.constraint(c);
148 if (constraint.lower_bound() ==
149 -std::numeric_limits<double>::infinity()) {
150 HighsStatus status =
151 highs.addRow(/*lhs=*/-kHighsInf,
152 /*rhs=*/constraint.upper_bound(),
153 /*numnz=*/constraint.var_index_size(),
154 /*cind=*/constraint.var_index().data(),
155 /*cval=*/constraint.coefficient().data());
156 if (status == HighsStatus::kError) {
158 response.set_status_str("ct addRow");
159 return response;
160 }
161 } else if (constraint.upper_bound() ==
162 std::numeric_limits<double>::infinity()) {
163 HighsStatus status =
164 highs.addRow(/*lhs=*/constraint.lower_bound(),
165 /*rhs=*/kHighsInf,
166 /*numnz=*/constraint.var_index_size(),
167 /*cind=*/constraint.var_index().data(),
168 /*cval=*/constraint.coefficient().data());
169 if (status == HighsStatus::kError) {
171 response.set_status_str("ct addRow");
172 return response;
173 }
174 } else {
175 HighsStatus status =
176 highs.addRow(/*lhs=*/constraint.lower_bound(),
177 /*rhs=*/constraint.upper_bound(),
178 /*numnz=*/constraint.var_index_size(),
179 /*cind=*/constraint.var_index().data(),
180 /*cval=*/constraint.coefficient().data());
181 if (status == HighsStatus::kError) {
183 response.set_status_str("ct addRow");
184 return response;
185 }
186 }
187
188 // Constraint names.
189 std::string constraint_name_str = "";
190 if (!constraint.name().empty()) {
191 constraint_name_str = constraint.name();
192 highs.passRowName(c, constraint_name_str);
193 }
194 }
195
196 if (!model.general_constraint().empty()) {
198 response.set_status_str("general constraints are not supported in Highs");
199 return response;
200 }
201 }
202
203 if (model.maximize()) {
204 const ObjSense pass_sense = ObjSense::kMaximize;
205 highs.changeObjectiveSense(pass_sense);
206 }
207
208 if (model.objective_offset()) {
209 const double offset = model.objective_offset();
210 highs.changeObjectiveOffset(offset);
211 }
212
213 // Logging.
214 if (request->enable_internal_solver_output()) {
215 highs.setOptionValue("log_to_console", true);
216 highs.setOptionValue("output_flag", true);
217 } else {
218 highs.setOptionValue("log_to_console", false);
219 highs.setOptionValue("output_flag", false);
220 }
221
222 const absl::Time time_before = absl::Now();
223 UserTimer user_timer;
224 user_timer.Start();
225 HighsStatus run_status = highs.run();
226 switch (run_status) {
227 case HighsStatus::kError: {
229 response.set_status_str("Error running HiGHS run()");
230 return response;
231 }
232 case HighsStatus::kWarning: {
233 response.set_status_str("Warning HiGHS run()");
234 break;
235 }
236 case HighsStatus::kOk: {
237 HighsModelStatus model_status = highs.getModelStatus();
238 switch (model_status) {
239 case HighsModelStatus::kOptimal:
241 break;
242 case HighsModelStatus::kUnboundedOrInfeasible:
243 response.set_status_str(
244 "The model may actually be unbounded: HiGHS returned "
245 "kUnboundedOrInfeasible");
247 break;
248 case HighsModelStatus::kInfeasible:
250 break;
251 case HighsModelStatus::kUnbounded:
253 break;
254 default: {
255 // TODO(user): report feasible status.
256 const HighsInfo& info = highs.getInfo();
257 if (info.primal_solution_status == kSolutionStatusFeasible)
259 break;
260 }
261 }
262 }
263 }
264
265 const absl::Duration solving_duration = absl::Now() - time_before;
266 user_timer.Stop();
268 absl::ToDoubleSeconds(solving_duration));
270 absl::ToDoubleSeconds(user_timer.GetDuration()));
271
272 if (response.status() == MPSOLVER_OPTIMAL) {
273 double objective_value = highs.getObjectiveValue();
274 response.set_objective_value(objective_value);
275 response.set_best_objective_bound(objective_value);
276
277 response.mutable_variable_value()->Resize(variable_size, 0);
278 for (int column = 0; column < variable_size; column++) {
279 response.mutable_variable_value()->mutable_data()[column] =
280 highs.getSolution().col_value[column];
281 }
282
283 if (has_integer_variables) {
284 for (int v = 0; v < variable_size; ++v) {
285 if (model.variable(v).is_integer()) {
286 response.set_variable_value(v,
287 std::round(response.variable_value(v)));
288 }
289 }
290 }
291
292 if (!has_integer_variables && model.general_constraint_size() == 0) {
293 response.mutable_dual_value()->Resize(model.constraint_size(), 0);
294 for (int row = 0; row < model.constraint_size(); row++) {
295 response.set_dual_value(row, highs.getSolution().row_value[row]);
296 }
297 }
298 }
299
300 return response;
301}
302
303absl::Status SetSolverSpecificParameters(const std::string& parameters,
304 Highs& highs) {
305 if (parameters.empty()) return absl::OkStatus();
306 std::vector<std::string> error_messages;
307 for (absl::string_view line : absl::StrSplit(parameters, '\n')) {
308 // Comment tokens end at the next new-line, or the end of the string.
309 // The first character must be '#'
310 if (line[0] == '#') continue;
311 for (absl::string_view token :
312 absl::StrSplit(line, ',', absl::SkipWhitespace())) {
313 if (token.empty()) continue;
314 std::vector<std::string> key_value =
315 absl::StrSplit(token, absl::ByAnyChar(" ="), absl::SkipWhitespace());
316 // If one parameter fails, we keep processing the list of parameters.
317 if (key_value.size() != 2) {
318 const std::string current_message =
319 absl::StrCat("Cannot parse parameter '", token,
320 "'. Expected format is 'ParameterName value' or "
321 "'ParameterName=value'");
322 error_messages.push_back(current_message);
323 continue;
324 }
325 HighsStatus status = highs.setOptionValue(key_value[0], key_value[1]);
326 if (status == HighsStatus::kError) {
327 const std::string current_message =
328 absl::StrCat("Error setting parameter '", key_value[0],
329 "' to value '", key_value[1], "': ");
330 error_messages.push_back(current_message);
331 continue;
332 }
333 }
334 }
335
336 if (error_messages.empty()) return absl::OkStatus();
337 return absl::InvalidArgumentError(absl::StrJoin(error_messages, "\n"));
338}
339
340} // namespace operations_research
absl::Duration GetDuration() const
Definition timer.h:47
void Start()
When Start() is called multiple times, only the most recent is used.
Definition timer.h:30
void Stop()
Definition timer.h:38
const ::std::string & name() const
int var_index_size() const
repeated int32 var_index = 6 [packed = true];
const ::operations_research::MPVariableProto & variable(int index) const
int variable_size() const
repeated .operations_research.MPVariableProto variable = 3;
const ::operations_research::MPGeneralConstraintProto & general_constraint(int index) const
const ::operations_research::MPConstraintProto & constraint(int index) const
int general_constraint_size() const
repeated .operations_research.MPGeneralConstraintProto general_constraint = 7;
bool has_name() const
optional string name = 5 [default = ""];
const ::operations_research::PartialVariableAssignment & solution_hint() const
const ::std::string & name() const
int constraint_size() const
repeated .operations_research.MPConstraintProto constraint = 4;
static constexpr SolverType HIGHS_MIXED_INTEGER_PROGRAMMING
void set_variable_value(int index, double value)
::operations_research::MPSolveInfo *PROTOBUF_NONNULL mutable_solve_info()
::operations_research::MPSolverResponseStatus status() const
void set_dual_value(int index, double value)
void set_status_str(Arg_ &&arg, Args_... args)
::google::protobuf::RepeatedField< double > *PROTOBUF_NONNULL mutable_variable_value()
::google::protobuf::RepeatedField< double > *PROTOBUF_NONNULL mutable_dual_value()
void set_status(::operations_research::MPSolverResponseStatus value)
void set_solve_wall_time_seconds(double value)
void set_solve_user_time_seconds(double value)
const ::std::string & name() const
int var_index_size() const
repeated int32 var_index = 1 [packed = true];
In SWIG mode, we don't want anything besides these top-level includes.
std::optional< LazyMutableCopy< MPModelProto > > GetMPModelOrPopulateResponse(LazyMutableCopy< MPModelRequest > &request, MPSolutionResponse *response)
absl::StatusOr< MPSolutionResponse > HighsSolveProto(LazyMutableCopy< MPModelRequest > request)
Solve the input MIP model with the HIGHS solver.
absl::Status SetSolverSpecificParameters(absl::string_view parameters, GRBenv *gurobi)
WallTimer UserTimer
Definition timer.h:65