Coverage for picos/solvers/solver.py: 83.33%
282 statements
« prev ^ index » next coverage.py v6.5.0, created at 2023-02-15 14:21 +0000
1# ------------------------------------------------------------------------------
2# Copyright (C) 2017-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"""Backend for solver interface implementations."""
21import importlib.util
22import os
23import sys
24import time
25from abc import ABC, abstractmethod
26from contextlib import contextmanager
28from .. import glyphs, settings
29from ..apidoc import api_end, api_start
30from ..formatting import solver_box
31from ..modeling.solution import Solution
33_API_START = api_start(globals())
34# -------------------------------
37class SolverError(Exception):
38 """Base class for solver-specific exceptions."""
40 pass
43class ProblemUpdateError(SolverError):
44 """Changes to the problem could not be forward to the solver.
46 Raised by implementations of ``_update_problem`` to signal to the method
47 ``_load_problem`` that the problem needs to be re-imported.
48 """
50 pass
53class OptionError(SolverError):
54 """Base class for solver option related errors."""
56 pass
59class UnsupportedOptionError(OptionError):
60 """The solver does not support an option.
62 Raised by implementations of ``_solve`` to signal to the user that an option
63 they specified is not supported by the solver or the requested sub-solver,
64 or in conjunction with the given problem type or with another option. If the
65 option is valid but not supported by PICOS, then NotImplementedError should
66 be raised instead. The exception is only raised if the ``strictOptions``
67 option is set, otherwise a warning is printed.
68 """
70 pass
73# TODO: Handle conflicting options globally, instead of within solver
74# implementations. (Should not inherit from SolverError then.)
75class ConflictingOptionsError(OptionError):
76 """Two solver options are in conflict.
78 Raised by implementations of ``_solve`` to signal to the user that two
79 options they specified cannot be used in conjunction.
80 """
82 pass
85# TODO: Handle dependent options globally, instead of within solver
86# implementations. (Should not inherit from SolverError then.)
87class DependentOptionError(OptionError):
88 """A solver option is invalid due to another option not being set.
90 Raised by implementations of ``_solve`` to signal to the user that an option
91 they specified needs another option to also be set.
92 """
94 pass
97# TODO: Handle option value errors globally, instead of within solver
98# implementations. (Should not inherit from SolverError then.)
99class OptionValueError(OptionError, ValueError):
100 """A solver option has an invalid value.
102 Raised by implementations of ``_solve`` to signal to the user that they have
103 set an option to an invalid value.
104 """
106 pass
109# TODO: Add a write function that interfaces the solver's export to file.
110# TODO: Potentially make this inherit from Reformulation.
111class Solver(ABC):
112 """Base class for an interface to an optimization solver."""
114 # --------------------------------------------------------------------------
115 # Static methods.
116 # --------------------------------------------------------------------------
118 @staticmethod
119 def check_import(importName):
120 """Asserts that a module is available without actually importing it.
122 :raises ModuleNotFoundError:
123 If the module could not be found.
124 """
125 if importlib.util.find_spec(importName) is None:
126 raise ModuleNotFoundError(
127 "Python module '{}' not found.".format(importName))
129 # --------------------------------------------------------------------------
130 # Abstract class methods.
131 # --------------------------------------------------------------------------
133 @classmethod
134 @abstractmethod
135 def supports(cls, footprint, explain=False):
136 """Whether a type of problem, given by footprint, is supported.
138 The default implementation ensures that all reformulations required by
139 user's choice have been performed before the problem is handed to the
140 solver. Solver implementations are thus required to incorporate it.
142 :param bool explain:
143 If :obj:`True`, then this returns a :class:`tuple` where the first
144 element is this method's regular return value and where the second
145 element is a string naming one reason why the footprint is not
146 supported (:obj:`None` if it is).
147 """
148 if footprint.options.dualize:
149 if explain:
150 return False, "Variants of the primal problem (dualize=True)."
151 else:
152 return False
154 return (True, None) if explain else True
156 @classmethod
157 @abstractmethod
158 def default_penalty(cls):
159 """Report the default penalty for the solver.
161 See :class:`~picos.Options` for the scale.
162 """
163 pass
165 @classmethod
166 @abstractmethod
167 def test_availability(cls):
168 """Raise an exception if the solver is not installed on the system.
170 Checks whether the solver is installed on the system, and raises an
171 appropriate exception (usually :exc:`ModuleNotFoundError` or
172 :exc:`ImportError`) if not. Does not return anything.
173 """
174 pass
176 # TODO: Consider separate abstract methods for better interface validation.
177 @classmethod
178 @abstractmethod
179 def names(cls):
180 """Return a name sequence ``(internal, short, long, interface)``.
182 1. The internal name is a lowercase keyword used for solver selection.
183 2. The short name is a properly capitalized official solver shortand.
184 3. The long name is the full official name of the solver.
185 4. The interface name is a properly capitalized short name of the Python
186 interface used, or :obj:`None` if the solver is Python-native or
187 includes a unique Python interface.
188 """
189 pass
191 @classmethod
192 @abstractmethod
193 def is_free(cls):
194 """Report whether the solver is free software.
196 This allows users to prevent PICOS from using non-free solvers at all,
197 including for internal use, via the :data:`~.settings.NONFREE_SOLVERS`
198 setting.
199 """
200 pass
202 # --------------------------------------------------------------------------
203 # Non-abstract class methods.
204 # --------------------------------------------------------------------------
206 @classmethod
207 def get_via_name(cls, interface_in_parenthesis=False):
208 """Return the name of the solver with the Python interface used."""
209 _, display, _, interface = cls.names()
210 return "{} via {}".format(display, interface) if interface else display
212 # --------------------------------------------------------------------------
213 # __init__ and instance properties.
214 # --------------------------------------------------------------------------
216 def __init__(self, problem):
217 """Instanciate a solver interface with an optimization problem.
219 An exception is raised when the solver is not available on the user's
220 platform. No exception is raised when the problem type is not supported
221 as the problem is first imported when a solution is requested.
223 Solver implementations are supposed to also implement :meth:`__init__`,
224 but with ``problem`` as its only positional argument, and using
225 :obj:`super` to provide fixed values for this method's additional
226 parameters.
228 :param problem: A PICOS optimization problem.
229 :type problem: :class:`Problem <picos.Problem>`
230 """
231 # Make sure the solver is available.
232 self.test_availability()
234 # The external (PICOS) problem represenation.
235 # HACK: Quick and dirty conversion to accept reformulations as input.
236 from ..modeling import Problem
237 from ..reforms import Reformulation
238 if isinstance(problem, Reformulation):
239 problem.successor = self
240 self.predecessor = problem
241 self._ext = None
242 else:
243 assert isinstance(problem, Problem)
244 self._ext = problem
246 # The solver's internal problem representation, which the advanced user
247 # may access at their own risk.
248 self.int = None
250 # The last optimization objective that was imported.
251 self._knownObjective = None
253 # The PICOS variables that are currently imported.
254 self._knownVariables = set()
256 # The PICOS constraints that are currently imported.
257 self._knownConstraints = set()
259 @property
260 def ext(self):
261 """The "external" (input) problem."""
262 return self._ext if self._ext else self.predecessor.output
264 @property
265 def name(self):
266 """Keyword string of the solver."""
267 return self.names()[0]
269 @property
270 def short_name(self):
271 """Short name of the solver."""
272 return self.names()[1]
274 @property
275 def long_name(self):
276 """Long name of the solver."""
277 return self.names()[2]
279 @property
280 def interface_name(self):
281 """Short name of the Python interface used, or :obj:`None`."""
282 return self.names()[3]
284 @property
285 def via_name(self):
286 """The short names of the solver and Python interface used."""
287 return self.get_via_name()
289 # --------------------------------------------------------------------------
290 # Abstract instance methods.
291 # --------------------------------------------------------------------------
293 @abstractmethod
294 def reset_problem(self):
295 """Reset the solver's internal problem representation and related data.
297 Method implementations are supposed to
299 - set ``int`` to None (after performing any garbage collection), and
300 - reset all additional problem metadata to the state it had after
301 :meth:`__init__`, in particular the data stored for
302 ``_update_problem``.
304 Solver implementations should not call :meth:`reset_problem` directly,
305 except from within :meth:`__init__` if this is convenient.
307 The user may call this method at any time if they wish to solve the
308 problem from scratch.
309 """
310 pass
312 @abstractmethod
313 def _import_problem(self):
314 """Convert a PICOS problem to the solver's internal representation.
316 Method implementations can assume to be run directly after either
317 :meth:`__init__` or :meth:`reset_problem`, and before ``_solve``. The
318 method is supposed to transform only the problem formulation itself;
319 solver configuration options are passed inside ``_solve`` instead.
320 """
321 pass
323 @abstractmethod
324 def _update_problem(self):
325 """Update the solver's internal problem representation, if possible.
327 Method implementations should make use of ``_objective_has_changed``,
328 ``_new_variables``, ``_removed_variables``, ``_new_constraints`` and
329 ``_removed_constraints``. Note that you can use each of the latter four
330 generators only once each update as they will update the sets of known
331 variables and constraints, respectively.
333 Method implementations may raise
335 - :exc:`NotImplementedError`, if updates to the internal problem
336 instance of the solver are not supported (not at all or just not by
337 PICOS), or
338 - :exc:`ProblemUpdateError`, if an update to the solver's internal
339 problem instance is not possible for the particular set of changes in
340 the problem formulation.
342 In both cases, the user will receive a warning and the problem will be
343 re-imported instead of updated. In the case of
344 :exc:`ProblemUpdateError`, a reason should be given and will be included
345 in the warning.
347 Solver implementations should not call ``_update_problem`` directly, but
348 instead call ``_load_problem``.
349 """
350 pass
352 @abstractmethod
353 def _solve(self):
354 """Solve the problem and return the solution.
356 Method implementations can assume to be run after ``_load_problem``,
357 which attempts to run ``_update_problem`` and falls back to
358 ``_import_problem``. The method is supposed to pass options to the
359 solver, run it within the ``_stopwatch`` context, and return the
360 solution. The solution object should be created via ``_make_solution``.
362 An InappropriateSolverError should be raised if the solver (or its
363 requested sub-solver) does not support the given problem type.
365 :returns picos.modeling.Solution: The solution found by the solver.
366 """
367 pass
369 # --------------------------------------------------------------------------
370 # Non-abstract class methods.
371 # --------------------------------------------------------------------------
373 @classmethod
374 def penalty(cls, options):
375 """Report solver penalty given an :class:`~picos.Options` object."""
376 return options["penalty_{}".format(cls.names()[0])]
378 @classmethod
379 def available(cls, verbose=False):
380 """Whether the solver is properly installed on the system."""
381 name = cls.names()[0]
382 via_name = cls.get_via_name()
384 if name in settings.SOLVER_BLACKLIST:
385 if verbose:
386 print("The solver {} is blacklisted.".format(via_name))
387 return False
389 if settings.SOLVER_WHITELIST and name not in settings.SOLVER_WHITELIST:
390 if verbose:
391 print("The solver {} is not whitelisted.".format(via_name))
392 return False
394 if not settings.NONFREE_SOLVERS and not cls.is_free():
395 if verbose:
396 print("The solver {} is non-free.".format(via_name))
397 return False
399 try:
400 cls.test_availability()
401 except Exception as error:
402 if verbose:
403 print(error)
404 return False
406 return True
408 @classmethod
409 def predict(cls, footprint):
410 """Return the solver class.
412 This mimics the behavior of
413 :meth:`Reformulation.predict <picos.reforms.Reformulation>` so that
414 solvers can be the last pipeline node in a reformulation strategy.
415 """
416 return cls
418 # --------------------------------------------------------------------------
419 # Non-abstract instance methods (except for __init__ and properties).
420 # -------------------------------------------------------------------------
422 def __repr__(self):
423 return glyphs.repr1(
424 "Problem interface between PICOS and {}".format(self.via_name))
426 def reset(self):
427 """A shorthand for :meth:`reset_problem`.
429 This is defined for consistency with
430 :meth:`Reformulation.reset <.reformulation.Reformulation.reset>`.
431 """
432 self.reset_problem()
434 def external_problem(self):
435 """Return the external (PICOS) problem represenation."""
436 return self.ext
438 def internal_problem(self):
439 """Return the solver's internal problem represenation."""
440 return self.int
442 def verbosity(self):
443 """Return the problem's current verbosity level."""
444 return self.ext.options.verbosity
446 def _verbosity_printer(self, minLevel, message=None):
447 """Print a message if the verbosity level reaches a threshold.
449 :returns: Whether messages are printed.
450 """
451 condition = self.ext.options.verbosity >= minLevel
452 if condition and message is not None:
453 print(message)
454 return condition
456 def _warn(self, message=None):
457 """Print a warning message, if the verbosity level allows for it.
459 :returns: Whether warning messages are printed.
460 """
461 return self._verbosity_printer(0, message)
463 def _verbose(self, message=None):
464 """Print an informative message, if the verbosity level allows for it.
466 :returns: Whether informative messages are printed.
467 """
468 return self._verbosity_printer(1, message)
470 def _debug(self, message=None):
471 """Print a debug message, if the verbosity level allows for it.
473 :returns: Whether debug messages are printed.
474 """
475 return self._verbosity_printer(2, message)
477 def _handle_unsupported_option(self, option, customMessage=None):
478 """Inform the user about an unsupported option.
480 The manner depends on the ``strict_options`` option; either a warning is
481 printed or an exception is raised.
482 """
483 assert option in self.ext.options, \
484 "The option '{}' does not exist.".format(option)
486 if self.ext.options[option] in (None, False):
487 return
489 if customMessage:
490 message = customMessage
491 else:
492 message = "{} does not support the '{}' option." \
493 .format(self.via_name, option)
495 if self.ext.options.strict_options:
496 raise UnsupportedOptionError(message)
497 else:
498 self._warn(message)
500 def _handle_unsupported_options(self, *options):
501 """Handle a number of unsupported options at once."""
502 for option in options:
503 self._handle_unsupported_option(option)
505 def _handle_bad_solver_specific_option(self, key, value, error):
506 picos_option = "{}_params".format(self.name)
507 assert picos_option in self.ext.options, \
508 "The PICOS option '{}' does not exist.".format(picos_option)
510 raise OptionValueError(
511 "Either the option '{}' set via '{}' does not exist for {} or the "
512 "given value '{}' is not valid for that option.".format(
513 key, picos_option, self.via_name, value)) from error
515 def _handle_bad_solver_specific_option_key(self, key, error=None):
516 picos_option = "{}_params".format(self.name)
517 assert picos_option in self.ext.options, \
518 "The PICOS option '{}' does not exist.".format(picos_option)
520 raise OptionValueError(
521 "The option '{}' set via '{}' does not exist for {}.".format(
522 key, picos_option, self.via_name)) from error
524 def _handle_bad_solver_specific_option_value(self, key, value, error=None):
525 picos_option = "{}_params".format(self.name)
526 assert picos_option in self.ext.options, \
527 "The PICOS option '{}' does not exist.".format(picos_option)
529 raise OptionValueError(
530 "The value '{}' for option '{}' set via '{}' is not valid for {}."
531 .format(value, key, picos_option, self.via_name)) from error
533 def _handle_continuous_nonconvex_error(self, error):
534 """Raise a descriptive :exc:`ArithmeticError`."""
535 raise ArithmeticError("{0} refuses the problem as (continuous) "
536 "nonconvex even though PICOS ensures convexity of (continuous) "
537 "problems given to {0}. The most likely cause is that some "
538 "quadratic form is numerically on the verge of being semidefinite, "
539 "with PICOS' and {0}'s judgement differing. You could try a slight "
540 "perturbation of your data such that all quadratic forms become "
541 "definite.".format(self.short_name)) from error
543 def _load_problem(self):
544 """(Re-)import or update the solver's problem state for solving."""
545 # Make sure the problem is supported.
546 footprint = self.ext.footprint
547 assert self.supports(footprint), \
548 "PICOS gave {} an unsupported problem to load: {}".format(
549 self.via_name, footprint)
551 # Import or update the problem.
552 if self.int is None:
553 self._verbose("Building a {} problem instance."
554 .format(self.short_name))
555 self._import_problem()
556 else:
557 try:
558 self._verbose("Updating the {} problem instance."
559 .format(self.short_name))
560 self._update_problem()
561 except (NotImplementedError, ProblemUpdateError) as error:
562 if type(error) is NotImplementedError:
563 reason = "Not supported with {}.".format(self.via_name)
564 else:
565 reason = str(error)
566 if reason == "":
567 reason = "Unknown reason."
568 self._verbose("Update failed: {}".format(reason))
569 self._verbose("Rebuilding the {} problem instance."
570 .format(self.short_name))
571 self.reset_problem()
572 self._import_problem()
574 # Remember which objective and what constraints were imported.
575 self._knownObjective = self.ext.objective
576 self._knownVariables = set(self.ext.variables.values())
577 self._knownConstraints = set(self.ext.constraints.values())
579 def _objective_has_changed(self):
580 """Check for an objective function change.
582 :returns: Whether the optimization objective has changed since the last
583 forward or update.
584 """
585 assert self._knownObjective is not None, \
586 "_objective_has_changed may only be used inside _update_problem."
588 objectiveChanged = self._knownObjective != self.ext.objective
590 if objectiveChanged:
591 self._knownObjective = self.ext.objective
593 return objectiveChanged
595 def _new_variables(self):
596 """Check for new variables.
598 Yields PICOS variables that were added to the external problem
599 representation since the last import or update.
601 Note that variables received from this method will also be added to the
602 set of known variables, so you can only iterate once within each update.
603 """
604 for variable in self.ext.variables.values():
605 if variable not in self._knownVariables:
606 self._knownVariables.add(variable)
607 yield variable
609 def _removed_variables(self):
610 """Check for removed variables.
612 Yields PICOS variables that were removed from the external problem
613 representation since the last import or update.
615 Note that variables received from this method will also be removed from
616 the set of known variables, so you can only iterate once within each
617 update.
618 """
619 newVariables = set(self.ext.variables.values())
620 for variable in self._knownVariables:
621 if variable not in newVariables:
622 yield variable
623 self._knownVariables.intersection_update(newVariables)
625 def _new_constraints(self):
626 """Check for new constraints.
628 Yields PICOS constraints that were added to the external problem
629 representation since the last import or update.
631 Note that constraints received from this method will also be added to
632 the set of known constraints, so you can only iterate once within each
633 update.
634 """
635 for constraint in self.ext.constraints.values():
636 if constraint not in self._knownConstraints:
637 self._knownConstraints.add(constraint)
638 yield constraint
640 def _removed_constraints(self):
641 """Check for removed constraints.
643 Yields PICOS constraints that were removed from the external problem
644 representation since the last import or update.
646 Note that constraints received from this method will also be removed
647 from the set of known constraints, so you can only iterate once within
648 each update.
649 """
650 newConstraints = set(self.ext.constraints.values())
651 for constraint in self._knownConstraints:
652 if constraint not in newConstraints:
653 yield constraint
654 self._knownConstraints.intersection_update(newConstraints)
656 @contextmanager
657 def _stopwatch(self):
658 """Store the time spent within the context in ``timer``.
660 Solver implementations should use this context around the call to the
661 solution routine to measure its search time.
662 """
663 startTime = time.time()
664 yield
665 endTime = time.time()
666 self.timer = endTime - startTime
668 def _reset_stopwatch(self):
669 """Reset the timer of the ``_stopwatch`` context manager."""
670 self.timer = None
672 def _make_solution(self, value, primals, duals, primalStatus, dualStatus,
673 problemStatus, info=None, vectorizedPrimals=True):
674 """Create a solution problem from within :meth:`_solve`.
676 Note that the default value for ``vectorizedPrimals`` is :obj:`True`,
677 unlike that of
678 :meth:`Solution.__init__ <picos.modeling.Solution.__init__>`. This is
679 because users are expected to create manual solutions from matrix data
680 while solvers usually work with the vectorized variables.
681 """
682 from ..modeling import Solution
683 from . import get_solver_name
685 assert self.timer is not None, \
686 "Solvers must measure search time via _stopwatch."
688 return Solution(
689 primals=primals,
690 duals=duals,
691 problem=self.ext,
692 solver=get_solver_name(self),
693 primalStatus=primalStatus,
694 dualStatus=dualStatus,
695 problemStatus=problemStatus,
696 searchTime=self.timer,
697 info=info,
698 vectorizedPrimals=vectorizedPrimals,
699 reportedValue=value)
701 def execute(self):
702 """Solve the problem and return the solution.
704 :returns picos.Solution or list(picos.Solution): A solution object or
705 list thereof.
706 """
707 self._load_problem()
708 self._reset_stopwatch()
710 self._verbose("Starting solution search.")
712 solution = self._solve()
714 if isinstance(solution, list):
715 assert all(isinstance(s, Solution) for s in solution)
716 else:
717 assert isinstance(solution, Solution)
719 return solution
721 @contextmanager
722 def _header(self, subsolver=None):
723 """Print both a header and a footer."""
724 if subsolver:
725 s = subsolver
726 elif self.interface_name:
727 s = self.interface_name
728 else:
729 s = None
731 with solver_box(self.long_name, self.short_name, s, self._verbose()):
732 yield
734 @property
735 def _license_warnings(self):
736 """Whether license related warnings may ignore verbosity."""
737 return settings.LICENSE_WARNINGS and self.ext.options.license_warnings
739 @contextmanager
740 def _enforced_verbosity(self, noStdOutAt=0, noStdErrAt=-1):
741 """Enfoce the user-specified verbosity within the context.
743 :param int noStdOutAt: Don't print to stdout at or below this verbosity.
744 :param int noStdErrAt: Don't print to stderr at or below this verbosity.
746 .. warning::
748 This context manager monkey-patches the :mod:`sys` module and is not
749 thread safe.
750 """
751 verbosity = self.ext.verbosity()
753 if verbosity <= max(noStdOutAt, noStdErrAt):
754 devNull = open(os.devnull, "w")
756 if verbosity <= noStdOutAt:
757 oldOut = sys.stdout
758 sys.stdout = devNull
760 if verbosity <= noStdErrAt:
761 oldErr = sys.stderr
762 sys.stderr = devNull
764 try:
765 yield
766 finally:
767 if verbosity <= noStdOutAt:
768 sys.stdout = oldOut
770 if verbosity <= noStdErrAt:
771 sys.stderr = oldErr
774# --------------------------------------
775__all__ = api_end(_API_START, globals())