CPMpy ortools interface (cpmpy.solvers.ortools)

Interface to OR-Tools’ CP-SAT Python API.

Google OR-Tools is open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions. The OR-Tools CP-SAT solver is an award-winning constraint programming solver that uses SAT (satisfiability) methods and lazy-clause generation (see https://developers.google.com/optimization).

Always use cp.SolverLookup.get("ortools") to instantiate the solver object.

Installation

The ‘ortools’ python package is bundled by default with CPMpy. It can also be installed separately through pip:

$ pip install ortools

Detailed installation instructions available at: https://developers.google.com/optimization/install

The rest of this documentation is for advanced users.

List of classes

CPM_ortools

Interface to OR-Tools' CP-SAT Python API.

Module details

class cpmpy.solvers.ortools.CPM_ortools(cpm_model=None, subsolver=None)[source]

Interface to OR-Tools’ CP-SAT Python API.

Creates the following attributes (see parent constructor for more):

  • ort_model: the ortools.sat.python.cp_model.CpModel() created by _model()

  • ort_solver: the ortools cp_model.CpSolver() instance used in solve()

The DirectConstraint, when used, calls a function on the ort_model object.

Documentation of the solver’s own Python API: https://developers.google.com/optimization/reference/python/sat/python/cp_model

add(cpm_expr)[source]

Eagerly add a constraint to the underlying solver.

Any CPMpy expression given is immediately transformed (through transform()) and then posted to the solver in this function.

This can raise ‘NotImplementedError’ for any constraint not supported after transformation

The variables used in expressions given to add are stored as ‘user variables’. Those are the only ones the user knows and cares about (and will be populated with a value after solve). All other variables are auxiliary variables created by transformations.

Parameters:

cpm_expr (Expression or list of Expression) – CPMpy expression, or list thereof

Returns:

self

classmethod default_params()[source]
get_core()[source]

For use with s.solve(assumptions=[...]). Only meaningful if the solver returned UNSAT. In that case, get_core() returns a small subset of assumption variables that are unsat together.

CPMpy will return only those variables that are False (in the UNSAT core)

Note that there is no guarantee that the core is minimal, though this interface does open up the possibility to add more advanced Minimal Unsatisfiabile Subset algorithms on top. All contributions welcome!

For pure OR-Tools example, see http://github.com/google/or-tools/blob/master/ortools/sat/samples/assumptions_sample_sat.py

Requires ortools >= 8.2!!!

has_objective()[source]

Returns whether the solver has an objective function or not.

maximize(expr)

Post the given expression to the solver as objective to maximize

maximize() can be called multiple times, only the last one is stored

minimize(expr)

Post the given expression to the solver as objective to minimize

minimize() can be called multiple times, only the last one is stored

property native_model

Returns the solver’s underlying native model (for direct solver access).

objective(expr, minimize)[source]

Post the given expression to the solver as objective to minimize/maximize

  • expr: Expression, the CPMpy expression that represents the objective function

  • minimize: Bool, whether it is a minimization problem (True) or maximization problem (False)

‘objective()’ can be called multiple times, only the last one is stored

Note

technical side note: any constraints created during conversion of the objective are premanently posted to the solver

objective_value()

Returns the value of the objective function of the latest solver run on this model

Returns:

an integer or ‘None’ if it is not run, or a satisfaction problem

solution_hint(cpm_vars, vals)[source]

OR-Tools supports warmstarting the solver with a feasible solution.

More specifically, it will branch that variable on that value first if possible. This is known as ‘phase saving’ in the SAT literature, but then extended to integer variables.

The solution hint does NOT need to satisfy all constraints, it should just provide reasonable default values for the variables. It can decrease solving times substantially, especially when solving a similar model repeatedly.

Parameters:
  • cpm_vars – list of CPMpy variables

  • vals – list of (corresponding) values for the variables

solve(time_limit=None, assumptions=None, solution_callback=None, **kwargs)[source]

Call the CP-SAT solver

Parameters:
  • time_limit (float, optional) – maximum solve time in seconds

  • assumptions – list of CPMpy Boolean variables (or their negation) that are assumed to be true. For repeated solving, and/or for use with s.get_core(): if the model is UNSAT, get_core() returns a small subset of assumption variables that are unsat together. Note: the or-tools interface is stateless, so you can incrementally call solve() with assumptions, but or-tools will always start from scratch…

  • solution_callback (an ort.CpSolverSolutionCallback object) – CPMpy includes its own, namely OrtSolutionCounter. If you want to count all solutions, don’t forget to also add the keyword argument ‘enumerate_all_solutions=True’.

The ortools solver parameters are defined in its ‘sat_parameters.proto’ description: https://github.com/google/or-tools/blob/stable/ortools/sat/sat_parameters.proto

You can use any of these parameters as keyword argument to solve() and they will be forwarded to the solver. Examples include:

Argument

Description

num_search_workers=8

number of parallel workers (default: 8)

log_search_progress=True

to log the search process to stdout (default: False)

cp_model_presolve=False

to disable presolve (default: True, almost always beneficial)

cp_model_probing_level=0

to disable probing (default: 2, also valid: 1, maybe 3, etc…)

linearization_level=0

to disable linearisation (default: 1, can also set to 2)

optimize_with_core=True

to do max-sat like lowerbound optimisation (default: False)

use_branching_in_lp=True

to generate more info in lp propagator (default: False)

polish_lp_solution=True

to spend time in lp propagator searching integer values (default: False)

symmetry_level=1

only do symmetry breaking in presolve (default: 2, also possible: 0)

Examples

o.solve(num_search_workers=8, log_search_progress=True)
solveAll(display=None, time_limit=None, solution_limit=None, call_from_model=False, **kwargs)[source]

A shorthand to (efficiently) compute all solutions, map them to CPMpy and optionally display the solutions.

It is just a wrapper around the use of OrtSolutionPrinter() in fact.

Parameters:
  • display – either a list of CPMpy expressions, OR a callback function, called with the variables after value-mapping. default/None: nothing displayed

  • solution_limit – stop after this many solutions (default: None)

  • call_from_model – whether the method is called from a CPMpy Model instance or not

Returns:

number of solutions found

solver_var(cpm_var)[source]

Creates solver variable for cpmpy variable or returns from cache if previously created

solver_vars(cpm_vars)

Like solver_var() but for arbitrary shaped lists/tensors

status()
static supported()[source]

Check for support in current system setup. Return True if the system has package installed or supports solver, else returns False.

Returns:

Solver support by current system setup.

Return type:

[bool]

transform(cpm_expr)[source]

Transform arbitrary CPMpy expressions to constraints the solver supports

Implemented through chaining multiple solver-independent transformation functions from the cpmpy/transformations/ directory.

See the Adding a new solver docs on readthedocs for more information.

Parameters:

cpm_expr (Expression or list of Expression) – CPMpy expression, or list thereof

Returns:

list of Expression

classmethod tunable_params()[source]

Suggestion of tunable hyperparameters of the solver. List compiled based on a conversation with OR-tools’ Laurent Perron (issue #138).