Coverage for picos/constraints/constraint.py: 86.75%
166 statements
« prev ^ index » next coverage.py v6.5.0, created at 2023-03-26 07:46 +0000
« prev ^ index » next coverage.py v6.5.0, created at 2023-03-26 07:46 +0000
1# ------------------------------------------------------------------------------
2# Copyright (C) 2018 Maximilian Stahlberg
3#
4# This file is part of PICOS.
5#
6# PICOS is free software: you can redistribute it and/or modify it under the
7# terms of the GNU General Public License as published by the Free Software
8# Foundation, either version 3 of the License, or (at your option) any later
9# version.
10#
11# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY
12# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
13# A PARTICULAR PURPOSE. See the GNU General Public License for more details.
14#
15# You should have received a copy of the GNU General Public License along with
16# this program. If not, see <http://www.gnu.org/licenses/>.
17# ------------------------------------------------------------------------------
19"""Backend for constraint type implementations."""
21import random
22import threading
23from abc import ABC, abstractmethod
24from copy import copy as pycopy
26import cvxopt
28from .. import glyphs
29from ..apidoc import api_end, api_start
30from ..caching import cached_property, empty_cache
31from ..containers import DetailedType
33_API_START = api_start(globals())
34# -------------------------------
37# The constraint IDs start at a random value to prevent a clash if constraints
38# are are pickled and loaded in another python session.
39_LAST_CONSTRAINT_ID = int(random.getrandbits(31))
41# A lock for _LAST_CONSTRAINT_ID, if the user threads to create constraints.
42_CONSTRAINT_ID_LOCK = threading.Lock()
45def _make_constraint_id():
46 """Create a unique ID for a new constraint."""
47 with _CONSTRAINT_ID_LOCK:
48 global _LAST_CONSTRAINT_ID
49 _LAST_CONSTRAINT_ID += 1
50 return _LAST_CONSTRAINT_ID
53class ConstraintType(DetailedType):
54 """Container for a pair of constraint class type and constraint subtype."""
56 pass
59class Constraint(ABC):
60 """Abstract base class for optimization constraints.
62 Implementations
64 * need to implement at least the abstract methods ``_str``,
65 ``_expression_names``, and ``_get_slack``,
66 * need to implement ``_get_size``, unless duals are not supported, and
67 * are supposed to call :meth:`Constraint.__init__` from within their own
68 implementation of ``__init__``.
69 """
71 LE = "<"
72 GE = ">"
73 EQ = "="
75 def __init__(self, typeTerm, customString=None, printSize=False):
76 """Perform basic initialization for :class:`Constraint` instances.
78 :param str typeTerm: Short string denoting the constraint type.
79 :param str customString: Optional string description.
80 :param bool printSize: Whether to include the constraint's shape in its
81 representation string.
82 """
83 self.typeTerm = typeTerm
84 self.customString = customString
85 self.printSize = printSize
87 self._id = _make_constraint_id()
89 self.name = None
90 self._dual = None
92 @property
93 def type(self):
94 """Detailed type of the constraint.
96 The detailed type of the constraint, which is suffcient to predict the
97 outcome (detailed types and quantities of auxilary variables and
98 constraints) of any constraint conversion.
99 """
100 return ConstraintType(self.__class__, self._subtype())
102 subtype = property(lambda self: self._subtype())
104 @classmethod
105 def make_type(cls, *args, **kwargs):
106 """Create a detailed constraint type from subtype parameters."""
107 return ConstraintType(cls, cls.Subtype(*args, **kwargs))
109 @abstractmethod
110 def _subtype(self):
111 """Subtype of the constraint.
113 :returns: A hashable object that, together with the constraint class,
114 is sufficient to predict the outcome (detailed types and quantities
115 of auxilary variables and constraints) of any constraint conversion.
116 """
117 pass
119 @classmethod
120 @abstractmethod
121 def _cost(cls, subtype):
122 r"""Report an estimate number of real constraint matrix rows occupied.
124 Given the subtype of a constraint, returns an estimate on the number of
125 rows that a constraint with this subtype would occupy in the constraint
126 matrix of a (hypothetical) solver that supports direct input of such a
127 constraint.
129 Some conventions:
131 - For a conic constraint, this is the cone's dimensionality.
132 - For a (complex) affine equality :math:`A = B`, this is the number of
133 elements in the matrix :math:`A - B` (times two).
134 - For a constraint that poses a bound on a scalar function on an
135 :math:`n`-dimensional vector space, this is :math:`n + 1` (:math:`1`
136 for the affine bound).
137 - In particular, a bound on a function of symmetric (hermitian) matrices
138 occupies :math:`\frac{n(n + 1)}{2} + 1` (:math:`n^2 + 1`) rows.
139 - For a quadratic constraint, this is the number of coefficients in the
140 simplified quadratic form, plus one (for the affine part).
141 """
142 pass
144 def __hash__(self):
145 """Return the unique ID."""
146 return self._id
148 def __eq__(self, other):
149 """Whether the unique IDs equal."""
150 return self._id == other._id
152 def __repr__(self):
153 if self.printSize:
154 return glyphs.repr2("{} {} Constraint".format(
155 glyphs.size(*self.size), self.typeTerm), self.__str__())
156 else:
157 return glyphs.repr2("{} Constraint".format(self.typeTerm),
158 self.__str__())
160 def __str__(self):
161 return "{}{}".format(
162 self.customString if self.customString else self._str(),
163 " ({})".format(self.name) if self.name else "")
165 def __len__(self):
166 """Return number of scalar Lagrange dual variables."""
167 return self.size[0] * self.size[1]
169 @property
170 def id(self):
171 """The unique ID of the constraint, assigned at creation.
173 The ID is kept when the constraint is copied via
174 :meth:`replace_mutables`, so that the copy can be identified with the
175 original despite pointing to different expressions and mutable objects.
176 """
177 return self._id
179 @abstractmethod
180 def _expression_names(self):
181 """Attribute names of the expressions stored in the constraint."""
182 pass
184 @abstractmethod
185 def _str(self):
186 """Algebraic representation of the constraint."""
187 pass
189 def _get_size(self):
190 """Langrange dual variable shape.
192 The dimensionality of the constraint, more precisely the dimensionality
193 of its Lagrange dual variable, as a pair.
194 """
195 # TODO: This seems to be associated with the size of the slack vector
196 # as well (the test bench checks against this) and therefor should
197 # probably be abstract as well.
198 raise NotImplementedError(
199 "{} does not define a constraint (dual value) dimensionality."
200 .format(self.__class__.__name__))
202 @abstractmethod
203 def _get_slack(self):
204 """Value of a slack variable or of the negative constraint violation.
206 A negative value whose absolute value corresponds to the amount of
207 violation, if the constraint is violated, or a non-negative value that
208 corresponds to the value of a slack variable, otherwise.
209 """
210 pass
212 def _wrap_get_slack(self):
213 """Convert a scalar slack value to float.
215 A wrapper retrieving the slack in a consistent manner: If it is a scalar
216 value, it is returned as a float, otherwise as a
217 :class:`CVXOPT matrix <cvxopt.matrix>`.
218 """
219 slack = self._get_slack()
221 if isinstance(slack, float):
222 return slack
224 assert isinstance(slack, cvxopt.matrix), "Constraints need to return " \
225 "the slack as either a float or a CVXOPT matrix."
227 if slack.size == (1, 1):
228 return float(slack[0])
229 else:
230 return slack
232 def _get_dual(self):
233 return self._dual
235 def _set_dual(self, value):
236 """Store a constraint's dual value.
238 Stores a dual solution value for the dual variable corresponding to the
239 constraint in a consistent manner.
241 Duals for multidmensional constraints are stored as a CVXOPT (sparse)
242 matrix while duals for scalar constraints are stored as a Python scalar.
243 """
244 from ..expressions.data import load_data
246 if value is None:
247 self._dual = None
248 else:
249 dual = load_data(value, self.size)[0]
250 self._dual = dual[0] if dual.size == (1, 1) else dual
252 size = property(lambda self: self._get_size(), doc=_get_size.__doc__)
253 slack = property(lambda self: self._wrap_get_slack(),
254 doc=_get_slack.__doc__)
255 dual = property(lambda self: self._get_dual(), _set_dual)
256 """Value of the constraint's Lagrange dual variable."""
258 def delete(self):
259 """Raise a :exc:`NotImplementedError`.
261 Formerly this would remove the constraint from the single problem it is
262 assigned to, if any.
264 .. deprecated:: 2.0
266 Both variables and constraints have been decoupled from problems:
267 Both may safely appear in multiple problems but at the same time
268 they do not know which problems they were added to. To remove a
269 constraint from a problem, you have to call its
270 :meth:`~picos.modeling.problem.Problem.remove_constraint` method.
271 """
272 raise NotImplementedError("Telling a constraint to remove itself from "
273 "problems is not possible anymore, use Problem.remove_constraint "
274 "on selected problems instead.")
276 # TODO: Solve this with inspection instead of _expression_names?
277 # TODO: Is this even needed for anything apart from mutables and
278 # replace_mutables? If not, maybe just implement those two with
279 # every constraint just like for expressions?
280 # Idea: Could add a MutableRegister abstract base class used by Expression
281 # and Constraint.
282 @property
283 def expressions(self):
284 """Yield expressions stored with the constraint."""
285 for name in self._expression_names():
286 yield getattr(self, name)
288 @cached_property
289 def mutables(self):
290 """All mutables referenced by the constraint."""
291 mtbs = frozenset()
292 for expression in self.expressions:
293 mtbs = mtbs.union(expression.mutables)
294 return mtbs
296 @cached_property
297 def variables(self):
298 """All decision variables referenced by the constraint."""
299 from ..expressions.variables import BaseVariable
301 return frozenset(mutable for mutable in self.mutables
302 if isinstance(mutable, BaseVariable))
304 @cached_property
305 def parameters(self):
306 """All parameters referenced by the constraint."""
307 from ..expressions.variables import BaseVariable
309 return frozenset(mutable for mutable in self.mutables
310 if not isinstance(mutable, BaseVariable))
312 def replace_mutables(self, new_mutables):
313 """Make the constraint concern a different set of mutables.
315 See :meth:`~.expression.Expression.replace_mutables` for more.
316 """
317 the_copy = pycopy(self)
319 # Clear the cache of the copy as it can reference old mutables.
320 empty_cache(the_copy)
322 # Rewrite expressions.
323 for name in the_copy._expression_names():
324 expression = getattr(self, name)
325 new_expression = expression.replace_mutables(new_mutables)
326 setattr(the_copy, name, new_expression)
328 # HACK: Delete a custom string because it can contain old mutable names.
329 # In particular Norm uses it when creating a SOCConstraint.
330 # TODO: Get rid of custom strings.
331 the_copy.customString = None
333 # TODO: Reset a dual value assigned to the constraint?
334 # theCopy._dual = None
336 return the_copy
338 # TODO: Evaluate uses of this method.
339 def constring(self):
340 """Return an algebraic string representation of the constraint."""
341 return self._str()
343 # TODO: Re-implement pretty printing for problems.
344 def keyconstring(self):
345 """Return the regular string representation."""
346 return self.__str__()
348 def _assure_lhs_rhs_relation(self):
349 if not hasattr(self, "relation") or not hasattr(self, "lhs") \
350 or not hasattr(self, "rhs"):
351 raise TypeError("{} does not explicitly define a relation "
352 "between a left hand side and a right hand side expression."
353 .format(self.__class__.__name__))
355 def is_equality(self):
356 """Whether the constraints states an equality."""
357 self._assure_lhs_rhs_relation()
358 return self.relation == self.EQ
360 def is_inequality(self):
361 """Whether the constraints states an inequality."""
362 self._assure_lhs_rhs_relation()
363 return self.relation != self.EQ
365 def is_increasing(self):
366 """Whether the left side is posed smaller or equal than the right."""
367 self._assure_lhs_rhs_relation()
368 return self.relation == self.LE
370 def is_decreasing(self):
371 """Whether the left side is posed greater or equal than the right."""
372 self._assure_lhs_rhs_relation()
373 return self.relation == self.GE
376class ConicConstraint(Constraint):
377 """Base class for constraints with an immediate conic representation."""
379 @property
380 @abstractmethod
381 def conic_membership_form(self):
382 r"""The constraint in conic membership form.
384 For a conic constraint
385 :math:`Ax \succeq_C b \Leftrightarrow Ax - b \in C` this is the pair
386 :math:`(Ax - b, C)` where :math:`Ax - b` is an affine expression and
387 :math:`C` a basic cone supported by PICOS.
388 """
389 pass
391 @cached_property
392 def conic_standard_form(self):
393 r"""The constraint in conic standard form.
395 For a conic constraint :math:`Ax \succeq_C b` this is the triple
396 :math:`(Ax, b, C)` where :math:`Ax` is a linear expression, :math:`b` is
397 a constant, and :math:`C` a basic cone supported by PICOS.
398 """
399 member, cone = self.conic_membership_form
400 return member.lin, -member.cst, cone
402 @cached_property
403 def inverse_conic_standard_form(self):
404 r"""The constraint in inverse conic standard form.
406 For a conic constraint
407 :math:`Ax \succeq_C b \Leftrightarrow -Ax \preceq_C -b` this is the
408 triple :math:`(-Ax, -b, C)` where :math:`Ax` is a linear expression,
409 :math:`b` is a constant, and :math:`C` a basic cone supported by PICOS.
410 """
411 member, cone = self.conic_membership_form
412 return -member.lin, member.cst, cone
415class ConstraintConversion(ABC):
416 """Recipe for conversion from one constraint to a set of other constraints.
418 Implementations of this class are defined within the class body of a
419 Constraint implementation to tell PICOS' reformulation framework how that
420 constraint can be reformulated into a number of other constraints and
421 auxiliary variables.
423 Implementation class names must end in ``Conversion``, and in particular may
424 be called just ``Conversion``. If for instance
425 :class:`AbsoluteValueConstraint <.con_absolute.AbsoluteValueConstraint>`
426 defines :class:`AffineConversion
427 <.con_absolute.AbsoluteValueConstraint.AffineConversion>`, then the
428 reformulation will be coined ``AbsoluteValueToAffineReformulation``. If the
429 conversions was just named ``Conversion``, the result would be a class named
430 ``AbsoluteValueReformulation``.
431 """
433 @classmethod
434 @abstractmethod
435 def predict(cls, subtype, options):
436 """Predict the outcome of a constraint conversion.
438 :param object subtype: A hashable object as could be returned by the
439 ``_subtype`` method of the parent constraint implementation.
440 :param ~picos.Options options: Solution options to assume used.
441 :yields: Records to be added to a problem footprint when an instance of
442 the parent constraint with the given subtype is converted according
443 to this conversion.
444 """
445 pass
447 # TODO: Make this yield variables and constraints instad of returning a
448 # Problem instance (this was not possible with the old expressions).
449 @classmethod
450 @abstractmethod
451 def convert(cls, constraint, options):
452 """Convert a given constraint.
454 Returns a temporary problem instance that contains auxilary constraints
455 and variables replacing the given constraint.
456 """
457 pass
459 @classmethod
460 def dual(cls, auxVarPrimals, auxConDuals, options):
461 """Convert back the dual value of a constraint that was converted.
463 Given a mapping of auxilary variable names (as named in :meth:`convert`)
464 to primals and a list of auxilary constraint duals (in the order as the
465 constraints were added in :meth:`convert`), returns a dual value for the
466 converted constraint.
468 :raises NotImplementedError: When dual format not decided upon or not
469 known. This will be caught by the reformulation's backward method.
470 """
471 raise NotImplementedError(
472 "{} does not describe how to convert back the dual.".format(
473 cls.__qualname__ if hasattr(cls, "__qualname__") else cls.__name__))
475 def __init__(self):
476 """Raise a :exc:`TypeError` on instanciation."""
477 raise TypeError("Constraint conversion classes are not supposed to be "
478 "instanciated.")
481# --------------------------------------
482__all__ = api_end(_API_START, globals())