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
6// http://www.apache.org/licenses/LICENSE-2.0
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.
14// Configures the behavior of a MathOpt solver.
18package operations_research.service.v1.mathopt;
20import "google/protobuf/duration.proto";
22option java_multiple_files = true;
23option java_package = "com.google.ortools.service.v1.mathopt";
24option csharp_namespace = "Google.OrTools.Service";
26// The solvers supported by MathOpt.
28 SOLVER_TYPE_UNSPECIFIED = 0;
30 // Solving Constraint Integer Programs (SCIP) solver (third party).
32 // Supports LP, MIP, and nonconvex integer quadratic problems. No dual data
33 // for LPs is returned though. Prefer GLOP for LPs.
34 SOLVER_TYPE_GSCIP = 1;
36 // Gurobi solver (third party).
38 // Supports LP, MIP, and nonconvex integer quadratic problems. Generally the
39 // fastest option, but has special licensing.
40 SOLVER_TYPE_GUROBI = 2;
42 // Google's Glop solver.
44 // Supports LP with primal and dual simplex methods.
47 // Google's CP-SAT solver.
49 // Supports problems where all variables are integer and bounded (or implied
50 // to be after presolve). Experimental support to rescale and discretize
51 // problems with continuous variables.
52 SOLVER_TYPE_CP_SAT = 4;
54 // Google's PDLP solver.
56 // Supports LP and convex diagonal quadratic objectives. Uses first order
57 // methods rather than simplex. Can solve very large problems.
60 // GNU Linear Programming Kit (GLPK) (third party).
62 // Supports MIP and LP.
64 // Thread-safety: GLPK use thread-local storage for memory allocations. As a
65 // consequence Solver instances must be destroyed on the same thread as they
66 // are created or GLPK will crash. It seems OK to call Solver::Solve() from
67 // another thread than the one used to create the Solver but it is not
68 // documented by GLPK and should be avoided.
70 // When solving a LP with the presolver, a solution (and the unbound rays) are
71 // only returned if an optimal solution has been found. Else nothing is
72 // returned. See glpk-5.0/doc/glpk.pdf page #40 available from glpk-5.0.tar.gz
76 // The Operator Splitting Quadratic Program (OSQP) solver (third party).
78 // Supports continuous problems with linear constraints and linear or convex
79 // quadratic objectives. Uses a first-order method.
82 // The Embedded Conic Solver (ECOS) (third party).
84 // Supports LP and SOCP problems. Uses interior point methods (barrier).
87 // The Splitting Conic Solver (SCS) (third party).
89 // Supports LP and SOCP problems. Uses a first-order method.
92 // The HiGHS Solver (third party).
94 // Supports LP and MIP problems (convex QPs are unimplemented).
95 SOLVER_TYPE_HIGHS = 10;
97 // MathOpt's reference implementation of a MIP solver.
99 // Slow/not recommended for production. Not an LP solver (no dual information
101 SOLVER_TYPE_SANTORINI = 11;
103 // Fico XPRESS solver (third party).
105 // Supports LP, MIP, and nonconvex integer quadratic problems.
106 // A fast option, but has special licensing.
107 SOLVER_TYPE_XPRESS = 12;
110// Selects an algorithm for solving linear programs.
111enum LPAlgorithmProto {
112 LP_ALGORITHM_UNSPECIFIED = 0;
114 // The (primal) simplex method. Typically can provide primal and dual
115 // solutions, primal/dual rays on primal/dual unbounded problems, and a basis.
116 LP_ALGORITHM_PRIMAL_SIMPLEX = 1;
118 // The dual simplex method. Typically can provide primal and dual
119 // solutions, primal/dual rays on primal/dual unbounded problems, and a basis.
120 LP_ALGORITHM_DUAL_SIMPLEX = 2;
122 // The barrier method, also commonly called an interior point method (IPM).
123 // Can typically give both primal and dual solutions. Some implementations can
124 // also produce rays on unbounded/infeasible problems. A basis is not given
125 // unless the underlying solver does "crossover" and finishes with simplex.
126 LP_ALGORITHM_BARRIER = 3;
128 // An algorithm based around a first-order method. These will typically
129 // produce both primal and dual solutions, and potentially also certificates
130 // of primal and/or dual infeasibility. First-order methods typically will
131 // provide solutions with lower accuracy, so users should take care to set
132 // solution quality parameters (e.g., tolerances) and to validate solutions.
133 LP_ALGORITHM_FIRST_ORDER = 4;
136// Effort level applied to an optional task while solving (see
137// SolveParametersProto for use).
139// Emphasis is used to configure a solver feature as follows:
140// * If a solver doesn't support the feature, only UNSPECIFIED will always be
141// valid, any other setting will typically an invalid argument error (some
142// solvers may also accept OFF).
143// * If the solver supports the feature:
144// - When set to UNSPECIFIED, the underlying default is used.
145// - When the feature cannot be turned off, OFF will return an error.
146// - If the feature is enabled by default, the solver default is typically
148// - If the feature is supported, LOW, MEDIUM, HIGH, and VERY HIGH will never
149// give an error, and will map onto their best match.
151 EMPHASIS_UNSPECIFIED = 0;
156 EMPHASIS_VERY_HIGH = 5;
159// Parameters to control a single solve.
161// Contains both parameters common to all solvers e.g. time_limit, and
162// parameters for a specific solver, e.g. gscip. If a value is set in both
163// common and solver specific field, the solver specific setting is used.
165// The common parameters that are optional and unset or an enum with value
166// unspecified indicate that the solver default is used.
168// Solver specific parameters for solvers other than the one in use are ignored.
170// Parameters that depends on the model (e.g. branching priority is set for
171// each variable) are passed in ModelSolveParametersProto.
172message SolveParametersProto {
173 // Maximum time a solver should spend on the problem (or infinite if not set).
175 // This value is not a hard limit, solve time may slightly exceed this value.
176 // This parameter is always passed to the underlying solver, the solver
177 // default is not used.
178 google.protobuf.Duration time_limit = 1;
180 // Limit on the iterations of the underlying algorithm (e.g. simplex pivots).
181 // The specific behavior is dependent on the solver and algorithm used, but
182 // often can give a deterministic solve limit (further configuration may be
183 // needed, e.g. one thread).
185 // Typically supported by LP, QP, and MIP solvers, but for MIP solvers see
187 optional int64 iteration_limit = 2;
189 // Limit on the number of subproblems solved in enumerative search (e.g.
190 // branch and bound). For many solvers this can be used to deterministically
191 // limit computation (further configuration may be needed, e.g. one thread).
193 // Typically for MIP solvers, see also iteration_limit.
194 optional int64 node_limit = 24;
196 // The solver stops early if it can prove there are no primal solutions at
197 // least as good as cutoff.
199 // On an early stop, the solver returns termination reason NO_SOLUTION_FOUND
200 // and with limit CUTOFF and is not required to give any extra solution
201 // information. Has no effect on the return value if there is no early stop.
203 // It is recommended that you use a tolerance if you want solutions with
204 // objective exactly equal to cutoff to be returned.
206 // See the user guide for more details and a comparison with best_bound_limit.
207 optional double cutoff_limit = 20;
209 // The solver stops early as soon as it finds a solution at least this good,
210 // with termination reason FEASIBLE and limit OBJECTIVE.
211 optional double objective_limit = 21;
213 // The solver stops early as soon as it proves the best bound is at least this
214 // good, with termination reason FEASIBLE or NO_SOLUTION_FOUND and limit
217 // See the user guide for more details and a comparison with cutoff_limit.
218 optional double best_bound_limit = 22;
220 // The solver stops early after finding this many feasible solutions, with
221 // termination reason FEASIBLE and limit SOLUTION. Must be greater than zero
222 // if set. It is often used get the solver to stop on the first feasible
223 // solution found. Note that there is no guarantee on the objective value for
224 // any of the returned solutions.
226 // Solvers will typically not return more solutions than the solution limit,
227 // but this is not enforced by MathOpt, see also b/214041169.
229 // Currently supported for Gurobi and SCIP, and for CP-SAT only with value 1.
230 optional int32 solution_limit = 23;
232 // Enables printing the solver implementation traces. The location of those
233 // traces depend on the solver. For SCIP and Gurobi this will be the standard
234 // output streams. For Glop and CP-SAT this will LOG(INFO).
236 // Note that if the solver supports message callback and the user registers a
237 // callback for it, then this parameter value is ignored and no traces are
239 bool enable_output = 3;
241 // If set, it must be >= 1.
242 optional int32 threads = 4;
244 // Seed for the pseudo-random number generator in the underlying
245 // solver. Note that all solvers use pseudo-random numbers to select things
246 // such as perturbation in the LP algorithm, for tie-break-up rules, and for
247 // heuristic fixings. Varying this can have a noticeable impact on solver
250 // Although all solvers have a concept of seeds, note that valid values
251 // depend on the actual solver.
252 // - Gurobi: [0:GRB_MAXINT] (which as of Gurobi 9.0 is 2x10^9).
253 // - GSCIP: [0:2147483647] (which is MAX_INT or kint32max or 2^31-1).
254 // - GLOP: [0:2147483647] (same as above)
255 // In all cases, the solver will receive a value equal to:
256 // MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, random_seed)).
257 optional int32 random_seed = 5;
259 // An absolute optimality tolerance (primarily) for MIP solvers.
261 // The absolute GAP is the absolute value of the difference between:
262 // * the objective value of the best feasible solution found,
263 // * the dual bound produced by the search.
264 // The solver can stop once the absolute GAP is at most absolute_gap_tolerance
265 // (when set), and return TERMINATION_REASON_OPTIMAL.
267 // Must be >= 0 if set.
269 // See also relative_gap_tolerance.
270 optional double absolute_gap_tolerance = 18;
272 // A relative optimality tolerance (primarily) for MIP solvers.
274 // The relative GAP is a normalized version of the absolute GAP (defined on
275 // absolute_gap_tolerance), where the normalization is solver-dependent, e.g.
276 // the absolute GAP divided by the objective value of the best feasible
279 // The solver can stop once the relative GAP is at most relative_gap_tolerance
280 // (when set), and return TERMINATION_REASON_OPTIMAL.
282 // Must be >= 0 if set.
284 // See also absolute_gap_tolerance.
285 optional double relative_gap_tolerance = 17;
287 // Maintain up to `solution_pool_size` solutions while searching. The solution
288 // pool generally has two functions:
289 // (1) For solvers that can return more than one solution, this limits how
290 // many solutions will be returned.
291 // (2) Some solvers may run heuristics using solutions from the solution
292 // pool, so changing this value may affect the algorithm's path.
293 // To force the solver to fill the solution pool, e.g. with the n best
294 // solutions, requires further, solver specific configuration.
295 optional int32 solution_pool_size = 25;
297 // The algorithm for solving a linear program. If LP_ALGORITHM_UNSPECIFIED,
298 // use the solver default algorithm.
300 // For problems that are not linear programs but where linear programming is
301 // a subroutine, solvers may use this value. E.g. MIP solvers will typically
302 // use this for the root LP solve only (and use dual simplex otherwise).
303 LPAlgorithmProto lp_algorithm = 6;
305 // Effort on simplifying the problem before starting the main algorithm, or
306 // the solver default effort level if EMPHASIS_UNSPECIFIED.
307 EmphasisProto presolve = 7;
309 // Effort on getting a stronger LP relaxation (MIP only), or the solver
310 // default effort level if EMPHASIS_UNSPECIFIED.
312 // NOTE: disabling cuts may prevent callbacks from having a chance to add cuts
313 // at MIP_NODE, this behavior is solver specific.
314 EmphasisProto cuts = 8;
316 // Effort in finding feasible solutions beyond those encountered in the
317 // complete search procedure (MIP only), or the solver default effort level if
318 // EMPHASIS_UNSPECIFIED.
319 EmphasisProto heuristics = 9;
321 // Effort in rescaling the problem to improve numerical stability, or the
322 // solver default effort level if EMPHASIS_UNSPECIFIED.
323 EmphasisProto scaling = 10;
325 reserved 12, 13, 14, 15, 16, 19, 26, 27;
327 reserved 11; // Deleted