Google OR-Tools v9.12
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"
38#include "ortools/linear_solver/linear_solver.pb.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()) {
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()) {
67 response.set_status(MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS);
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) {
77 response.set_status(MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS);
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() ==
98 MPModelRequest::HIGHS_MIXED_INTEGER_PROGRAMMING
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) {
157 response.set_status(MPSOLVER_MODEL_INVALID);
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) {
170 response.set_status(MPSOLVER_MODEL_INVALID);
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) {
182 response.set_status(MPSOLVER_MODEL_INVALID);
183 response.set_status_str("ct addRow");
184 return response;
185 }
186 }
187
188 // Constraint names.
189 for (int c = 0; c < model.constraint_size(); ++c) {
190 const MPConstraintProto& constraint = model.constraint(c);
191 std::string constraint_name_str = "";
192 if (!constraint.name().empty()) {
193 constraint_name_str = constraint.name();
194 highs.passRowName(c, constraint_name_str);
195 }
196 }
197 }
198
199 if (!model.general_constraint().empty()) {
200 response.set_status(MPSOLVER_MODEL_INVALID);
201 response.set_status_str("general constraints are not supported in Highs");
202 return response;
203 }
204 }
205
206 if (model.maximize()) {
207 const ObjSense pass_sense = ObjSense::kMaximize;
208 highs.changeObjectiveSense(pass_sense);
209 }
210
211 if (model.objective_offset()) {
212 const double offset = model.objective_offset();
213 highs.changeObjectiveOffset(offset);
214 }
215
216 // Logging.
217 if (request->enable_internal_solver_output()) {
218 highs.setOptionValue("log_to_console", true);
219 highs.setOptionValue("output_flag", true);
220 } else {
221 highs.setOptionValue("log_to_console", false);
222 highs.setOptionValue("output_flag", false);
223 }
224
225 const absl::Time time_before = absl::Now();
226 UserTimer user_timer;
227 user_timer.Start();
228 HighsStatus run_status = highs.run();
229 switch (run_status) {
230 case HighsStatus::kError: {
231 response.set_status(MPSOLVER_NOT_SOLVED);
232 response.set_status_str("Error running HiGHS run()");
233 return response;
234 }
235 case HighsStatus::kWarning: {
236 response.set_status_str("Warning HiGHS run()");
237 break;
238 }
239 case HighsStatus::kOk: {
240 HighsModelStatus model_status = highs.getModelStatus();
241 switch (model_status) {
242 case HighsModelStatus::kOptimal:
243 response.set_status(MPSOLVER_OPTIMAL);
244 break;
245 case HighsModelStatus::kUnboundedOrInfeasible:
246 response.set_status_str(
247 "The model may actually be unbounded: HiGHS returned "
248 "kUnboundedOrInfeasible");
249 response.set_status(MPSOLVER_INFEASIBLE);
250 break;
251 case HighsModelStatus::kInfeasible:
252 response.set_status(MPSOLVER_INFEASIBLE);
253 break;
254 case HighsModelStatus::kUnbounded:
255 response.set_status(MPSOLVER_UNBOUNDED);
256 break;
257 default: {
258 // TODO(user): report feasible status.
259 const HighsInfo& info = highs.getInfo();
260 if (info.primal_solution_status == kSolutionStatusFeasible)
261 response.set_status(MPSOLVER_FEASIBLE);
262 break;
263 }
264 }
265 }
266 }
267
268 const absl::Duration solving_duration = absl::Now() - time_before;
269 user_timer.Stop();
270 response.mutable_solve_info()->set_solve_wall_time_seconds(
271 absl::ToDoubleSeconds(solving_duration));
272 response.mutable_solve_info()->set_solve_user_time_seconds(
273 absl::ToDoubleSeconds(user_timer.GetDuration()));
274
275 if (response.status() == MPSOLVER_OPTIMAL) {
276 double objective_value = highs.getObjectiveValue();
277 response.set_objective_value(objective_value);
278 response.set_best_objective_bound(objective_value);
279
280 response.mutable_variable_value()->Resize(variable_size, 0);
281 for (int column = 0; column < variable_size; column++) {
282 response.mutable_variable_value()->mutable_data()[column] =
283 highs.getSolution().col_value[column];
284 }
285
286 if (has_integer_variables) {
287 for (int v = 0; v < variable_size; ++v) {
288 if (model.variable(v).is_integer()) {
289 response.set_variable_value(v,
290 std::round(response.variable_value(v)));
291 }
292 }
293 }
294
295 if (!has_integer_variables && model.general_constraint_size() == 0) {
296 response.mutable_dual_value()->Resize(model.constraint_size(), 0);
297 for (int row = 0; row < model.constraint_size(); row++) {
298 response.set_dual_value(row, highs.getSolution().row_value[row]);
299 }
300 }
301 }
302
303 return response;
304}
305
306absl::Status SetSolverSpecificParameters(const std::string& parameters,
307 Highs& highs) {
308 if (parameters.empty()) return absl::OkStatus();
309 std::vector<std::string> error_messages;
310 for (absl::string_view line : absl::StrSplit(parameters, '\n')) {
311 // Comment tokens end at the next new-line, or the end of the string.
312 // The first character must be '#'
313 if (line[0] == '#') continue;
314 for (absl::string_view token :
315 absl::StrSplit(line, ',', absl::SkipWhitespace())) {
316 if (token.empty()) continue;
317 std::vector<std::string> key_value =
318 absl::StrSplit(token, absl::ByAnyChar(" ="), absl::SkipWhitespace());
319 // If one parameter fails, we keep processing the list of parameters.
320 if (key_value.size() != 2) {
321 const std::string current_message =
322 absl::StrCat("Cannot parse parameter '", token,
323 "'. Expected format is 'ParameterName value' or "
324 "'ParameterName=value'");
325 error_messages.push_back(current_message);
326 continue;
327 }
328 HighsStatus status = highs.setOptionValue(key_value[0], key_value[1]);
329 if (status == HighsStatus::kError) {
330 const std::string current_message =
331 absl::StrCat("Error setting parameter '", key_value[0],
332 "' to value '", key_value[1], "': ");
333 error_messages.push_back(current_message);
334 continue;
335 }
336 }
337 }
338
339 if (error_messages.empty()) return absl::OkStatus();
340 return absl::InvalidArgumentError(absl::StrJoin(error_messages, "\n"));
341}
342
343} // namespace operations_research
absl::Duration GetDuration() const
Definition timer.h:49
void Start()
When Start() is called multiple times, only the most recent is used.
Definition timer.h:32
void Stop()
Definition timer.h:40
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:67