ortools.math_opt.python.parameters

  1# Copyright 2010-2024 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"""Configures the solving of an optimization model."""
 15
 16import dataclasses
 17import datetime
 18import enum
 19from typing import Dict, Optional
 20
 21from ortools.pdlp import solvers_pb2 as pdlp_solvers_pb2
 22from ortools.glop import parameters_pb2 as glop_parameters_pb2
 23from ortools.gscip import gscip_pb2
 24from ortools.math_opt import parameters_pb2 as math_opt_parameters_pb2
 25from ortools.math_opt.solvers import glpk_pb2
 26from ortools.math_opt.solvers import gurobi_pb2
 27from ortools.math_opt.solvers import highs_pb2
 28from ortools.math_opt.solvers import osqp_pb2
 29from ortools.sat import sat_parameters_pb2
 30
 31
 32@enum.unique
 33class SolverType(enum.Enum):
 34    """The underlying solver to use.
 35
 36    This must stay synchronized with math_opt_parameters_pb2.SolverTypeProto.
 37
 38    Attributes:
 39      GSCIP: Solving Constraint Integer Programs (SCIP) solver (third party).
 40        Supports LP, MIP, and nonconvex integer quadratic problems. No dual data
 41        for LPs is returned though. Prefer GLOP for LPs.
 42      GUROBI: Gurobi solver (third party). Supports LP, MIP, and nonconvex integer
 43        quadratic problems. Generally the fastest option, but has special
 44        licensing, see go/gurobi-google for details.
 45      GLOP: Google's Glop linear solver. Supports LP with primal and dual simplex
 46        methods.
 47      CP_SAT: Google's CP-SAT solver. Supports problems where all variables are
 48        integer and bounded (or implied to be after presolve). Experimental
 49        support to rescale and discretize problems with continuous variables.
 50      MOE:begin_intracomment_strip
 51      PDLP: Google's PDLP solver. Supports LP and convex diagonal quadratic
 52        objectives. Uses first order methods rather than simplex. Can solve very
 53        large problems.
 54      MOE:end_intracomment_strip
 55      GLPK: GNU Linear Programming Kit (GLPK) (third party). Supports MIP and LP.
 56        Thread-safety: GLPK use thread-local storage for memory allocations. As a
 57        consequence when using IncrementalSolver, the user must make sure that
 58        instances are closed on the same thread as they are created or GLPK will
 59        crash. To do so, use `with` or call IncrementalSolver#close(). It seems OK
 60        to call IncrementalSolver#Solve() from another thread than the one used to
 61        create the Solver but it is not documented by GLPK and should be avoided.
 62        Of course these limitations do not apply to the solve() function that
 63        recreates a new GLPK problem in the calling thread and destroys before
 64        returning.  When solving a LP with the presolver, a solution (and the
 65        unbound rays) are only returned if an optimal solution has been found.
 66        Else nothing is returned. See glpk-5.0/doc/glpk.pdf page #40 available
 67        from glpk-5.0.tar.gz for details.
 68      OSQP: The Operator Splitting Quadratic Program (OSQP) solver (third party).
 69        Supports continuous problems with linear constraints and linear or convex
 70        quadratic objectives. Uses a first-order method.
 71      ECOS: The Embedded Conic Solver (ECOS) (third party). Supports LP and SOCP
 72        problems. Uses interior point methods (barrier).
 73      SCS: The Splitting Conic Solver (SCS) (third party). Supports LP and SOCP
 74        problems. Uses a first-order method.
 75      HIGHS: The HiGHS Solver (third party). Supports LP and MIP problems (convex
 76        QPs are unimplemented).
 77      SANTORINI: The Santorini Solver (first party). Supports MIP. Experimental,
 78        do not use in production.
 79    """
 80
 81    GSCIP = math_opt_parameters_pb2.SOLVER_TYPE_GSCIP
 82    GUROBI = math_opt_parameters_pb2.SOLVER_TYPE_GUROBI
 83    GLOP = math_opt_parameters_pb2.SOLVER_TYPE_GLOP
 84    CP_SAT = math_opt_parameters_pb2.SOLVER_TYPE_CP_SAT
 85    PDLP = math_opt_parameters_pb2.SOLVER_TYPE_PDLP
 86    GLPK = math_opt_parameters_pb2.SOLVER_TYPE_GLPK
 87    OSQP = math_opt_parameters_pb2.SOLVER_TYPE_OSQP
 88    ECOS = math_opt_parameters_pb2.SOLVER_TYPE_ECOS
 89    SCS = math_opt_parameters_pb2.SOLVER_TYPE_SCS
 90    HIGHS = math_opt_parameters_pb2.SOLVER_TYPE_HIGHS
 91    SANTORINI = math_opt_parameters_pb2.SOLVER_TYPE_SANTORINI
 92
 93
 94def solver_type_from_proto(
 95    proto_value: math_opt_parameters_pb2.SolverTypeProto,
 96) -> Optional[SolverType]:
 97    if proto_value == math_opt_parameters_pb2.SOLVER_TYPE_UNSPECIFIED:
 98        return None
 99    return SolverType(proto_value)
100
101
102def solver_type_to_proto(
103    solver_type: Optional[SolverType],
104) -> math_opt_parameters_pb2.SolverTypeProto:
105    if solver_type is None:
106        return math_opt_parameters_pb2.SOLVER_TYPE_UNSPECIFIED
107    return solver_type.value
108
109
110@enum.unique
111class LPAlgorithm(enum.Enum):
112    """Selects an algorithm for solving linear programs.
113
114    Attributes:
115      * UNPSECIFIED: No algorithm is selected.
116      * PRIMAL_SIMPLEX: The (primal) simplex method. Typically can provide primal
117        and dual solutions, primal/dual rays on primal/dual unbounded problems,
118        and a basis.
119      * DUAL_SIMPLEX: The dual simplex method. Typically can provide primal and
120        dual solutions, primal/dual rays on primal/dual unbounded problems, and a
121        basis.
122      * BARRIER: The barrier method, also commonly called an interior point method
123        (IPM). Can typically give both primal and dual solutions. Some
124        implementations can also produce rays on unbounded/infeasible problems. A
125        basis is not given unless the underlying solver does "crossover" and
126        finishes with simplex.
127      * FIRST_ORDER: An algorithm based around a first-order method. These will
128        typically produce both primal and dual solutions, and potentially also
129        certificates of primal and/or dual infeasibility. First-order methods
130        typically will provide solutions with lower accuracy, so users should take
131        care to set solution quality parameters (e.g., tolerances) and to validate
132        solutions.
133
134    This must stay synchronized with math_opt_parameters_pb2.LPAlgorithmProto.
135    """
136
137    PRIMAL_SIMPLEX = math_opt_parameters_pb2.LP_ALGORITHM_PRIMAL_SIMPLEX
138    DUAL_SIMPLEX = math_opt_parameters_pb2.LP_ALGORITHM_DUAL_SIMPLEX
139    BARRIER = math_opt_parameters_pb2.LP_ALGORITHM_BARRIER
140    FIRST_ORDER = math_opt_parameters_pb2.LP_ALGORITHM_FIRST_ORDER
141
142
143def lp_algorithm_from_proto(
144    proto_value: math_opt_parameters_pb2.LPAlgorithmProto,
145) -> Optional[LPAlgorithm]:
146    if proto_value == math_opt_parameters_pb2.LP_ALGORITHM_UNSPECIFIED:
147        return None
148    return LPAlgorithm(proto_value)
149
150
151def lp_algorithm_to_proto(
152    lp_algorithm: Optional[LPAlgorithm],
153) -> math_opt_parameters_pb2.LPAlgorithmProto:
154    if lp_algorithm is None:
155        return math_opt_parameters_pb2.LP_ALGORITHM_UNSPECIFIED
156    return lp_algorithm.value
157
158
159@enum.unique
160class Emphasis(enum.Enum):
161    """Effort level applied to an optional task while solving (see SolveParameters for use).
162
163    - OFF: disable this task.
164    - LOW: apply reduced effort.
165    - MEDIUM: typically the default setting (unless the default is off).
166    - HIGH: apply extra effort beyond MEDIUM.
167    - VERY_HIGH: apply the maximum effort.
168
169    Typically used as Optional[Emphasis]. It used to configure a solver feature as
170    follows:
171      * If a solver doesn't support the feature, only None will always be valid,
172        any other setting will give an invalid argument error (some solvers may
173        also accept OFF).
174      * If the solver supports the feature:
175        - When set to None, the underlying default is used.
176        - When the feature cannot be turned off, OFF will produce an error.
177        - If the feature is enabled by default, the solver default is typically
178          mapped to MEDIUM.
179        - If the feature is supported, LOW, MEDIUM, HIGH, and VERY HIGH will never
180          give an error, and will map onto their best match.
181
182    This must stay synchronized with math_opt_parameters_pb2.EmphasisProto.
183    """
184
185    OFF = math_opt_parameters_pb2.EMPHASIS_OFF
186    LOW = math_opt_parameters_pb2.EMPHASIS_LOW
187    MEDIUM = math_opt_parameters_pb2.EMPHASIS_MEDIUM
188    HIGH = math_opt_parameters_pb2.EMPHASIS_HIGH
189    VERY_HIGH = math_opt_parameters_pb2.EMPHASIS_VERY_HIGH
190
191
192def emphasis_from_proto(
193    proto_value: math_opt_parameters_pb2.EmphasisProto,
194) -> Optional[Emphasis]:
195    if proto_value == math_opt_parameters_pb2.EMPHASIS_UNSPECIFIED:
196        return None
197    return Emphasis(proto_value)
198
199
200def emphasis_to_proto(
201    emphasis: Optional[Emphasis],
202) -> math_opt_parameters_pb2.EmphasisProto:
203    if emphasis is None:
204        return math_opt_parameters_pb2.EMPHASIS_UNSPECIFIED
205    return emphasis.value
206
207
208@dataclasses.dataclass
209class GurobiParameters:
210    """Gurobi specific parameters for solving.
211
212    See https://www.gurobi.com/documentation/9.1/refman/parameters.html for a list
213    of possible parameters.
214
215    Example use:
216      gurobi=GurobiParameters();
217      gurobi.param_values["BarIterLimit"] = "10";
218
219    With Gurobi, the order that parameters are applied can have an impact in rare
220    situations. Parameters are applied in the following order:
221     * LogToConsole is set from SolveParameters.enable_output.
222     * Any common parameters not overwritten by GurobiParameters.
223     * param_values in iteration order (insertion order).
224    We set LogToConsole first because setting other parameters can generate
225    output.
226    """
227
228    param_values: Dict[str, str] = dataclasses.field(default_factory=dict)
229
230    def to_proto(self) -> gurobi_pb2.GurobiParametersProto:
231        return gurobi_pb2.GurobiParametersProto(
232            parameters=[
233                gurobi_pb2.GurobiParametersProto.Parameter(name=key, value=val)
234                for key, val in self.param_values.items()
235            ]
236        )
237
238
239@dataclasses.dataclass
240class GlpkParameters:
241    """GLPK specific parameters for solving.
242
243    Fields are optional to enable to capture user intention; if they set
244    explicitly a value to then no generic solve parameters will overwrite this
245    parameter. User specified solver specific parameters have priority on generic
246    parameters.
247
248    Attributes:
249      compute_unbound_rays_if_possible: Compute the primal or dual unbound ray
250        when the variable (structural or auxiliary) causing the unboundness is
251        identified (see glp_get_unbnd_ray()). The unset value is equivalent to
252        false. Rays are only available when solving linear programs, they are not
253        available for MIPs. On top of that they are only available when using a
254        simplex algorithm with the presolve disabled. A primal ray can only be
255        built if the chosen LP algorithm is LPAlgorithm.PRIMAL_SIMPLEX. Same for a
256        dual ray and LPAlgorithm.DUAL_SIMPLEX. The computation involves the basis
257        factorization to be available which may lead to extra computations/errors.
258    """
259
260    compute_unbound_rays_if_possible: Optional[bool] = None
261
262    def to_proto(self) -> glpk_pb2.GlpkParametersProto:
263        return glpk_pb2.GlpkParametersProto(
264            compute_unbound_rays_if_possible=self.compute_unbound_rays_if_possible
265        )
266
267
268@dataclasses.dataclass
269class SolveParameters:
270    """Parameters to control a single solve.
271
272  If a value is set in both common and solver specific field (e.g. gscip), the
273  solver specific setting is used.
274
275  Solver specific parameters for solvers other than the one in use are ignored.
276
277  Parameters that depends on the model (e.g. branching priority is set for each
278  variable) are passed in ModelSolveParameters.
279
280  See solve() and IncrementalSolver.solve() in solve.py for more details.
281
282  Attributes:
283    time_limit: The maximum time a solver should spend on the problem, or if
284      None, then the time limit is infinite. This value is not a hard limit,
285      solve time may slightly exceed this value. This parameter is always passed
286      to the underlying solver, the solver default is not used.
287    iteration_limit: Limit on the iterations of the underlying algorithm (e.g.
288      simplex pivots). The specific behavior is dependent on the solver and
289      algorithm used, but often can give a deterministic solve limit (further
290      configuration may be needed, e.g. one thread). Typically supported by LP,
291      QP, and MIP solvers, but for MIP solvers see also node_limit.
292    node_limit: Limit on the number of subproblems solved in enumerative search
293      (e.g. branch and bound). For many solvers this can be used to
294      deterministically limit computation (further configuration may be needed,
295      e.g. one thread). Typically for MIP solvers, see also iteration_limit.
296    cutoff_limit: The solver stops early if it can prove there are no primal
297      solutions at least as good as cutoff. On an early stop, the solver returns
298      TerminationReason.NO_SOLUTION_FOUND and with Limit.CUTOFF and is not
299      required to give any extra solution information. Has no effect on the
300      return value if there is no early stop. It is recommended that you use a
301      tolerance if you want solutions with objective exactly equal to cutoff to
302      be returned. See the user guide for more details and a comparison with
303      best_bound_limit.
304    objective_limit: The solver stops early as soon as it finds a solution at
305      least this good, with TerminationReason.FEASIBLE and Limit.OBJECTIVE.
306    best_bound_limit: The solver stops early as soon as it proves the best bound
307      is at least this good, with TerminationReason of FEASIBLE or
308      NO_SOLUTION_FOUND and Limit.OBJECTIVE. See the user guide for more details
309      and a comparison with cutoff_limit.
310    solution_limit: The solver stops early after finding this many feasible
311      solutions, with TerminationReason.FEASIBLE and Limit.SOLUTION. Must be
312      greater than zero if set. It is often used get the solver to stop on the
313      first feasible solution found. Note that there is no guarantee on the
314      objective value for any of the returned solutions. Solvers will typically
315      not return more solutions than the solution limit, but this is not
316      enforced by MathOpt, see also b/214041169. Currently supported for Gurobi
317      and SCIP, and for CP-SAT only with value 1.
318    enable_output: If the solver should print out its log messages.
319    threads: An integer >= 1, how many threads to use when solving.
320    random_seed: Seed for the pseudo-random number generator in the underlying
321      solver. Note that valid values depend on the actual solver:
322        * Gurobi: [0:GRB_MAXINT] (which as of Gurobi 9.0 is 2x10^9).
323        * GSCIP: [0:2147483647] (which is MAX_INT or kint32max or 2^31-1).
324        * GLOP: [0:2147483647] (same as above).
325      In all cases, the solver will receive a value equal to:
326      MAX(0, MIN(MAX_VALID_VALUE_FOR_SOLVER, random_seed)).
327    absolute_gap_tolerance: An absolute optimality tolerance (primarily) for MIP
328      solvers. The absolute GAP is the absolute value of the difference between:
329        * the objective value of the best feasible solution found,
330        * the dual bound produced by the search.
331      The solver can stop once the absolute GAP is at most
332      absolute_gap_tolerance (when set), and return TerminationReason.OPTIMAL.
333      Must be >= 0 if set. See also relative_gap_tolerance.
334    relative_gap_tolerance: A relative optimality tolerance (primarily) for MIP
335      solvers. The relative GAP is a normalized version of the absolute GAP
336      (defined on absolute_gap_tolerance), where the normalization is
337      solver-dependent, e.g. the absolute GAP divided by the objective value of
338      the best feasible solution found. The solver can stop once the relative
339      GAP is at most relative_gap_tolerance (when set), and return
340      TerminationReason.OPTIMAL. Must be >= 0 if set. See also
341      absolute_gap_tolerance.
342    solution_pool_size: Maintain up to `solution_pool_size` solutions while
343      searching. The solution pool generally has two functions:
344        * For solvers that can return more than one solution, this limits how
345          many solutions will be returned.
346        * Some solvers may run heuristics using solutions from the solution
347          pool, so changing this value may affect the algorithm's path.
348      To force the solver to fill the solution pool, e.g. with the n best
349      solutions, requires further, solver specific configuration.
350    lp_algorithm: The algorithm for solving a linear program. If UNSPECIFIED,
351      use the solver default algorithm. For problems that are not linear
352      programs but where linear programming is a subroutine, solvers may use
353      this value. E.g. MIP solvers will typically use this for the root LP solve
354      only (and use dual simplex otherwise).
355    presolve: Effort on simplifying the problem before starting the main
356      algorithm (e.g. simplex).
357    cuts: Effort on getting a stronger LP relaxation (MIP only). Note that in
358      some solvers, disabling cuts may prevent callbacks from having a chance to
359      add cuts at MIP_NODE.
360    heuristics: Effort in finding feasible solutions beyond those encountered in
361      the complete search procedure.
362    scaling: Effort in rescaling the problem to improve numerical stability.
363    gscip: GSCIP specific solve parameters.
364    gurobi: Gurobi specific solve parameters.
365    glop: Glop specific solve parameters.
366    cp_sat: CP-SAT specific solve parameters.
367    pdlp: PDLP specific solve parameters.
368    osqp: OSQP specific solve parameters. Users should prefer the generic
369      MathOpt parameters over OSQP-level parameters, when available: - Prefer
370      SolveParameters.enable_output to OsqpSettingsProto.verbose. - Prefer
371      SolveParameters.time_limit to OsqpSettingsProto.time_limit. - Prefer
372      SolveParameters.iteration_limit to OsqpSettingsProto.iteration_limit. - If
373      a less granular configuration is acceptable, prefer
374      SolveParameters.scaling to OsqpSettingsProto.
375    glpk: GLPK specific solve parameters.
376    highs: HiGHS specific solve parameters.
377  """  # fmt: skip
378
379    time_limit: Optional[datetime.timedelta] = None
380    iteration_limit: Optional[int] = None
381    node_limit: Optional[int] = None
382    cutoff_limit: Optional[float] = None
383    objective_limit: Optional[float] = None
384    best_bound_limit: Optional[float] = None
385    solution_limit: Optional[int] = None
386    enable_output: bool = False
387    threads: Optional[int] = None
388    random_seed: Optional[int] = None
389    absolute_gap_tolerance: Optional[float] = None
390    relative_gap_tolerance: Optional[float] = None
391    solution_pool_size: Optional[int] = None
392    lp_algorithm: Optional[LPAlgorithm] = None
393    presolve: Optional[Emphasis] = None
394    cuts: Optional[Emphasis] = None
395    heuristics: Optional[Emphasis] = None
396    scaling: Optional[Emphasis] = None
397    gscip: gscip_pb2.GScipParameters = dataclasses.field(
398        default_factory=gscip_pb2.GScipParameters
399    )
400    gurobi: GurobiParameters = dataclasses.field(default_factory=GurobiParameters)
401    glop: glop_parameters_pb2.GlopParameters = dataclasses.field(
402        default_factory=glop_parameters_pb2.GlopParameters
403    )
404    cp_sat: sat_parameters_pb2.SatParameters = dataclasses.field(
405        default_factory=sat_parameters_pb2.SatParameters
406    )
407    pdlp: pdlp_solvers_pb2.PrimalDualHybridGradientParams = dataclasses.field(
408        default_factory=pdlp_solvers_pb2.PrimalDualHybridGradientParams
409    )
410    osqp: osqp_pb2.OsqpSettingsProto = dataclasses.field(
411        default_factory=osqp_pb2.OsqpSettingsProto
412    )
413    glpk: GlpkParameters = dataclasses.field(default_factory=GlpkParameters)
414    highs: highs_pb2.HighsOptionsProto = dataclasses.field(
415        default_factory=highs_pb2.HighsOptionsProto
416    )
417
418    def to_proto(self) -> math_opt_parameters_pb2.SolveParametersProto:
419        """Returns a protocol buffer equivalent to this."""
420        result = math_opt_parameters_pb2.SolveParametersProto(
421            enable_output=self.enable_output,
422            lp_algorithm=lp_algorithm_to_proto(self.lp_algorithm),
423            presolve=emphasis_to_proto(self.presolve),
424            cuts=emphasis_to_proto(self.cuts),
425            heuristics=emphasis_to_proto(self.heuristics),
426            scaling=emphasis_to_proto(self.scaling),
427            gscip=self.gscip,
428            gurobi=self.gurobi.to_proto(),
429            glop=self.glop,
430            cp_sat=self.cp_sat,
431            pdlp=self.pdlp,
432            osqp=self.osqp,
433            glpk=self.glpk.to_proto(),
434            highs=self.highs,
435        )
436        if self.time_limit is not None:
437            result.time_limit.FromTimedelta(self.time_limit)
438        if self.iteration_limit is not None:
439            result.iteration_limit = self.iteration_limit
440        if self.node_limit is not None:
441            result.node_limit = self.node_limit
442        if self.cutoff_limit is not None:
443            result.cutoff_limit = self.cutoff_limit
444        if self.objective_limit is not None:
445            result.objective_limit = self.objective_limit
446        if self.best_bound_limit is not None:
447            result.best_bound_limit = self.best_bound_limit
448        if self.solution_limit is not None:
449            result.solution_limit = self.solution_limit
450        if self.threads is not None:
451            result.threads = self.threads
452        if self.random_seed is not None:
453            result.random_seed = self.random_seed
454        if self.absolute_gap_tolerance is not None:
455            result.absolute_gap_tolerance = self.absolute_gap_tolerance
456        if self.relative_gap_tolerance is not None:
457            result.relative_gap_tolerance = self.relative_gap_tolerance
458        if self.solution_pool_size is not None:
459            result.solution_pool_size = self.solution_pool_size
460        return result