Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
parameters.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// IWYU pragma: private, include "ortools/math_opt/cpp/math_opt.h"
15// IWYU pragma: friend "ortools/math_opt/cpp/.*"
16
17#ifndef OR_TOOLS_MATH_OPT_CPP_PARAMETERS_H_
18#define OR_TOOLS_MATH_OPT_CPP_PARAMETERS_H_
19
20#include <cstdint>
21#include <optional>
22#include <string>
23
24#include "absl/status/statusor.h"
25#include "absl/strings/string_view.h"
26#include "absl/time/time.h"
28#include "ortools/glop/parameters.pb.h" // IWYU pragma: export
29#include "ortools/gscip/gscip.pb.h" // IWYU pragma: export
30#include "ortools/math_opt/cpp/enums.h" // IWYU pragma: export
31#include "ortools/math_opt/parameters.pb.h"
32#include "ortools/math_opt/solvers/gurobi.pb.h" // IWYU pragma: export
33#include "ortools/math_opt/solvers/highs.pb.h" // IWYU pragma: export
34#include "ortools/pdlp/solvers.pb.h" // IWYU pragma: export
35#include "ortools/sat/sat_parameters.pb.h" // IWYU pragma: export
36
37namespace operations_research {
38namespace math_opt {
39
40// The solvers supported by MathOpt.
41enum class SolverType {
42 // Solving Constraint Integer Programs (SCIP) solver (third party).
43 //
44 // Supports LP, MIP, and nonconvex integer quadratic problems. No dual data
45 // for LPs is returned though. Prefer GLOP for LPs.
46 kGscip = SOLVER_TYPE_GSCIP,
47
48 // Gurobi solver (third party).
49 //
50 // Supports LP, MIP, and nonconvex integer quadratic problems. Generally the
51 // fastest option, but has special licensing.
52 kGurobi = SOLVER_TYPE_GUROBI,
53
54 // Google's Glop solver.
55 //
56 // Supports LP with primal and dual simplex methods.
57 kGlop = SOLVER_TYPE_GLOP,
58
59 // Google's CP-SAT solver.
60 //
61 // Supports problems where all variables are integer and bounded (or implied
62 // to be after presolve). Experimental support to rescale and discretize
63 // problems with continuous variables.
64 kCpSat = SOLVER_TYPE_CP_SAT,
65
66 // Google's PDLP solver.
67 //
68 // Supports LP and convex diagonal quadratic objectives. Uses first order
69 // methods rather than simplex. Can solve very large problems.
70 kPdlp = SOLVER_TYPE_PDLP,
71
72 // GNU Linear Programming Kit (GLPK) (third party).
73 //
74 // Supports MIP and LP.
75 //
76 // Thread-safety: GLPK use thread-local storage for memory allocations. As a
77 // consequence when using IncrementalSolver, the user must make sure that
78 // instances are destroyed on the same thread as they are created or GLPK will
79 // crash. It seems OK to call IncrementalSolver::Solve() from another thread
80 // than the one used to create the Solver but it is not documented by GLPK and
81 // should be avoided. Of course these limitations do not apply to the Solve()
82 // function that recreates a new GLPK problem in the calling thread and
83 // destroys before returning.
84 //
85 // When solving a LP with the presolver, a solution (and the unbound rays) are
86 // only returned if an optimal solution has been found. Else nothing is
87 // returned. See glpk-5.0/doc/glpk.pdf page #40 available from glpk-5.0.tar.gz
88 // for details.
89 kGlpk = SOLVER_TYPE_GLPK,
90
91 // The Embedded Conic Solver (ECOS).
92 //
93 // Supports LP and SOCP problems. Uses interior point methods (barrier).
94 kEcos = SOLVER_TYPE_ECOS,
95
96 // The Splitting Conic Solver (SCS) (third party).
97 //
98 // Supports LP and SOCP problems. Uses a first-order method.
99 kScs = SOLVER_TYPE_SCS,
100
101 // The HiGHS Solver (third party).
102 //
103 // Supports LP and MIP problems (convex QPs are unimplemented).
104 kHighs = SOLVER_TYPE_HIGHS,
105
106 // MathOpt's reference implementation of a MIP solver.
107 //
108 // Slow/not recommended for production. Not an LP solver (no dual information
109 // returned).
110 kSantorini = SOLVER_TYPE_SANTORINI,
111
112 // Fico XPRESS solver (third party).
113 //
114 // Supports LP, MIP, and nonconvex integer quadratic problems.
115 // A fast option, but has special licensing.
116 kXpress = SOLVER_TYPE_XPRESS,
117};
118
119MATH_OPT_DEFINE_ENUM(SolverType, SOLVER_TYPE_UNSPECIFIED);
120
121// Parses a flag of type SolverType.
122//
123// The expected values are the one returned by EnumToString().
124bool AbslParseFlag(absl::string_view text, SolverType* value,
125 std::string* error);
126
127// Unparses a flag of type SolverType.
128//
129// The returned values are the same as EnumToString().
130std::string AbslUnparseFlag(SolverType value);
131
132// Selects an algorithm for solving linear programs.
133enum class LPAlgorithm {
134 // The (primal) simplex method. Typically can provide primal and dual
135 // solutions, primal/dual rays on primal/dual unbounded problems, and a basis.
136 kPrimalSimplex = LP_ALGORITHM_PRIMAL_SIMPLEX,
137
138 // The dual simplex method. Typically can provide primal and dual
139 // solutions, primal/dual rays on primal/dual unbounded problems, and a basis.
140 kDualSimplex = LP_ALGORITHM_DUAL_SIMPLEX,
141
142 // The barrier method, also commonly called an interior point method (IPM).
143 // Can typically give both primal and dual solutions. Some implementations can
144 // also produce rays on unbounded/infeasible problems. A basis is not given
145 // unless the underlying solver does "crossover" and finishes with simplex.
146 kBarrier = LP_ALGORITHM_BARRIER,
147
148 // An algorithm based around a first-order method. These will typically
149 // produce both primal and dual solutions, and potentially also certificates
150 // of primal and/or dual infeasibility. First-order methods typically will
151 // provide solutions with lower accuracy, so users should take care to set
152 // solution quality parameters (e.g., tolerances) and to validate solutions.
153 kFirstOrder = LP_ALGORITHM_FIRST_ORDER,
154};
155
156MATH_OPT_DEFINE_ENUM(LPAlgorithm, LP_ALGORITHM_UNSPECIFIED);
157
158// Parses a flag of type LPAlgorithm.
159//
160// The expected values are the one returned by EnumToString().
161bool AbslParseFlag(absl::string_view text, LPAlgorithm* value,
162 std::string* error);
163
164// Unparses a flag of type LPAlgorithm.
165//
166// The returned values are the same as EnumToString().
167std::string AbslUnparseFlag(LPAlgorithm value);
168
169// Effort level applied to an optional task while solving (see SolveParameters
170// for use).
171//
172// Typically used as a std::optional<Emphasis>. It's used to configure a solver
173// feature as follows:
174// * If a solver doesn't support the feature, only nullopt will always be
175// valid, any other setting will give an invalid argument error (some solvers
176// may also accept kOff).
177// * If the solver supports the feature:
178// - When unset, the underlying default is used.
179// - When the feature cannot be turned off, kOff will return an error.
180// - If the feature is enabled by default, the solver default is typically
181// mapped to kMedium.
182// - If the feature is supported, kLow, kMedium, kHigh, and kVeryHigh will
183// never give an error, and will map onto their best match.
184enum class Emphasis {
185 kOff = EMPHASIS_OFF,
186 kLow = EMPHASIS_LOW,
187 kMedium = EMPHASIS_MEDIUM,
188 kHigh = EMPHASIS_HIGH,
189 kVeryHigh = EMPHASIS_VERY_HIGH
190};
191
192MATH_OPT_DEFINE_ENUM(Emphasis, EMPHASIS_UNSPECIFIED);
193
194// Parses a flag of type Emphasis.
195//
196// The expected values are the one returned by EnumToString().
197bool AbslParseFlag(absl::string_view text, Emphasis* value, std::string* error);
198
199// Unparses a flag of type Emphasis.
200//
201// The returned values are the same as EnumToString().
202std::string AbslUnparseFlag(Emphasis value);
203
204// Gurobi specific parameters for solving. See
205// https://www.gurobi.com/documentation/9.1/refman/parameters.html
206// for a list of possible parameters.
207//
208// Example use:
209// GurobiParameters gurobi;
210// gurobi.param_values["BarIterLimit"] = "10";
211//
212// With Gurobi, the order that parameters are applied can have an impact in rare
213// situations. Parameters are applied in the following order:
214// * LogToConsole is set from SolveParameters.enable_output.
215// * Any common parameters not overwritten by GurobiParameters.
216// * param_values in iteration order (insertion order).
217// We set LogToConsole first because setting other parameters can generate
218// output.
220 // Parameter name-value pairs to set in insertion order.
222
223 GurobiParametersProto Proto() const;
224 static GurobiParameters FromProto(const GurobiParametersProto& proto);
225
226 bool empty() const { return param_values.empty(); }
227};
228
229// GLPK specific parameters for solving.
230//
231// Fields are optional to enable capturing user intention; if the user
232// explicitly sets a value, then no generic solve parameters will overwrite this
233// parameter. User specified solver specific parameters have priority over
234// generic parameters.
236 // Compute the primal or dual unbound ray when the variable (structural or
237 // auxiliary) causing the unboundness is identified (see glp_get_unbnd_ray()).
238 //
239 // The unset value is equivalent to false.
240 //
241 // Rays are only available when solving linear programs, they are not
242 // available for MIPs. On top of that they are only available when using a
243 // simplex algorithm with the presolve disabled.
244 //
245 // A primal ray can only be built if the chosen LP algorithm is
246 // LPAlgorithm::kPrimalSimplex. Same for a dual ray and
247 // LPAlgorithm::kDualSimplex.
248 //
249 // The computation involves the basis factorization to be available which may
250 // lead to extra computations/errors.
251 std::optional<bool> compute_unbound_rays_if_possible = std::nullopt;
252
253 GlpkParametersProto Proto() const;
254 static GlpkParameters FromProto(const GlpkParametersProto& proto);
255};
256
257// Parameters to control a single solve.
258//
259// Contains both parameters common to all solvers, e.g. time_limit, and
260// parameters for a specific solver, e.g. gscip. If a value is set in both
261// common and solver specific fields, the solver specific setting is used.
262//
263// The common parameters that are optional and unset indicate that the solver
264// default is used.
265//
266// Solver specific parameters for solvers other than the one in use are ignored.
267//
268// Parameters that depends on the model (e.g. branching priority is set for
269// each variable) are passed in ModelSolveParametersProto.
271 // Enables printing the solver implementation traces. These traces are sent
272 // to the standard output stream.
273 //
274 // Note that if the user registers a message callback, then this parameter
275 // value is ignored and no traces are printed.
276 bool enable_output = false;
277
278 // Maximum time a solver should spend on the problem.
279 //
280 // This value is not a hard limit, solve time may slightly exceed this value.
281 // Always passed to the underlying solver, the solver default is not used.
282 absl::Duration time_limit = absl::InfiniteDuration();
283
284 // Limit on the iterations of the underlying algorithm (e.g. simplex pivots).
285 // The specific behavior is dependent on the solver and algorithm used, but
286 // often can give a deterministic solve limit (further configuration may be
287 // needed, e.g. one thread).
288 //
289 // Typically supported by LP, QP, and MIP solvers, but for MIP solvers see
290 // also node_limit.
291 std::optional<int64_t> iteration_limit;
292
293 // Limit on the number of subproblems solved in enumerative search (e.g.
294 // branch and bound). For many solvers this can be used to deterministically
295 // limit computation (further configuration may be needed, e.g. one thread).
296 //
297 // Typically for MIP solvers, see also iteration_limit.
298 std::optional<int64_t> node_limit;
299
300 // The solver stops early if it can prove there are no primal solutions at
301 // least as good as cutoff.
302 //
303 // On an early stop, the solver returns termination reason kNoSolutionFound
304 // and with limit kCutoff and is not required to give any extra solution
305 // information. Has no effect on the return value if there is no early stop.
306 //
307 // It is recommended that you use a tolerance if you want solutions with
308 // objective exactly equal to cutoff to be returned.
309 //
310 // See the user guide for more details and a comparison with best_bound_limit.
311 std::optional<double> cutoff_limit;
312
313 // The solver stops early as soon as it finds a solution at least this good,
314 // with termination reason kFeasible and limit kObjective.
315 std::optional<double> objective_limit;
316
317 // The solver stops early as soon as it proves the best bound is at least this
318 // good, with termination reason kFeasible or kNoSolutionFound and limit
319 // kObjective.
320 //
321 // See the user guide for a comparison with cutoff_limit.
322 std::optional<double> best_bound_limit;
323
324 // The solver stops early after finding this many feasible solutions, with
325 // termination reason kFeasible and limit kSolution. Must be greater than
326 // zero if set. It is often used to get the solver to stop on the first
327 // feasible solution found. Note that there is no guarantee on the objective
328 // value for any of the returned solutions.
329 //
330 // Solvers will typically not return more solutions than the solution limit,
331 // but this is not enforced by MathOpt, see also b/214041169.
332 //
333 // Currently supported for Gurobi and SCIP, and for CP-SAT only with value 1.
334 std::optional<int32_t> solution_limit;
335
336 // If unset, use the solver default. If set, it must be >= 1.
337 std::optional<int32_t> threads;
338
339 // Seed for the pseudo-random number generator in the underlying
340 // solver. Note that all solvers use pseudo-random numbers to select things
341 // such as perturbation in the LP algorithm, for tie-break-up rules, and for
342 // heuristic fixings. Varying this can have a noticeable impact on solver
343 // behavior.
344 //
345 // Although all solvers have a concept of seeds, note that valid values
346 // depend on the actual solver.
347 // - Gurobi: [0:GRB_MAXINT] (which as of Gurobi 9.0 is 2x10^9).
348 // - GSCIP: [0:2147483647] (which is MAX_INT or kint32max or 2^31-1).
349 // - GLOP: [0:2147483647] (same as above)
350 // In all cases, the solver will receive a value equal to:
351 // MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, random_seed)).
352 std::optional<int32_t> random_seed;
353
354 // An absolute optimality tolerance (primarily) for MIP solvers.
355 //
356 // The absolute GAP is the absolute value of the difference between:
357 // * the objective value of the best feasible solution found,
358 // * the dual bound produced by the search.
359 // The solver can stop once the absolute GAP is at most absolute_gap_tolerance
360 // (when set), and return TerminationReason::kOptimal.
361 //
362 // Must be >= 0 if set.
363 //
364 // See also relative_gap_tolerance.
365 std::optional<double> absolute_gap_tolerance;
366
367 // A relative optimality tolerance (primarily) for MIP solvers.
368 //
369 // The relative GAP is a normalized version of the absolute GAP (defined on
370 // absolute_gap_tolerance), where the normalization is solver-dependent, e.g.
371 // the absolute GAP divided by the objective value of the best feasible
372 // solution found.
373 //
374 // The solver can stop once the relative GAP is at most relative_gap_tolerance
375 // (when set), and return TerminationReason::kOptimal.
376 //
377 // Must be >= 0 if set.
378 //
379 // See also absolute_gap_tolerance.
380 std::optional<double> relative_gap_tolerance;
381
382 // Maintain up to `solution_pool_size` solutions while searching. The solution
383 // pool generally has two functions:
384 // (1) For solvers that can return more than one solution, this limits how
385 // many solutions will be returned.
386 // (2) Some solvers may run heuristics using solutions from the solution
387 // pool, so changing this value may affect the algorithm's path.
388 // To force the solver to fill the solution pool, e.g. with the n best
389 // solutions, requires further, solver specific configuration.
390 std::optional<int32_t> solution_pool_size;
391
392 // The algorithm for solving a linear program. If nullopt, use the solver
393 // default algorithm.
394 //
395 // For problems that are not linear programs but where linear programming is
396 // a subroutine, solvers may use this value. E.g. MIP solvers will typically
397 // use this for the root LP solve only (and use dual simplex otherwise).
398 std::optional<LPAlgorithm> lp_algorithm;
399
400 // Effort on simplifying the problem before starting the main algorithm, or
401 // the solver default effort level if unset.
402 std::optional<Emphasis> presolve;
403
404 // Effort on getting a stronger LP relaxation (MIP only) or the solver default
405 // effort level if unset.
406 //
407 // NOTE: disabling cuts may prevent callbacks from having a chance to add cuts
408 // at MIP_NODE, this behavior is solver specific.
409 std::optional<Emphasis> cuts;
410
411 // Effort in finding feasible solutions beyond those encountered in the
412 // complete search procedure (MIP only), or the solver default effort level if
413 // unset.
414 std::optional<Emphasis> heuristics;
415
416 // Effort in rescaling the problem to improve numerical stability, or the
417 // solver default effort level if unset.
418 std::optional<Emphasis> scaling;
419
420 GScipParameters gscip;
422 glop::GlopParameters glop;
423 sat::SatParameters cp_sat;
424 pdlp::PrimalDualHybridGradientParams pdlp;
425
427 HighsOptionsProto highs;
428
429 SolveParametersProto Proto() const;
430 static absl::StatusOr<SolveParameters> FromProto(
431 const SolveParametersProto& proto);
432};
433
434bool AbslParseFlag(absl::string_view text, SolveParameters* solve_parameters,
435 std::string* error);
436
437std::string AbslUnparseFlag(SolveParameters solve_parameters);
438
439} // namespace math_opt
440} // namespace operations_research
441
442#endif // OR_TOOLS_MATH_OPT_CPP_PARAMETERS_H_
#define MATH_OPT_DEFINE_ENUM(CppEnum, proto_unspecified_value)
Definition enums.h:325
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
When the underlying default is used When the feature cannot be turned kOff will return an error If the feature is enabled by the solver default is typically If the feature is kLow
Definition parameters.h:182
bool AbslParseFlag(const absl::string_view text, SolverType *const value, std::string *const error)
SolverType
The solvers supported by MathOpt.
Definition parameters.h:41
Emphasis
never give an error, and will map onto their best match.
Definition parameters.h:184
LPAlgorithm
Selects an algorithm for solving linear programs.
Definition parameters.h:133
When the underlying default is used When the feature cannot be turned kOff will return an error If the feature is enabled by the solver default is typically If the feature is kMedium
Definition parameters.h:182
std::string AbslUnparseFlag(const SolverType value)
When the underlying default is used When the feature cannot be turned kOff will return an error If the feature is enabled by the solver default is typically If the feature is kHigh
Definition parameters.h:182
In SWIG mode, we don't want anything besides these top-level includes.
std::optional< bool > compute_unbound_rays_if_possible
Definition parameters.h:251
static GlpkParameters FromProto(const GlpkParametersProto &proto)
gtl::linked_hash_map< std::string, std::string > param_values
Parameter name-value pairs to set in insertion order.
Definition parameters.h:221
static GurobiParameters FromProto(const GurobiParametersProto &proto)
std::optional< LPAlgorithm > lp_algorithm
Definition parameters.h:398
pdlp::PrimalDualHybridGradientParams pdlp
Definition parameters.h:424
static absl::StatusOr< SolveParameters > FromProto(const SolveParametersProto &proto)
std::optional< int32_t > threads
If unset, use the solver default. If set, it must be >= 1.
Definition parameters.h:337