import warnings
from typing import Any, List
import numpy as np
from cvxpy.atoms import EXP_ATOMS, NONPOS_ATOMS, PSD_ATOMS, SOC_ATOMS
from cvxpy.constraints import (PSD, SOC, Equality, ExpCone, Inequality, NonNeg,
NonPos, PowCone3D, Zero,)
from cvxpy.error import DCPError, DGPError, DPPError, SolverError
from cvxpy.problems.objective import Maximize
from cvxpy.reductions.chain import Chain
from cvxpy.reductions.complex2real import complex2real
from cvxpy.reductions.cone2cone.exotic2common import (EXOTIC_CONES,
Exotic2Common,)
from cvxpy.reductions.cvx_attr2constr import CvxAttr2Constr
from cvxpy.reductions.dcp2cone.cone_matrix_stuffing import ConeMatrixStuffing
from cvxpy.reductions.dcp2cone.dcp2cone import Dcp2Cone
from cvxpy.reductions.dgp2dcp.dgp2dcp import Dgp2Dcp
from cvxpy.reductions.eval_params import EvalParams
from cvxpy.reductions.flip_objective import FlipObjective
from cvxpy.reductions.qp2quad_form import qp2symbolic_qp
from cvxpy.reductions.qp2quad_form.qp_matrix_stuffing import QpMatrixStuffing
from cvxpy.reductions.solvers import defines as slv_def
from cvxpy.reductions.solvers.constant_solver import ConstantSolver
from cvxpy.reductions.solvers.solver import Solver
from cvxpy.settings import PARAM_THRESHOLD
from cvxpy.utilities.debug_tools import build_non_disciplined_error_msg
def _is_lp(self):
"""Is problem a linear program?
"""
for c in self.constraints:
if not (isinstance(c, (Equality, Zero)) or c.args[0].is_pwl()):
return False
for var in self.variables():
if var.is_psd() or var.is_nsd():
return False
return (self.is_dcp() and self.objective.args[0].is_pwl())
def _solve_as_qp(problem, candidates):
if _is_lp(problem) and \
[s for s in candidates['conic_solvers'] if s not in candidates['qp_solvers']]:
# OSQP can take many iterations for LPs; use a conic solver instead
# GUROBI and CPLEX QP/LP interfaces are more efficient
# -> Use them instead of conic if applicable.
return False
return candidates['qp_solvers'] and qp2symbolic_qp.accepts(problem)
def _reductions_for_problem_class(problem, candidates, gp: bool = False) -> List[Any]:
"""
Builds a chain that rewrites a problem into an intermediate
representation suitable for numeric reductions.
Parameters
----------
problem : Problem
The problem for which to build a chain.
candidates : dict
Dictionary of candidate solvers divided in qp_solvers
and conic_solvers.
gp : bool
If True, the problem is parsed as a Disciplined Geometric Program
instead of as a Disciplined Convex Program.
Returns
-------
list of Reduction objects
A list of reductions that can be used to convert the problem to an
intermediate form.
Raises
------
DCPError
Raised if the problem is not DCP and `gp` is False.
DGPError
Raised if the problem is not DGP and `gp` is True.
"""
reductions = []
# TODO Handle boolean constraints.
if complex2real.accepts(problem):
reductions += [complex2real.Complex2Real()]
if gp:
reductions += [Dgp2Dcp()]
if not gp and not problem.is_dcp():
append = build_non_disciplined_error_msg(problem, 'DCP')
if problem.is_dgp():
append += ("\nHowever, the problem does follow DGP rules. "
"Consider calling solve() with `gp=True`.")
elif problem.is_dqcp():
append += ("\nHowever, the problem does follow DQCP rules. "
"Consider calling solve() with `qcp=True`.")
raise DCPError(
"Problem does not follow DCP rules. Specifically:\n" + append)
elif gp and not problem.is_dgp():
append = build_non_disciplined_error_msg(problem, 'DGP')
if problem.is_dcp():
append += ("\nHowever, the problem does follow DCP rules. "
"Consider calling solve() with `gp=False`.")
elif problem.is_dqcp():
append += ("\nHowever, the problem does follow DQCP rules. "
"Consider calling solve() with `qcp=True`.")
raise DGPError("Problem does not follow DGP rules." + append)
# Dcp2Cone and Qp2SymbolicQp require problems to minimize their objectives.
if type(problem.objective) == Maximize:
reductions += [FlipObjective()]
if _solve_as_qp(problem, candidates):
reductions += [CvxAttr2Constr(), qp2symbolic_qp.Qp2SymbolicQp()]
else:
# Canonicalize it to conic problem.
if not candidates['conic_solvers']:
raise SolverError("Problem could not be reduced to a QP, and no "
"conic solvers exist among candidate solvers "
"(%s)." % candidates)
else:
reductions += [Dcp2Cone(), CvxAttr2Constr()]
return reductions
def construct_solving_chain(problem, candidates,
gp: bool = False,
enforce_dpp: bool = False,
ignore_dpp: bool = False) -> "SolvingChain":
"""Build a reduction chain from a problem to an installed solver.
Note that if the supplied problem has 0 variables, then the solver
parameter will be ignored.
Parameters
----------
problem : Problem
The problem for which to build a chain.
candidates : dict
Dictionary of candidate solvers divided in qp_solvers
and conic_solvers.
gp : bool
If True, the problem is parsed as a Disciplined Geometric Program
instead of as a Disciplined Convex Program.
enforce_dpp : bool, optional
When True, a DPPError will be thrown when trying to parse a non-DPP
problem (instead of just a warning). Defaults to False.
ignore_dpp : bool, optional
When True, DPP problems will be treated as non-DPP,
which may speed up compilation. Defaults to False.
Returns
-------
SolvingChain
A SolvingChain that can be used to solve the problem.
Raises
------
SolverError
Raised if no suitable solver exists among the installed solvers, or
if the target solver is not installed.
"""
if len(problem.variables()) == 0:
return SolvingChain(reductions=[ConstantSolver()])
reductions = _reductions_for_problem_class(problem, candidates, gp)
# Process DPP status of the problem.
dpp_context = 'dcp' if not gp else 'dgp'
dpp_error_msg = (
"You are solving a parameterized problem that is not DPP. "
"Because the problem is not DPP, subsequent solves will not be "
"faster than the first one. For more information, see the "
"documentation on Discplined Parametrized Programming, at\n"
"\thttps://www.cvxpy.org/tutorial/advanced/index.html#"
"disciplined-parametrized-programming")
if ignore_dpp or not problem.is_dpp(dpp_context):
# No warning for ignore_dpp.
if ignore_dpp:
reductions = [EvalParams()] + reductions
elif not enforce_dpp:
warnings.warn(dpp_error_msg)
reductions = [EvalParams()] + reductions
else:
raise DPPError(dpp_error_msg)
elif any(param.is_complex() for param in problem.parameters()):
reductions = [EvalParams()] + reductions
else: # Compilation with DPP.
n_parameters = sum(np.prod(param.shape) for param in problem.parameters())
if n_parameters >= PARAM_THRESHOLD:
warnings.warn(
"Your problem has too many parameters for efficient DPP "
"compilation. We suggest setting 'ignore_dpp = True'."
)
# Conclude with matrix stuffing; choose one of the following paths:
# (1) QpMatrixStuffing --> [a QpSolver],
# (2) ConeMatrixStuffing --> [a ConicSolver]
if _solve_as_qp(problem, candidates):
# Canonicalize as a QP
solver = candidates['qp_solvers'][0]
solver_instance = slv_def.SOLVER_MAP_QP[solver]
reductions += [QpMatrixStuffing(),
solver_instance]
return SolvingChain(reductions=reductions)
# Canonicalize as a cone program
if not candidates['conic_solvers']:
raise SolverError("Problem could not be reduced to a QP, and no "
"conic solvers exist among candidate solvers "
"(%s)." % candidates)
constr_types = set()
# ^ We use constr_types to infer an incomplete list of cones that
# the solver will need after canonicalization.
for c in problem.constraints:
constr_types.add(type(c))
ex_cos = [ct for ct in constr_types if ct in EXOTIC_CONES]
# ^ The way we populate "ex_cos" will need to change if and when
# we have atoms that require exotic cones.
for co in ex_cos:
sim_cos = EXOTIC_CONES[co] # get the set of required simple cones
constr_types.update(sim_cos)
constr_types.remove(co)
# We now go over individual elementary cones support by CVXPY (
# SOC, ExpCone, NonNeg, Zero, PSD, PowCone3D) and check if
# they've appeared in constr_types or if the problem has an atom
# requiring that cone.
cones = []
atoms = problem.atoms()
if SOC in constr_types or any(atom in SOC_ATOMS for atom in atoms):
cones.append(SOC)
if ExpCone in constr_types or any(atom in EXP_ATOMS for atom in atoms):
cones.append(ExpCone)
if any(t in constr_types for t in [Inequality, NonPos, NonNeg]) \
or any(atom in NONPOS_ATOMS for atom in atoms):
cones.append(NonNeg)
if Equality in constr_types or Zero in constr_types:
cones.append(Zero)
if PSD in constr_types \
or any(atom in PSD_ATOMS for atom in atoms) \
or any(v.is_psd() or v.is_nsd() for v in problem.variables()):
cones.append(PSD)
if PowCone3D in constr_types:
# if we add in atoms that specifically use the 3D power cone
# (rather than the ND power cone), then we'll need to check
# for those atoms here as well.
cones.append(PowCone3D)
# Here, we make use of the observation that canonicalization only
# increases the number of constraints in our problem.
has_constr = len(cones) > 0 or len(problem.constraints) > 0
for solver in candidates['conic_solvers']:
solver_instance = slv_def.SOLVER_MAP_CONIC[solver]
if (all(c in solver_instance.SUPPORTED_CONSTRAINTS for c in cones)
and (has_constr or not solver_instance.REQUIRES_CONSTR)):
if ex_cos:
reductions.append(Exotic2Common())
reductions += [ConeMatrixStuffing(), solver_instance]
return SolvingChain(reductions=reductions)
raise SolverError("Either candidate conic solvers (%s) do not support the "
"cones output by the problem (%s), or there are not "
"enough constraints in the problem." % (
candidates['conic_solvers'],
", ".join([cone.__name__ for cone in cones])))
[docs]class SolvingChain(Chain):
"""A reduction chain that ends with a solver.
Parameters
----------
reductions : list[Reduction]
A list of reductions. The last reduction in the list must be a solver
instance.
Attributes
----------
reductions : list[Reduction]
A list of reductions.
solver : Solver
The solver, i.e., reductions[-1].
"""
def __init__(self, problem=None, reductions=None) -> None:
super(SolvingChain, self).__init__(problem=problem,
reductions=reductions)
if not isinstance(self.reductions[-1], Solver):
raise ValueError("Solving chains must terminate with a Solver.")
self.solver = self.reductions[-1]
[docs] def prepend(self, chain) -> "SolvingChain":
"""
Create and return a new SolvingChain by concatenating
chain with this instance.
"""
return SolvingChain(reductions=chain.reductions + self.reductions)
[docs] def solve(self, problem, warm_start: bool, verbose: bool, solver_opts):
"""Solves the problem by applying the chain.
Applies each reduction in the chain to the problem, solves it,
and then inverts the chain to return a solution of the supplied
problem.
Parameters
----------
problem : Problem
The problem to solve.
warm_start : bool
Whether to warm start the solver.
verbose : bool
Whether to enable solver verbosity.
solver_opts : dict
Solver specific options.
Returns
-------
solution : Solution
A solution to the problem.
"""
data, inverse_data = self.apply(problem)
solution = self.solver.solve_via_data(data, warm_start,
verbose, solver_opts)
return self.invert(solution, inverse_data)
[docs] def solve_via_data(self, problem, data, warm_start: bool = False, verbose: bool = False,
solver_opts={}):
"""Solves the problem using the data output by the an apply invocation.
The semantics are:
.. code :: python
data, inverse_data = solving_chain.apply(problem)
solution = solving_chain.invert(solver_chain.solve_via_data(data, ...))
which is equivalent to writing
.. code :: python
solution = solving_chain.solve(problem, ...)
Parameters
----------
problem : Problem
The problem to solve.
data : map
Data for the solver.
warm_start : bool
Whether to warm start the solver.
verbose : bool
Whether to enable solver verbosity.
solver_opts : dict
Solver specific options.
Returns
-------
raw solver solution
The information returned by the solver; this is not necessarily
a Solution object.
"""
return self.solver.solve_via_data(data, warm_start, verbose,
solver_opts, problem._solver_cache)
