Coverage for picos/modeling/solution.py: 85.88%
255 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 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 solution representation."""
21import warnings
23from .. import glyphs
24from ..apidoc import api_end, api_start
26_API_START = api_start(globals())
27# -------------------------------
30# Solution status strings, as verified by PICOS.
31VS_UNKNOWN = "unverified"
32"""PICOS failed to verify the solution."""
34VS_DETACHED = "detached"
35"""The solution is not attached to a problem (it was given by the user)."""
37VS_EMPTY = "empty"
38"""The solution is empty; there are neither primals nor duals."""
40VS_DETACHED_EMPTY = "detached empty"
41"""The solution is both detached and empty."""
43VS_OUTDATED = "outdated"
44"""The solution does not fit the problem formulation any more.
46Variables or constraints were removed from the problem."""
48VS_INCOMPLETE = "incomplete"
49"""The primal (dual) solution does not concern all variables (constraints)."""
51VS_FEASIBLE = "feasible"
52"""The solution is primal feasible; there is no dual solution."""
54VS_INFEASIBLE = "infeasible"
55"""The solution is primal infeasible; there is no dual solution."""
57VS_PRIMAL_FEASIBLE = "primal feasible"
58"""The solution is primal feasible; a dual solution was not verified."""
60VS_PRIMAL_INFEASIBLE = "primal infeasible"
61"""The solution is primal infeasible; a dual solution was not verified."""
64# Primal or dual solution (or search) status strings, as claimed by the solver.
65SS_UNKNOWN = "unknown"
66"""The solver did not make a clear claim about the solution status."""
68SS_EMPTY = "empty"
69"""The solver claims not to have produced a solution."""
71SS_OPTIMAL = "optimal"
72"""The solution is optimal."""
74SS_FEASIBLE = "feasible"
75"""The solution is feasible."""
77SS_INFEASIBLE = "infeasible"
78"""No feasible solution exists.
80In the case of a primal solution, the problem is infeasible. In the case of a
81dual solution, the problem is unbounded.
82"""
84SS_PREMATURE = "premature"
85"""The search was prematurely terminated due to some limit."""
87SS_FAILURE = "failure"
88"""The search was termined due to a solver failure."""
91# Problem status strings, as claimed by the solver.
92PS_UNKNOWN = "unknown"
93"""The solver did not make a clear claim about the problem status."""
95PS_FEASIBLE = "feasible"
96"""The problem is primal (and dual) feasible and bounded."""
98PS_INFEASIBLE = "infeasible"
99"""The problem is primal infeasible (and dual unbounded or infeasible)."""
101PS_UNBOUNDED = "unbounded"
102"""The problem is primal unbounded (and dual infeasible)."""
104PS_INF_OR_UNB = "infeasible or unbounded"
105"""The problem is primal infeasible or unbounded.
107Being unbounded is usually infered from being dual infeasible."""
109PS_UNSTABLE = "unstable"
110"""The problem was found numerically unstable or otherwise hard to handle."""
112PS_ILLPOSED = "illposed"
113"""The problem was found to be in a state that is not amenable to solution."""
116def _check_type(argument, *types):
117 """Enforce the type of a method or function argument."""
118 for type_ in types:
119 if type_ is None:
120 type_ = type(None)
121 if isinstance(argument, type_):
122 return
124 raise TypeError("An argument is of type '{}' but must be instance of {}."
125 .format(type(argument).__name__, " or ".join("'{}'".format(t.__name__)
126 for t in types)))
129# TODO: Make all public fields use snake_case, ensure backwards compatibility.
130class Solution:
131 """Assignment of primal and dual values to variables and constraints.
133 Instances are usually returned by a solver (and thus bound to a
134 :class:`problem <picos.Problem>` instance), but may be manually created by
135 the user:
137 >>> import picos
138 >>> x = picos.RealVariable("x")
139 >>> s = picos.Solution({x: 1}); s
140 <detached primal solution from user>
141 >>> s.apply()
142 >>> x.value
143 1.0
145 If the solution was created by a solver (or attached to a problem via
146 :func:`attach_to`), more information is available:
148 >>> P = picos.Problem()
149 >>> P.minimize = x
150 >>> P += x >= 2
151 >>> s = P.solve(solver = "cvxopt", duals = False); s
152 <feasible primal solution (claimed optimal) from cvxopt>
153 >>> "{:.2f} ms".format(1000.0 * s.searchTime) #doctest: +SKIP
154 '0.83 ms'
155 >>> P += x >= 3; s
156 <infeasible primal solution (was feasible and claimed optimal) from cvxopt>
157 """
159 def __init__(self, primals, duals=None, problem=None, solver="user",
160 primalStatus=SS_UNKNOWN, dualStatus=SS_UNKNOWN,
161 problemStatus=PS_UNKNOWN, searchTime=0.0, info=None,
162 vectorizedPrimals=False, reportedValue=None):
163 """Create a solution to an optimization problem.
165 :param dict(picos.expressions.BaseVariable, object) primals:
166 A mapping of variables to their primal solution value.
167 :param dict(picos.constraints.Constraint, object) duals:
168 A mapping of constraints to their dual solution value.
169 :param picos.Problem problem:
170 The problem that was solved to create the solution. If ``None``,
171 then the solution is "detached".
172 :param str solver:
173 The name of the solver that was used to create the solution.
174 :param str primalStatus:
175 The primal solution status as reported by the solver.
176 :param str dualStatus:
177 The dual solution status as reported by the solver.
178 :param str problemStatus:
179 The state of the problem as reported by the solver.
180 :param float searchTime:
181 Seconds that the solution process took.
182 :param dict info:
183 Additional solution (meta)data.
184 :param bool vectorizedPrimals:
185 Whether primal solution values are given with respect to the
186 variable's special vectorization format as used by PICOS internally.
187 :param float reportedValue:
188 Objective value of the solution as reported by the solver.
189 """
190 from ..expressions import BaseVariable
191 from ..constraints import Constraint
192 from .problem import Problem
194 if primals is None:
195 primals = {}
197 if duals is None:
198 duals = {}
200 if info is None:
201 info = {}
203 # Be strict about the arguments as they are handed to the user.
204 _check_type(primals, dict)
205 _check_type(duals, dict)
206 _check_type(problem, None, Problem)
207 _check_type(solver, str)
208 _check_type(primalStatus, str)
209 _check_type(dualStatus, str)
210 _check_type(problemStatus, str)
211 _check_type(searchTime, float)
212 _check_type(info, dict)
213 _check_type(vectorizedPrimals, bool)
214 _check_type(reportedValue, None, float)
216 for variable, _ in primals.items():
217 if not isinstance(variable, BaseVariable):
218 raise TypeError("They keys in the primals argument of "
219 "Solution.__init__ must be variables.")
221 for constraint, _ in duals.items():
222 if not isinstance(constraint, Constraint):
223 raise TypeError("They keys in the duals argument of "
224 "Solution.__init__ must be constraints.")
226 # Derive a "claimed status" from the claimed primal and dual states.
227 if primals and duals:
228 if primalStatus == dualStatus:
229 claimedStatus = primalStatus
230 else:
231 claimedStatus = "primal {} and dual {}".format(
232 primalStatus, dualStatus)
233 elif primals:
234 # Do not warn about correctingdualStatus, because the solver might
235 # have produced primals but PICOS did not read them.
236 dualStatus = SS_EMPTY
237 claimedStatus = primalStatus
238 elif duals:
239 # Do not warn about correcting primalStatus, because the solver
240 # might have produced duals but PICOS did not read them.
241 primalStatus = SS_EMPTY
242 claimedStatus = dualStatus
243 else:
244 primalStatus = SS_EMPTY
245 dualStatus = SS_EMPTY
246 claimedStatus = SS_EMPTY
248 # Infeasible problem implies infeasible primal.
249 if problemStatus == PS_INFEASIBLE \
250 and primalStatus not in (SS_INFEASIBLE, SS_EMPTY):
251 warnings.warn(
252 "{} claims that a problem is infeasible but does not say the "
253 "same about the nonempty primal solution. Correcting this.".
254 format(solver), RuntimeWarning)
255 primalStatus = SS_INFEASIBLE
257 # Unbounded problem implies infeasible dual.
258 if problemStatus == PS_UNBOUNDED \
259 and dualStatus not in (SS_INFEASIBLE, SS_EMPTY):
260 warnings.warn(
261 "{} claims that a problem is unbounded but does not say that "
262 "the nonempty dual solution is infeasible. Correcting this.".
263 format(solver), RuntimeWarning)
264 dualStatus = SS_INFEASIBLE
266 # Optimal solution implies feasible problem.
267 if claimedStatus == SS_OPTIMAL and problemStatus != PS_FEASIBLE:
268 warnings.warn(
269 "{} claims to have found an optimal solution but does not say "
270 " that the problem is feasible. Correcting this."
271 .format(solver), RuntimeWarning)
272 problemStatus = PS_FEASIBLE
274 self.problem = problem
275 """The problem that was solved to produce the solution."""
277 self.solver = solver
278 """The solver that produced the solution."""
280 self.searchTime = searchTime
281 """Time in seconds that the solution search took."""
283 self.primals = primals
284 """The primal solution values returned by the solver."""
286 self.duals = duals
287 """The dual solution values returned by the solver."""
289 self.info = info
290 """Additional information provided by the solver."""
292 self.lastStatus = VS_UNKNOWN
293 """The solution status as verified by PICOS when the solution was
294 applied to the problem."""
296 self.primalStatus = primalStatus
297 """The primal solution status as claimed by the solver."""
299 self.dualStatus = dualStatus
300 """The dual solution status as claimed by the solver."""
302 self.claimedStatus = claimedStatus
303 """The primal and dual solution status as claimed by the solver."""
305 self.problemStatus = problemStatus
306 """The problem status as claimed by the solver."""
308 self.vectorizedPrimals = vectorizedPrimals
309 """Whether primal values refer to variables' special vectorizations."""
311 self.reportedValue = reportedValue
312 """The objective value of the solution as reported by the solver."""
314 def _status_of_problem(self, problem):
315 """Retrieve the problem's verified solution status.
317 Requires that the solution has just been applied to the problem.
318 """
319 if not self.primals and not self.duals:
320 return VS_EMPTY
322 try:
323 isFeasible = problem.check_current_value_feasibility()[0]
324 except LookupError:
325 return VS_INCOMPLETE
326 except Exception:
327 return VS_UNKNOWN
329 if isFeasible:
330 return VS_PRIMAL_FEASIBLE if self.duals else VS_FEASIBLE
331 else:
332 return VS_PRIMAL_INFEASIBLE if self.duals else VS_INFEASIBLE
334 @property
335 def status(self):
336 """The current solution status as verified by PICOS.
338 .. warning::
340 Accessing this attribute is expensive for large problems as a copy
341 of the problem needs to be created and valued. If you have just
342 applied the solution to a :class:`problem <picos.Problem>`, query
343 the solution's lastStatus attribute instead.
344 """
345 if not self.primals and not self.duals:
346 if not self.problem:
347 return VS_DETACHED_EMPTY
348 else:
349 return VS_EMPTY
350 elif not self.problem:
351 return VS_DETACHED
352 elif not self.primals:
353 return VS_UNKNOWN
355 problemCopy = self.problem.copy()
357 try:
358 self.apply(toProblem=problemCopy)
359 except RuntimeError:
360 return VS_OUTDATED
362 return self._status_of_problem(problemCopy)
364 @property
365 def value(self):
366 """The objective value of the solution as computed by PICOS.
368 .. warning::
370 Accessing this attribute is expensive for large problems as a copy
371 of the problem needs to be created and valued. If you have just
372 applied the solution to a :class:`problem <picos.Problem>`, query
373 that problem instead.
374 """
375 if not self.problem:
376 raise RuntimeError(
377 "Cannot compute the objective value of a detached solution. "
378 "Use attach_to to assign the solution to a problem.")
380 problemCopy = self.problem.copy()
382 self.apply(toProblem=problemCopy)
384 return problemCopy.value
386 @property
387 def reported_value(self):
388 """The objective value as reported by the solver, or :obj:`None`."""
389 return self.reportedValue
391 def __str__(self):
392 verifiedStatus = self.status
393 lastStatus = self.lastStatus
394 claimedStatus = self.claimedStatus
395 problemStatus = self.problemStatus
397 if self.primals and self.duals:
398 solutionType = "solution pair"
399 elif self.primals:
400 solutionType = "primal solution"
401 elif self.duals:
402 solutionType = "dual solution"
403 else:
404 solutionType = "solution" # "(detached) empty solution"
406 # Print the last status if it is known and differs from the current one.
407 printLastStatus = lastStatus != VS_UNKNOWN and \
408 verifiedStatus != lastStatus
410 # Print the claimed status only if it differs from the initial verified
411 # one is not implied by a problem status that will be printed.
412 printClaimedStatus = \
413 claimedStatus not in (verifiedStatus, SS_UNKNOWN) and \
414 problemStatus not in (PS_INFEASIBLE, PS_UNBOUNDED)
416 # Print the problem status only if it is interesting.
417 printProblemStatus = \
418 problemStatus not in (PS_UNKNOWN, PS_FEASIBLE)
420 if printLastStatus and printClaimedStatus:
421 unverifiedStatus = " (was {} and claimed {})".format(
422 lastStatus, claimedStatus)
423 elif printLastStatus:
424 unverifiedStatus = " (was {})".format(lastStatus)
425 elif printClaimedStatus:
426 unverifiedStatus = " (claimed {})".format(claimedStatus)
427 else:
428 unverifiedStatus = ""
430 if printProblemStatus:
431 unverifiedStatus += \
432 " for a problem claimed {}".format(problemStatus)
434 return "{} {}{} from {}".format(verifiedStatus, solutionType,
435 unverifiedStatus, self.solver)
437 def __repr__(self):
438 return glyphs.repr1(self.__str__())
440 def apply(self, primals=True, duals=True, clearOnNone=True, toProblem=None,
441 snapshotStatus=False):
442 """Apply the solution to the involved variables and constraints.
444 :param bool primals: Whether to apply the primal solution.
445 :param bool duals: Whether to apply the dual solution.
446 :param bool clearOnNone: Whether to clear the value of a variable or
447 constraint if the solution has it set to None. This could happen in
448 case of an error or shortcoming of the solver or PICOS.
449 :param picos.Problem toProblem: If set to a copy of the problem that was
450 used to produce the solution, will apply the solution to that copy's
451 variables and constraints instead.
452 :param bool snapshotStatus: Whether to update the lastStatus attribute
453 with the new (verified) solution status. PICOS enables this whenever
454 it applies a solution returned by a solver.
455 """
456 if toProblem:
457 if primals:
458 thePrimals = {}
459 try:
460 for variable, primal in self.primals.items():
461 thePrimals[toProblem.variables[variable.name]] = primal
462 except KeyError as error:
463 raise RuntimeError(
464 "Cannot apply solution to specified problem as not all "
465 "variables for which primal values exist were found.") \
466 from error
468 if duals:
469 theDuals = {}
470 try:
471 for constraint, dual in self.duals.items():
472 theDuals[toProblem.constraints[constraint.id]] = dual
473 except KeyError as error:
474 raise RuntimeError(
475 "Cannot apply solution to specified problem as not all "
476 "constraints for which dual values exist were found.") \
477 from error
478 else:
479 thePrimals = self.primals
480 theDuals = self.duals
482 if primals:
483 for variable, primal in thePrimals.items():
484 if primal is None and not clearOnNone:
485 continue
487 if self.vectorizedPrimals:
488 variable.internal_value = primal
489 else:
490 variable.value = primal
492 if duals:
493 for constraint, dual in theDuals.items():
494 if dual is None and not clearOnNone:
495 continue
496 constraint.dual = dual
498 if snapshotStatus:
499 if toProblem:
500 self.lastStatus = self._status_of_problem(toProblem)
501 elif self.problem:
502 self.lastStatus = self._status_of_problem(self.problem)
503 else: # detached solution
504 self.lastStatus = self.status
506 if toProblem:
507 toProblem._last_solution = self
508 elif self.problem:
509 self.problem._last_solution = self
511 def attach_to(self, problem, snapshotStatus=False):
512 """Attach (or move) the solution to a problem.
514 Only variables and constraints that exist on the problem (same name or
515 ID, respectively) are kept.
517 :param bool snapshotStatus: Whether to set the lastStatus attribute
518 of the copy to match the new problem.
519 """
520 self.problem = problem
522 # Find variables of same name in the problem and assign primals.
523 oldPrimals, self.primals = self.primals, {}
524 for variable, primal in oldPrimals.items():
525 if variable.name in problem.variables:
526 self.primals[problem.variables[variable.name]] = primal
528 # Find constraints of same ID in the problem and assign duals.
529 oldDuals, self.duals = self.duals, {}
530 for constraint, dual in oldDuals.items():
531 if constraint.id in problem.constraints:
532 self.duals[problem.constraints[constraint.id]] = dual
534 # Update the last (verified) status.
535 if snapshotStatus:
536 self.lastStatus = problem.status
537 else:
538 self.lastStatus = VS_UNKNOWN
541# --------------------------------------
542__all__ = api_end(_API_START, globals())