Coverage for picos/modeling/footprint.py: 75.72%
173 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) 2019-2020 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"""Optimization problem description classes.
21This module implements a footprint of a single problem, storing number and types
22of expressions and constraints, and the specification of a problem class.
23"""
25import math
26from inspect import isclass
27from itertools import chain
29from .. import constraints, expressions, glyphs
30from ..apidoc import api_end, api_start
31from ..caching import cached_property
32from ..containers import RecordTree
33from ..expressions import variables
34# from .options import OPTION_OBJS, Options # Circular import.
36_API_START = api_start(globals())
37# -------------------------------
40# Constants used by both Footprint and Specification.
41_OBJS = tuple(exp for exp in expressions.__dict__.values() if isclass(exp)
42 and issubclass(exp, expressions.Expression)
43 and exp != expressions.Expression) # ALl proper Expression subclasses.
44_DIRS = ("find", "min", "max")
45_VARS = tuple(var for var in expressions.__dict__.values() if isclass(var)
46 and issubclass(var, expressions.BaseVariable)
47 and var != expressions.BaseVariable) # ALl proper BaseVariable subclasses.
48_CONS = tuple(con for con in constraints.__dict__.values() if isclass(con)
49 and issubclass(con, constraints.Constraint)
50 and con != constraints.Constraint) # All proper Constraint subclasses.
51# _OPTS = tuple(option.name for option in OPTION_OBJS) # All option names.
54class Footprint(RecordTree):
55 """Statistics on an optimization problem."""
57 _ADD_VALUES = [("var",), ("con",)]
59 def __init__(self, recordsOrDict):
60 """Construct a :class:`Footprint` from raw data.
62 See :class:`picos.containers.RecordTree.__init__`. The ``addValues``
63 argument is fixed; only variable and constraint paths are added.
64 """
65 super(Footprint, self).__init__(recordsOrDict, self._ADD_VALUES)
67 # Sanity check records.
68 for path, value in self.items:
69 pathLen = len(path)
70 category = path[0] if pathLen > 0 else None
71 suptype = path[1] if pathLen > 1 else None
72 subtype = path[2] if pathLen > 2 else None
74 if category == "dir":
75 if pathLen == 2 and suptype in _DIRS and value is None:
76 continue
77 elif category == "obj":
78 if pathLen == 3 and suptype in _OBJS \
79 and isinstance(subtype, suptype.Subtype) and value is None:
80 continue
81 elif category == "var":
82 if pathLen == 3 and suptype in _VARS \
83 and isinstance(subtype, suptype.VarSubtype) \
84 and isinstance(value, int):
85 continue
86 elif category == "con":
87 if pathLen == 3 and suptype in _CONS \
88 and isinstance(subtype, suptype.Subtype) \
89 and isinstance(value, int):
90 continue
91 elif category == "opt":
92 # if pathLen == 2 and suptype in _OPTS:
93 if pathLen == 2 and isinstance(suptype, str):
94 continue
96 raise ValueError("Invalid problem footprint record: {} = {}."
97 .format(path, value))
99 # Sanity check for inconsistent duplicates or missing fields.
100 if len(self["dir"]) != 1:
101 raise TypeError("Not exactly one optimization direction defined for"
102 " a problem footprint (but {}).".format(len(self["dir"])))
103 elif len(self["obj"]) != 1:
104 raise TypeError("Not exactly one objective function defined for a "
105 "problem footprint (but {}).".format(len(self["obj"])))
107 def updated(self, recordsOrDict):
108 """Override :class:`~picos.containers.RecordTree.updated`.
110 This method, just like :meth:`__init__`, does not take the additional
111 ``addValues`` argument.
112 """
113 return self.__class__(
114 chain(self.records, self._record_iterator(recordsOrDict)))
116 @property
117 def direction(self):
118 """Objective function optimization direction."""
119 return next(self["dir"].paths)[0]
121 @property
122 def objective(self):
123 """Detailed type of the objective function."""
124 clstype, subtype = next(self["obj"].paths)
125 return expressions.ExpressionType(clstype, subtype)
127 @cached_property
128 def variables(self):
129 """A dictionary mapping detailed variable types to their quantity."""
130 return {variables.VariableType(*ts): n
131 for ts, n in self.get("var").items}
133 @cached_property
134 def constraints(self):
135 """A dictionary mapping detailed constraint types to their quantity."""
136 return {constraints.ConstraintType(*ts): n
137 for ts, n in self.get("con").items}
139 @cached_property
140 def nondefault_options(self):
141 """A dictionary mapping option names to their nondefault values.
143 .. warning::
145 This property is cached for performance reasons, do not modify any
146 mutable option value (make a deep copy instead)!
147 """
148 return {path[0]: value for path, value in self.get("opt").items}
150 @cached_property
151 def options(self):
152 """An :class:`~.options.Options` object.
154 .. warning::
156 This property is cached for performance reasons, do not modify the
157 returned object (make a :meth:`~.options.Options.copy` instead)!
158 """
159 from .options import Options
160 return Options(**self.nondefault_options)
162 @cached_property
163 def integer(self):
164 """Whether an integral variable type is present."""
165 return any(("var", vtype) in self for vtype in (
166 expressions.BinaryVariable, expressions.IntegerVariable))
168 @property
169 def continuous(self):
170 """Whether no integral variable type is present."""
171 return not self.integer
173 @cached_property
174 def nonconvex_quadratic_objective(self):
175 """Whether the problem has a nonconvex quadratic objective."""
176 if issubclass(self.objective.clstype, expressions.QuadraticExpression):
177 direction = self.direction
178 subtype = self.objective.subtype
180 assert direction in ("min", "max")
182 if self.objective.clstype is expressions.SquaredNorm:
183 if direction == "max":
184 return True
185 else:
186 if direction == "min" and not subtype.convex:
187 return True
188 elif direction == "max" and not subtype.concave:
189 return True
191 return False
193 def __str__(self):
194 dirStr = self.direction.capitalize()
195 objStr = str(self.objective)
196 varStr = ", ".join(sorted("{} {}".format(n, v)
197 for v, n in self.variables.items()))
198 conStr = ", ".join(sorted("{} {}".format(n, c)
199 for c, n in self.constraints.items()))
200 optStr = ", ".join(sorted("{}={}".format(n, v)
201 for n, v in self.nondefault_options.items()))
203 return "{} {} subject to {} using {} and {}.".format(
204 dirStr, objStr,
205 conStr if conStr else "no constraints",
206 varStr if varStr else "no variables",
207 optStr if optStr else "default options")
209 def __repr__(self):
210 return glyphs.repr2("Footprint", str(self))
212 @classmethod
213 def from_problem(cls, problem):
214 """Create a footprint from a problem instance."""
215 return cls(chain(
216 (("dir", problem.objective.direction, None),
217 ("obj", problem.objective.normalized.function.type, None)),
218 (("var", v.var_type, 1) for v in problem.variables.values()),
219 (("con", con.type, 1) for con in problem.constraints.values()),
220 (("opt", n, v) for n, v in problem.options.nondefaults.items())))
222 @classmethod
223 def from_types(cls, obj_dir, obj_func, vars=[], cons=[], nd_opts={}):
224 """Create a footprint from collections of detailed types.
226 :param str obj_dir:
227 Objective direction.
229 :param obj_func:
230 Detailed objective function type.
232 :parm list(tuple) vars:
233 A list of pairs of detailed variable type and occurence count.
235 :parm list(tuple) cons:
236 A list of pairs of detailed constraint type and occurence count.
238 :param list(str) nd_opts:
239 A dictionary mapping option names to nondefault values.
240 """
241 return cls(chain(
242 (("dir", obj_dir, None),
243 ("obj", obj_func, None)),
244 (("var", vn[0], vn[1]) for vn in vars),
245 (("con", cn[0], cn[1]) for cn in cons),
246 (("opt", name, value) for name, value in nd_opts.items())))
248 def with_extra_options(self, **extra_options):
249 """Return a copy with additional solution search options applied."""
250 # Determine the new option set.
251 options = self.options.self_or_updated(**extra_options)
253 # Delete old nondefault options and set new ones.
254 return self.updated(chain(
255 (("opt", self.NONE),),
256 (("opt", n, v) for n, v in options.nondefaults.items())
257 ))
259 @cached_property
260 def size(self):
261 """Return the estimated size of the (dense) scalar constraint matrix."""
262 num_vars = 0
263 num_cons = 0
265 for dim in self.variables.values():
266 num_vars += dim
268 for con, num in self.constraints.items():
269 num_cons += con.clstype._cost(con.subtype)*num
271 return max(1, num_vars)*max(1, num_cons)
273 @property
274 def cost(self):
275 """A very rough measure on how expensive solving such a problem is.
277 This is logarithmic in the estimated size of the constraint matrix.
278 """
279 return math.log(self.size, 10)
282class Specification:
283 """Representation of a mathematical class of optimization problems."""
285 def __init__(self, objectives=None, variables=None, constraints=None,
286 nondefault_options=None):
287 """Create a specification from the given features.
289 The token :obj:`None` means no requirement.
290 """
291 self._objs = objectives
293 self._tree = RecordTree(chain(
294 (("dir", RecordTree.ALL),), # Not checked.
295 (("obj", RecordTree.ALL),), # Checked manually.
297 (("var", RecordTree.ALL),) if variables is None else
298 (("var", var, RecordTree.ALL) for var in variables),
300 (("con", RecordTree.ALL),) if constraints is None else
301 (("con", con, RecordTree.ALL) for con in constraints),
303 (("opt", RecordTree.ALL),) if nondefault_options is None else
304 (("opt", opt, RecordTree.ALL) for opt in nondefault_options)
305 ))
307 # TODO: Consider adding a helper method that also gives one string reason
308 # why the footprint does not match the specification.
309 def __contains__(self, footprint):
310 """Whether a problem footprint matches the specification."""
311 if not isinstance(footprint, Footprint):
312 raise TypeError("May only check if a footprint matches the "
313 "specification, not an object of type {}."
314 .format(type(footprint).__name__))
316 if self._objs is not None:
317 obj = footprint.objective.clstype
319 if not any(issubclass(obj, allowed) for allowed in self._objs):
320 return False
322 if not footprint << self._tree:
323 return False
325 return True
327 def mismatch_reason(self, footprint):
328 """Give one string reason why the given footprint does not match."""
329 if self._objs is not None:
330 obj = footprint.objective.clstype
332 if not any(issubclass(obj, allowed) for allowed in self._objs):
333 return "Optimizing {}.".format(obj.__name__)
335 mismatch = footprint.mismatch(self._tree)
337 for path in mismatch.get("var").paths:
338 return "Representing {}.".format(path[0].__name__)
340 for path in mismatch.get("con").paths:
341 return "Obeying {}.".format(path[0].__name__)
343 for path in mismatch.get("opt").paths:
344 return "Setting {}.".format(path[0].__name__)
346 assert footprint << self._tree
348 return "No reason."
350 @staticmethod
351 def _paths_str(paths):
352 return ", ".join(
353 ":".join(p.__name__ if isclass(p) else str(p) for p in path)
354 for path in paths)
356 def __str__(self):
357 dirStr = "Optimize"
359 if self._objs is None:
360 objStr = "any objective"
361 elif not self._objs:
362 objStr = "no objective"
363 else:
364 objStr = ", ".join(o.__name__ for o in self._objs)
366 vars, cons, opts = (self._tree.get(x) for x in ("var", "con", "opt"))
368 if not vars:
369 varStr = "no variables"
370 elif vars is RecordTree.ALL:
371 varStr = "any variables"
372 else:
373 varStr = self._paths_str(vars.paths)
375 if not cons:
376 conStr = "no constraint"
377 elif cons is RecordTree.ALL:
378 conStr = "any constraint"
379 else:
380 conStr = self._paths_str(cons.paths)
382 if not opts:
383 optStr = "default options"
384 elif opts is RecordTree.ALL:
385 optStr = "any options"
386 else:
387 optStr = "nondefault values for " + self._paths_str(opts.paths)
389 return "{} {} subject to {} using {} and {}.".format(
390 dirStr, objStr, conStr, varStr, optStr)
392 def __repr__(self):
393 return glyphs.repr2("Specification", str(self))
396# --------------------------------------
397__all__ = api_end(_API_START, globals())