Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
solve.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
14// Command line interface to the MPSolver class.
15// See linear_solver.h and kUsageStr below.
16//
17// Examples.
18//
19// 1. To run SCIP for 90 seconds, dumping available information use:
20//
21// solve --solver=scip \
22// --time_limit=90s \
23// --stderrthreshold=0 \
24// --linear_solver_enable_verbose_output \
25// --input=/tmp/foo.mps \
26// --dump_model=/tmp/foo.model \
27// --dump_request=/tmp/foo.request \
28// --dump_response=/tmp/foo.response \
29// >/tmp/foo.out 2>/tmp/foo.err
30//
31// 2. To run CP_SAT for 10 minutes with 8 workers, you can use
32// CP-SAT parameters:
33//
34// solve --solver=sat \
35// --params="max_time_in_seconds:600, num_search_workers:8"
36// --stderrthreshold=0 \
37// --input=/tmp/foo.mps \
38// 2>/tmp/foo.err
39//
40// or use the solve binary flags:
41//
42// solve --solver=sat \
43// --time_limit=10m \
44// --num_threads=8 \
45// --stderrthreshold=0 \
46// --input=/tmp/foo.mps \
47// --dump_model=/tmp/foo.model \
48// --dump_request=/tmp/foo.request \
49// --dump_response=/tmp/foo.response \
50// 2>/tmp/foo.err
51
52#include <cstdio>
53#include <iostream>
54#include <optional>
55#include <string>
56#include <utility>
57
58#include "absl/flags/declare.h"
59#include "absl/flags/flag.h"
60#include "absl/status/status.h"
61#include "absl/status/statusor.h"
62#include "absl/strings/match.h"
63#include "absl/strings/str_cat.h"
64#include "absl/strings/str_format.h"
65#include "absl/time/time.h"
66#include "ortools/base/file.h"
72#include "ortools/linear_solver/linear_solver.pb.h"
77#include "ortools/sat/cp_model.pb.h"
80#include "ortools/util/sigint.h"
81
82ABSL_FLAG(std::string, input, "", "REQUIRED: Input file name.");
83ABSL_FLAG(std::string, sol_hint, "",
84 "Input file name with solution in .sol format.");
85ABSL_FLAG(std::optional<std::string>, solver, std::nullopt,
86 "The solver to use: bop, cbc, clp, glop, glpk_lp, glpk_mip, "
87 "gurobi_lp, gurobi_mip, pdlp, scip, knapsack, sat. If unspecified "
88 "either use MPModelRequest.solver_type if the --input is an "
89 "MPModelRequest and the field is set or use glop.");
90ABSL_FLAG(int, num_threads, 1,
91 "Number of threads to use by the underlying solver.");
92ABSL_FLAG(std::string, params_file, "",
93 "Solver specific parameters file. "
94 "If this flag is set, the --params flag is ignored.");
95ABSL_FLAG(std::string, params, "", "Solver specific parameters");
96ABSL_FLAG(absl::Duration, time_limit, absl::InfiniteDuration(),
97 "It specifies a limit on the solving time. The duration must be must "
98 "be positive. It default to an infinite duration meaning that no "
99 "time limit will be imposed.");
100ABSL_FLAG(std::string, output_csv, "",
101 "If non-empty, write the returned solution in csv format with "
102 "each line formed by a variable name and its value.");
103
104ABSL_FLAG(std::string, dump_format, "text",
105 "Format in which to dump protos (if flags --dump_model, "
106 "--dump_request, or --dump_response are used). Possible values: "
107 "'text', 'binary', 'json' which correspond to text proto format "
108 "binary proto format, and json. If 'binary' or 'json' are used, "
109 "we append '.bin' and '.json' to file names.");
110ABSL_FLAG(bool, dump_gzip, false,
111 "Whether to gzip dumped protos. Appends .gz to their name.");
112ABSL_FLAG(std::string, dump_model, "",
113 "If non-empty, dumps MPModelProto there.");
114ABSL_FLAG(std::string, dump_request, "",
115 "If non-empty, dumps MPModelRequest there.");
116ABSL_FLAG(std::string, dump_response, "",
117 "If non-empty, dumps MPSolutionResponse there.");
118ABSL_FLAG(std::string, sol_file, "",
119 "If non-empty, output the best solution in Miplib .sol format.");
120ABSL_FLAG(std::string, dump_mps, "",
121 "If non-empty, dumps the model in mps format there.");
122
123static const char kUsageStr[] =
124 "Run MPSolver on the given input file. Many formats are supported: \n"
125 " - a .mps or .mps.gz file,\n"
126 " - an MPModelProto (binary or text, possibly gzipped),\n"
127 " - an MPModelRequest (binary or text, possibly gzipped).";
128
129namespace operations_research {
130namespace {
131
132MPModelRequest ReadMipModel(const std::string& input) {
133 MPModelRequest request_proto;
134 MPModelProto model_proto;
135 if (absl::EndsWith(input, ".lp")) {
136 std::string data;
137 CHECK_OK(file::GetContents(input, &data, file::Defaults()));
138 absl::StatusOr<MPModelProto> result = ModelProtoFromLpFormat(data);
139 CHECK_OK(result);
140 model_proto = std::move(result).value();
141 } else if (absl::EndsWith(input, ".mps") ||
142 absl::EndsWith(input, ".mps.gz")) {
143 QCHECK_OK(glop::MPSReader().ParseFile(input, &model_proto))
144 << "Error while parsing the mps file '" << input << "'.";
145 } else {
146 ReadFileToProto(input, &model_proto).IgnoreError();
147 ReadFileToProto(input, &request_proto).IgnoreError();
148 }
149 // If the input is a proto in binary format, both ReadFileToProto could
150 // return true. Instead use the actual number of variables found to test the
151 // correct format of the input.
152 const bool is_model_proto = model_proto.variable_size() > 0;
153 const bool is_request_proto =
154 request_proto.model().variable_size() > 0 ||
155 !request_proto.model_delta().baseline_model_file_path().empty();
156 if (!is_model_proto && !is_request_proto) {
157 LOG(FATAL) << "Failed to parse '" << input
158 << "' as an MPModelProto or an MPModelRequest.";
159 } else {
160 CHECK(!(is_model_proto && is_request_proto));
161 }
162 if (is_request_proto) {
163 LOG(INFO) << "Read input proto as an MPModelRequest.";
164 } else {
165 LOG(INFO) << "Read input proto as an MPModelProto.";
166 model_proto.Swap(request_proto.mutable_model());
167 }
168 return request_proto;
169}
170
171MPSolutionResponse LocalSolve(const MPModelRequest& request_proto) {
172 // TODO(or-core-team): Why doesn't this use MPSolver::SolveWithProto() ?
173
174 // Create the solver, we use the name of the model as the solver name.
175 MPSolver solver(request_proto.model().name(),
177 request_proto.solver_type()));
178 const absl::Status set_num_threads_status =
179 solver.SetNumThreads(absl::GetFlag(FLAGS_num_threads));
180 if (set_num_threads_status.ok()) {
181 LOG(INFO) << "Set number of threads to " << absl::GetFlag(FLAGS_num_threads)
182 << ".";
183 } else if (absl::GetFlag(FLAGS_num_threads) != 1) {
184 LOG(ERROR) << "Failed to set number of threads due to: "
185 << set_num_threads_status.message() << ". Using 1 as default.";
186 }
187 solver.EnableOutput();
188
189 if (request_proto.has_solver_specific_parameters()) {
190 CHECK(solver.SetSolverSpecificParametersAsString(
191 request_proto.solver_specific_parameters()))
192 << "Wrong solver_specific_parameters (bad --params or --params_file ?)";
193 }
194
195 MPSolutionResponse response;
196
197 // Load the model proto into the solver.
198 {
199 std::string error_message;
200 const MPSolverResponseStatus status =
201 solver.LoadModelFromProtoWithUniqueNamesOrDie(request_proto.model(),
202 &error_message);
203 // Note, the underlying MPSolver treats time limit equal to 0 as no limit.
204 if (status != MPSOLVER_MODEL_IS_VALID) {
205 // HACK(user): For SAT solves, when the model is invalid we directly
206 // exit here.
207 if (request_proto.solver_type() ==
208 MPModelRequest::SAT_INTEGER_PROGRAMMING) {
209 sat::CpSolverResponse sat_response;
210 sat_response.set_status(sat::CpSolverStatus::MODEL_INVALID);
211 LOG(INFO) << sat::CpSolverResponseStats(sat_response);
212 exit(1);
213 }
214 response.set_status(status);
215 response.set_status_str(error_message);
216 return response;
217 }
218 }
219 if (request_proto.has_solver_time_limit_seconds()) {
220 solver.SetTimeLimit(
221 absl::Seconds(request_proto.solver_time_limit_seconds()));
222 }
223
224 // Register a signal handler to interrupt the solve when the user presses ^C.
225 // Note that we ignore all previously registered handler here. If SCIP is
226 // used, this handler will be overridden by the one of SCIP that does the same
227 // thing.
228 SigintHandler handler;
229 handler.Register([&solver] { solver.InterruptSolve(); });
230
231 // Solve.
232 const MPSolver::ResultStatus status = solver.Solve();
233
234 // If --verify_solution is true, we already verified it. If not, we add
235 // a verification step here.
236 if ((status == MPSolver::OPTIMAL || status == MPSolver::FEASIBLE) &&
237 !absl::GetFlag(FLAGS_verify_solution)) {
238 const bool verified =
239 solver.VerifySolution(/*tolerance=*/MPSolverParameters().GetDoubleParam(
241 absl::GetFlag(FLAGS_log_verification_errors));
242 LOG(INFO) << "The solution "
243 << (verified ? "was verified." : "didn't pass verification.");
244 }
245
246 // If the solver is a MIP, print the number of nodes.
247 // TODO(user): add the number of nodes to the response, and move this code
248 // to the main Run().
249 if (SolverTypeIsMip(request_proto.solver_type())) {
250 absl::PrintF("%-12s: %d\n", "Nodes", solver.nodes());
251 }
252
253 // Fill and return the response proto.
254 solver.FillSolutionResponseProto(&response);
255 return response;
256}
257
258void Run() {
259 QCHECK(!absl::GetFlag(FLAGS_input).empty()) << "--input is required";
260 QCHECK_GE(absl::GetFlag(FLAGS_time_limit), absl::ZeroDuration())
261 << "--time_limit must be given a positive duration";
262
263 // Parses --solver if set.
264 std::optional<MPSolver::OptimizationProblemType> type;
265 if (const std::optional<std::string> type_flag = absl::GetFlag(FLAGS_solver);
266 type_flag.has_value()) {
268 QCHECK(MPSolver::ParseSolverType(type_flag.value(), &decoded_type))
269 << "Unsupported --solver: " << type_flag.value();
270 type = decoded_type;
271 }
272
273 MPModelRequest request_proto = ReadMipModel(absl::GetFlag(FLAGS_input));
274
275 if (!absl::GetFlag(FLAGS_sol_hint).empty()) {
276 const auto read_sol =
277 ParseSolFile(absl::GetFlag(FLAGS_sol_hint), request_proto.model());
278 CHECK_OK(read_sol.status());
279 const MPSolutionResponse& sol = read_sol.value();
280 if (request_proto.model().has_solution_hint()) {
281 LOG(WARNING) << "Overwriting solution hint found in the request with "
282 << "solution from " << absl::GetFlag(FLAGS_sol_hint);
283 }
284 request_proto.mutable_model()->clear_solution_hint();
285 for (int i = 0; i < sol.variable_value_size(); ++i) {
286 request_proto.mutable_model()->mutable_solution_hint()->add_var_index(i);
287 request_proto.mutable_model()->mutable_solution_hint()->add_var_value(
288 sol.variable_value(i));
289 }
290 }
291
292 printf("%-12s: '%s'\n", "File", absl::GetFlag(FLAGS_input).c_str());
293
294 // Detect format to dump protos.
296 if (absl::GetFlag(FLAGS_dump_format) == "text") {
297 write_format = ProtoWriteFormat::kProtoText;
298 } else if (absl::GetFlag(FLAGS_dump_format) == "binary") {
299 write_format = ProtoWriteFormat::kProtoBinary;
300 } else if (absl::GetFlag(FLAGS_dump_format) == "json") {
301 write_format = ProtoWriteFormat::kJson;
302 } else {
303 LOG(FATAL) << "Unsupported --dump_format: "
304 << absl::GetFlag(FLAGS_dump_format);
305 }
306
307 if (!absl::GetFlag(FLAGS_dump_mps).empty()) {
308 CHECK_OK(WriteModelToMpsFile(absl::GetFlag(FLAGS_dump_mps),
309 request_proto.model()));
310 }
311
312 // Set or override request proto options from the command line flags.
313 if (type.has_value() || !request_proto.has_solver_type()) {
314 request_proto.set_solver_type(static_cast<MPModelRequest::SolverType>(
315 type.value_or(MPSolver::GLOP_LINEAR_PROGRAMMING)));
316 }
317 if (absl::GetFlag(FLAGS_time_limit) != absl::InfiniteDuration()) {
318 LOG(INFO) << "Setting a time limit of " << absl::GetFlag(FLAGS_time_limit);
319 request_proto.set_solver_time_limit_seconds(
320 absl::ToDoubleSeconds(absl::GetFlag(FLAGS_time_limit)));
321 }
322 if (absl::GetFlag(FLAGS_linear_solver_enable_verbose_output)) {
323 request_proto.set_enable_internal_solver_output(true);
324 }
325 if (!absl::GetFlag(FLAGS_params_file).empty()) {
326 CHECK(absl::GetFlag(FLAGS_params).empty())
327 << "--params and --params_file are incompatible";
328 std::string file_contents;
329 CHECK_OK(file::GetContents(absl::GetFlag(FLAGS_params_file), &file_contents,
331 << "Could not read parameters file.";
332 request_proto.set_solver_specific_parameters(file_contents);
333 }
334 if (!absl::GetFlag(FLAGS_params).empty()) {
335 request_proto.set_solver_specific_parameters(absl::GetFlag(FLAGS_params));
336 }
337
338 // If requested, save the model and/or request to file.
339 if (!absl::GetFlag(FLAGS_dump_model).empty()) {
340 CHECK_OK(WriteProtoToFile(absl::GetFlag(FLAGS_dump_model),
341 request_proto.model(), write_format,
342 absl::GetFlag(FLAGS_dump_gzip)));
343 }
344 if (!absl::GetFlag(FLAGS_dump_request).empty()) {
345 CHECK_OK(WriteProtoToFile(absl::GetFlag(FLAGS_dump_request), request_proto,
346 write_format, absl::GetFlag(FLAGS_dump_gzip)));
347 }
348
349 absl::PrintF(
350 "%-12s: %s\n", "Solver",
351 MPModelRequest::SolverType_Name(request_proto.solver_type()).c_str());
352 absl::PrintF("%-12s: %s\n", "Parameters", absl::GetFlag(FLAGS_params));
353 absl::PrintF("%-12s: %d x %d\n", "Dimension",
354 request_proto.model().constraint_size(),
355 request_proto.model().variable_size());
356
357 const absl::Time solve_start_time = absl::Now();
358
359 const MPSolutionResponse response = LocalSolve(request_proto);
360
361 const absl::Duration solving_time = absl::Now() - solve_start_time;
362 const bool has_solution = response.status() == MPSOLVER_OPTIMAL ||
363 response.status() == MPSOLVER_FEASIBLE;
364 absl::PrintF("%-12s: %s\n", "Status",
365 MPSolverResponseStatus_Name(
366 static_cast<MPSolverResponseStatus>(response.status()))
367 .c_str());
368 absl::PrintF("%-12s: %15.15e\n", "Objective",
369 has_solution ? response.objective_value() : 0.0);
370 absl::PrintF("%-12s: %15.15e\n", "BestBound",
371 has_solution ? response.best_objective_bound() : 0.0);
372 absl::PrintF("%-12s: %s\n", "StatusString", response.status_str());
373 absl::PrintF("%-12s: %-6.4g s\n", "Time",
374 absl::ToDoubleSeconds(solving_time));
375
376 // If requested, write the solution, in .sol format (--sol_file), proto
377 // format and/or csv format.
378 if (!absl::GetFlag(FLAGS_sol_file).empty() && has_solution) {
379 std::string sol_string;
380 absl::StrAppend(&sol_string, "=obj= ", response.objective_value(), "\n");
381 for (int i = 0; i < response.variable_value().size(); ++i) {
382 absl::StrAppend(&sol_string, request_proto.model().variable(i).name(),
383 " ", response.variable_value(i), "\n");
384 }
385 LOG(INFO) << "Writing .sol solution to '" << absl::GetFlag(FLAGS_sol_file)
386 << "'.\n";
387 CHECK_OK(file::SetContents(absl::GetFlag(FLAGS_sol_file), sol_string,
388 file::Defaults()));
389 }
390 if (!absl::GetFlag(FLAGS_dump_response).empty() && has_solution) {
391 CHECK_OK(WriteProtoToFile(absl::GetFlag(FLAGS_dump_response), response,
392 write_format, absl::GetFlag(FLAGS_dump_gzip)));
393 }
394 if (!absl::GetFlag(FLAGS_output_csv).empty() && has_solution) {
395 std::string csv_file;
396 for (int i = 0; i < response.variable_value_size(); ++i) {
397 csv_file +=
398 absl::StrFormat("%s,%e\n", request_proto.model().variable(i).name(),
399 response.variable_value(i));
400 }
401 CHECK_OK(file::SetContents(absl::GetFlag(FLAGS_output_csv), csv_file,
402 file::Defaults()));
403 }
404}
405
406} // namespace
407} // namespace operations_research
408
409int main(int argc, char** argv) {
410 InitGoogle(kUsageStr, &argc, &argv, /*remove_flags=*/true);
412}
@ FEASIBLE
feasible, or stopped by limit.
static bool ParseSolverType(absl::string_view solver_id, OptimizationProblemType *type)
static
void InitGoogle(absl::string_view usage, int *argc, char ***argv, bool deprecated)
Definition init_google.h:49
ABSL_FLAG(std::string, sol_hint, "", "Input file name with solution in .sol format.")
int main(int argc, char **argv)
Definition solve.cc:409
time_limit
Definition solve.cc:22
static const char kUsageStr[]
absl::StatusOr< std::string > GetContents(absl::string_view path, Options options)
-— Content API -—
Definition file.cc:348
Options Defaults()
Definition file.h:85
absl::Status SetContents(absl::string_view file_name, absl::string_view contents, Options options)
Definition file.cc:388
std::string CpSolverResponseStats(const CpSolverResponse &response, bool has_objective)
In SWIG mode, we don't want anything besides these top-level includes.
absl::Status WriteModelToMpsFile(absl::string_view filename, const MPModelProto &model, const MPModelExportOptions &options)
absl::StatusOr< glop::DenseRow > ParseSolFile(absl::string_view file_name, const glop::LinearProgram &model)
Parse a solution to model from a file.
Definition sol_reader.cc:35
bool SolverTypeIsMip(MPModelRequest::SolverType solver_type)
There is a homonymous version taking a MPSolver::OptimizationProblemType.
absl::Status WriteProtoToFile(absl::string_view filename, const google::protobuf::Message &proto, ProtoWriteFormat proto_write_format, bool gzipped, bool append_extension_to_file_name)
Definition file_util.cc:143
absl::Status ReadFileToProto(absl::string_view filename, google::protobuf::Message *proto, bool allow_partial)
Definition file_util.cc:54
absl::StatusOr< MPModelProto > ModelProtoFromLpFormat(absl::string_view model)
This calls ParseLp() under the hood. See below.
Definition lp_parser.cc:472
static int input(yyscan_t yyscanner)