#!/usr/bin/env python
#-*- coding:utf-8 -*-
##
## gurobi.py
##
"""
Interface to Gurobi Optimizer's Python API.
Gurobi Optimizer is a highly efficient commercial solver for Integer Linear Programming (and more).
Always use :func:`cp.SolverLookup.get("gurobi") <cpmpy.solvers.utils.SolverLookup.get>` to instantiate the solver object.
============
Installation
============
Requires that the 'gurobipy' python package is installed:
.. code-block:: console
$ pip install gurobipy
Gurobi Optimizer requires an active licence (for example a free academic license)
You can read more about available licences at https://www.gurobi.com/downloads/
See detailed installation instructions at:
https://support.gurobi.com/hc/en-us/articles/360044290292-How-do-I-install-Gurobi-for-Python-
The rest of this documentation is for advanced users.
===============
List of classes
===============
.. autosummary::
:nosignatures:
CPM_gurobi
==============
Module details
==============
"""
from .solver_interface import SolverInterface, SolverStatus, ExitStatus
from ..exceptions import NotSupportedError
from ..expressions.core import *
from ..expressions.utils import argvals, argval
from ..expressions.variables import _BoolVarImpl, NegBoolView, _IntVarImpl, _NumVarImpl, intvar
from ..expressions.globalconstraints import DirectConstraint
from ..transformations.comparison import only_numexpr_equality
from ..transformations.decompose_global import decompose_in_tree
from ..transformations.flatten_model import flatten_constraint, flatten_objective
from ..transformations.get_variables import get_variables
from ..transformations.linearize import linearize_constraint, only_positive_bv, only_positive_bv_wsum
from ..transformations.normalize import toplevel_list
from ..transformations.reification import only_implies, reify_rewrite, only_bv_reifies
from ..transformations.safening import no_partial_functions
try:
import gurobipy as gp
GRB_ENV = None
except ImportError:
pass
[docs]class CPM_gurobi(SolverInterface):
"""
Interface to Gurobi's Python API
Creates the following attributes (see parent constructor for more):
- ``grb_model``: object, TEMPLATE's model object
The :class:`~cpmpy.expressions.globalconstraints.DirectConstraint`, when used, calls a function on the ``grb_model`` object.
Documentation of the solver's own Python API:
https://docs.gurobi.com/projects/optimizer/en/current/reference/python.html
"""
[docs] @staticmethod
def supported():
return CPM_gurobi.installed() and CPM_gurobi.license_ok()
[docs] @staticmethod
def installed():
try:
import gurobipy as gp
return True
except ModuleNotFoundError:
return False
except Exception as e:
raise e
[docs] @staticmethod
def license_ok():
if not CPM_gurobi.installed():
warnings.warn(f"License check failed, python package 'gurobipy' is not installed! Please check 'CPM_gurobi.installed()' before attempting to check license.")
return False
try:
import gurobipy as gp
global GRB_ENV
if GRB_ENV is None:
# initialise the native gurobi model object
GRB_ENV = gp.Env(params={"OutputFlag": 0})
GRB_ENV.start()
return True
except Exception as e:
warnings.warn(f"Problem encountered with Gurobi license: {e}")
return False
def __init__(self, cpm_model=None, subsolver=None):
"""
Constructor of the native solver object
Arguments:
cpm_model: a CPMpy Model()
subsolver: None, not used
"""
if not self.installed():
raise Exception("CPM_gurobi: Install the python package 'gurobipy' to use this solver interface.")
elif not self.license_ok():
raise Exception("CPM_gurobi: A problem occured during license check. Make sure your license is activated!")
import gurobipy as gp
# TODO: subsolver could be a GRB_ENV if a user would want to hand one over
self.grb_model = gp.Model(env=GRB_ENV)
# initialise everything else and post the constraints/objective
# it is sufficient to implement add() and minimize/maximize() below
super().__init__(name="gurobi", cpm_model=cpm_model)
@property
def native_model(self):
"""
Returns the solver's underlying native model (for direct solver access).
"""
return self.grb_model
[docs] def solve(self, time_limit=None, solution_callback=None, **kwargs):
"""
Call the gurobi solver
Arguments:
time_limit (float, optional): maximum solve time in seconds
**kwargs: any keyword argument, sets parameters of solver object
Arguments that correspond to solver parameters:
Examples of gurobi supported arguments include:
- ``Threads`` : int
- ``MIPFocus`` : int
- ``ImproveStartTime`` : bool
- ``FlowCoverCuts`` : int
For a full list of gurobi parameters, please visit https://www.gurobi.com/documentation/9.5/refman/parameters.html#sec:Parameters
"""
from gurobipy import GRB
# ensure all vars are known to solver
self.solver_vars(list(self.user_vars))
# set time limit
if time_limit is not None:
if time_limit <= 0:
raise ValueError("Time limit must be positive")
self.grb_model.setParam("TimeLimit", time_limit)
# call the solver, with parameters
for param, val in kwargs.items():
self.grb_model.setParam(param, val)
_ = self.grb_model.optimize(callback=solution_callback)
grb_objective = self.grb_model.getObjective()
grb_status = self.grb_model.Status
# new status, translate runtime
self.cpm_status = SolverStatus(self.name)
self.cpm_status.runtime = self.grb_model.runtime
# translate exit status
if grb_status == GRB.OPTIMAL:
# COP
if self.has_objective():
self.cpm_status.exitstatus = ExitStatus.OPTIMAL
# CSP
else:
self.cpm_status.exitstatus = ExitStatus.FEASIBLE
elif grb_status == GRB.INFEASIBLE:
self.cpm_status.exitstatus = ExitStatus.UNSATISFIABLE
elif grb_status == GRB.TIME_LIMIT:
if self.grb_model.SolCount == 0:
# can be sat or unsat
self.cpm_status.exitstatus = ExitStatus.UNKNOWN
else:
self.cpm_status.exitstatus = ExitStatus.FEASIBLE
else: # another?
raise NotImplementedError(
f"Translation of gurobi status {grb_status} to CPMpy status not implemented") # a new status type was introduced, please report on github
# True/False depending on self.cpm_status
has_sol = self._solve_return(self.cpm_status)
# translate solution values (of user specified variables only)
self.objective_value_ = None
if has_sol:
# fill in variable values
for cpm_var in self.user_vars:
solver_val = self.solver_var(cpm_var).X
if cpm_var.is_bool():
cpm_var._value = solver_val >= 0.5
else:
cpm_var._value = int(solver_val)
# set _objective_value
if self.has_objective():
grb_obj_val = grb_objective.getValue()
if round(grb_obj_val) == grb_obj_val: # it is an integer?:
self.objective_value_ = int(grb_obj_val)
else: # can happen with DirectVar or when using floats as coefficients
self.objective_value_ = float(grb_obj_val)
else: # clear values of variables
for cpm_var in self.user_vars:
cpm_var._value = None
return has_sol
[docs] def solver_var(self, cpm_var):
"""
Creates solver variable for cpmpy variable
or returns from cache if previously created
"""
if is_num(cpm_var): # shortcut, eases posting constraints
return cpm_var
# special case, negative-bool-view
# work directly on var inside the view
if isinstance(cpm_var, NegBoolView):
raise Exception("Negative literals should not be part of any equation. "
"See /transformations/linearize for more details")
# create if it does not exit
if cpm_var not in self._varmap:
from gurobipy import GRB
if isinstance(cpm_var, _BoolVarImpl):
revar = self.grb_model.addVar(vtype=GRB.BINARY, name=cpm_var.name)
elif isinstance(cpm_var, _IntVarImpl):
revar = self.grb_model.addVar(cpm_var.lb, cpm_var.ub, vtype=GRB.INTEGER, name=str(cpm_var))
else:
raise NotImplementedError("Not a known var {}".format(cpm_var))
self._varmap[cpm_var] = revar
# return from cache
return self._varmap[cpm_var]
[docs] def objective(self, expr, minimize=True):
"""
Post the given expression to the solver as objective to minimize/maximize
'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
"""
from gurobipy import GRB
# make objective function non-nested
(flat_obj, flat_cons) = flatten_objective(expr)
flat_obj = only_positive_bv_wsum(flat_obj) # remove negboolviews
get_variables(flat_obj, collect=self.user_vars) # add potentially created variables
self += flat_cons
# make objective function or variable and post
obj = self._make_numexpr(flat_obj)
if minimize:
self.grb_model.setObjective(obj, sense=GRB.MINIMIZE)
else:
self.grb_model.setObjective(obj, sense=GRB.MAXIMIZE)
[docs] def has_objective(self):
return self.grb_model.getObjective().size() != 0 # TODO: check if better way to do this...
def _make_numexpr(self, cpm_expr):
"""
Turns a numeric CPMpy 'flat' expression into a solver-specific
numeric expression
Used especially to post an expression as objective function
"""
import gurobipy as gp
if is_num(cpm_expr):
return cpm_expr
# decision variables, check in varmap
if isinstance(cpm_expr, _NumVarImpl): # _BoolVarImpl is subclass of _NumVarImpl
return self.solver_var(cpm_expr)
# sum
if cpm_expr.name == "sum":
return gp.quicksum(self.solver_vars(cpm_expr.args))
if cpm_expr.name == "sub":
a,b = self.solver_vars(cpm_expr.args)
return a - b
# wsum
if cpm_expr.name == "wsum":
return gp.quicksum(w * self.solver_var(var) for w, var in zip(*cpm_expr.args))
raise NotImplementedError("gurobi: Not a known supported numexpr {}".format(cpm_expr))
[docs] def add(self, cpm_expr_orig):
"""
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.
:param cpm_expr: CPMpy expression, or list thereof
:type cpm_expr: Expression or list of Expression
:return: self
"""
from gurobipy import GRB
# add new user vars to the set
get_variables(cpm_expr_orig, collect=self.user_vars)
# transform and post the constraints
for cpm_expr in self.transform(cpm_expr_orig):
# Comparisons: only numeric ones as 'only_implies()' has removed the '==' reification for Boolean expressions
# numexpr `comp` bvar|const
if isinstance(cpm_expr, Comparison):
lhs, rhs = cpm_expr.args
grbrhs = self.solver_var(rhs)
# Thanks to `only_numexpr_equality()` only supported comparisons should remain
if cpm_expr.name == '<=':
grblhs = self._make_numexpr(lhs)
self.grb_model.addLConstr(grblhs, GRB.LESS_EQUAL, grbrhs)
elif cpm_expr.name == '>=':
grblhs = self._make_numexpr(lhs)
self.grb_model.addLConstr(grblhs, GRB.GREATER_EQUAL, grbrhs)
elif cpm_expr.name == '==':
if isinstance(lhs, _NumVarImpl) \
or (isinstance(lhs, Operator) and (lhs.name == 'sum' or lhs.name == 'wsum' or lhs.name == "sub")):
# a BoundedLinearExpression LHS, special case, like in objective
grblhs = self._make_numexpr(lhs)
self.grb_model.addLConstr(grblhs, GRB.EQUAL, grbrhs)
elif lhs.name == 'mul':
assert len(lhs.args) == 2, "Gurobi only supports multiplication with 2 variables"
a, b = self.solver_vars(lhs.args)
self.grb_model.setParam("NonConvex", 2)
self.grb_model.addConstr(a * b == grbrhs)
elif lhs.name == 'div':
if not is_num(lhs.args[1]):
raise NotSupportedError(f"Gurobi only supports division by constants, but got {lhs.args[1]}")
a, b = self.solver_vars(lhs.args)
self.grb_model.addLConstr(a / b, GRB.EQUAL, grbrhs)
else:
# General constraints
# grbrhs should be a variable for gurobi in the subsequent, fake it
if is_num(grbrhs):
grbrhs = self.solver_var(intvar(lb=grbrhs, ub=grbrhs))
if lhs.name == 'min':
self.grb_model.addGenConstrMin(grbrhs, self.solver_vars(lhs.args))
elif lhs.name == 'max':
self.grb_model.addGenConstrMax(grbrhs, self.solver_vars(lhs.args))
elif lhs.name == 'abs':
self.grb_model.addGenConstrAbs(grbrhs, self.solver_var(lhs.args[0]))
elif lhs.name == 'pow':
x, a = self.solver_vars(lhs.args)
self.grb_model.addGenConstrPow(x, grbrhs, a)
else:
raise NotImplementedError(
"Not a known supported gurobi comparison '{}' {}".format(lhs.name, cpm_expr))
else:
raise NotImplementedError(
"Not a known supported gurobi comparison '{}' {}".format(lhs.name, cpm_expr))
elif isinstance(cpm_expr, Operator) and cpm_expr.name == "->":
# Indicator constraints
# Take form bvar -> sum(x,y,z) >= rvar
cond, sub_expr = cpm_expr.args
assert isinstance(cond, _BoolVarImpl), f"Implication constraint {cpm_expr} must have BoolVar as lhs"
assert isinstance(sub_expr, Comparison), "Implication must have linear constraints on right hand side"
if isinstance(cond, NegBoolView):
cond, bool_val = self.solver_var(cond._bv), False
else:
cond, bool_val = self.solver_var(cond), True
lhs, rhs = sub_expr.args
if isinstance(lhs, _NumVarImpl) or lhs.name == "sum" or lhs.name == "wsum":
lin_expr = self._make_numexpr(lhs)
else:
raise Exception(f"Unknown linear expression {lhs} on right side of indicator constraint: {cpm_expr}")
if sub_expr.name == "<=":
self.grb_model.addGenConstrIndicator(cond, bool_val, lin_expr, GRB.LESS_EQUAL, self.solver_var(rhs))
elif sub_expr.name == ">=":
self.grb_model.addGenConstrIndicator(cond, bool_val, lin_expr, GRB.GREATER_EQUAL, self.solver_var(rhs))
elif sub_expr.name == "==":
self.grb_model.addGenConstrIndicator(cond, bool_val, lin_expr, GRB.EQUAL, self.solver_var(rhs))
else:
raise Exception(f"Unknown linear expression {sub_expr} name")
# True or False
elif isinstance(cpm_expr, BoolVal):
self.grb_model.addConstr(cpm_expr.args[0])
# a direct constraint, pass to solver
elif isinstance(cpm_expr, DirectConstraint):
cpm_expr.callSolver(self, self.grb_model)
else:
raise NotImplementedError(cpm_expr) # if you reach this... please report on github
return self
__add__ = add # avoid redirect in superclass
[docs] def solveAll(self, display=None, time_limit=None, solution_limit=None, call_from_model=False, **kwargs):
"""
Compute all solutions and optionally display the solutions.
This is the generic implementation, solvers can overwrite this with
a more efficient native implementation
Arguments:
display: either a list of CPMpy expressions, OR a callback function, called with the variables after value-mapping
default/None: nothing displayed
time_limit: stop after this many seconds (default: None)
solution_limit: stop after this many solutions (default: None)
call_from_model: whether the method is called from a CPMpy Model instance or not
any other keyword argument
Returns: number of solutions found
"""
from gurobipy import GRB
if time_limit is not None:
self.grb_model.setParam("TimeLimit", time_limit)
if solution_limit is None:
raise Exception(
"Gurobi does not support searching for all solutions. If you really need all solutions, "
"try setting solution limit to a large number")
# Force gurobi to keep searching in the tree for optimal solutions
sa_kwargs = {"PoolSearchMode":2, "PoolSolutions":solution_limit}
# solve the model
self.solve(time_limit=time_limit, **sa_kwargs, **kwargs)
optimal_val = None
solution_count = self.grb_model.SolCount
opt_sol_count = 0
# clear user vars if no solution found
if solution_count == 0:
self.objective_value_ = None
for var in self.user_vars:
var._value = None
for i in range(solution_count):
# Specify which solution to query
self.grb_model.setParam("SolutionNumber", i)
sol_obj_val = self.grb_model.PoolObjVal
if optimal_val is None:
optimal_val = sol_obj_val
if optimal_val is not None:
# sub-optimal solutions
if sol_obj_val != optimal_val:
break
opt_sol_count += 1
# Translate solution to variables
for cpm_var in self.user_vars:
solver_val = self.solver_var(cpm_var).Xn
if cpm_var.is_bool():
cpm_var._value = solver_val >= 0.5
else:
cpm_var._value = int(solver_val)
# Translate objective
if self.has_objective():
self.objective_value_ = self.grb_model.PoolObjVal
if display is not None:
if isinstance(display, Expression):
print(argval(display))
elif isinstance(display, list):
print(argvals(display))
else:
display() # callback
# Reset pool search mode to default
self.grb_model.setParam("PoolSearchMode", 0)
if opt_sol_count:
if opt_sol_count == solution_limit:
self.cpm_status.exitstatus = ExitStatus.FEASIBLE
else:
grb_status = self.grb_model.Status
if grb_status == GRB.TIME_LIMIT: # reached time limit
self.cpm_status.exitstatus = ExitStatus.FEASIBLE
else: # found all solutions
self.cpm_status.exitstatus = ExitStatus.OPTIMAL
# if unsat or timout with no solution, .solve() will have already set the state accordingly (so nothing to update)
return opt_sol_count