Coverage for picos/modeling/strategy.py: 79.87%
159 statements
« prev ^ index » next coverage.py v6.5.0, created at 2023-02-15 14:21 +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 strategy search."""
21from collections import OrderedDict
23from .. import glyphs
24from ..apidoc import api_end, api_start
25from ..containers import OrderedSet
26from ..reforms import SORTED_REFORMS, ExtraOptions, Reformulation
27from ..solvers import Solver, available_solvers, get_solver, get_solver_name
28from .problem import Problem
30_API_START = api_start(globals())
31# -------------------------------
34class NoStrategyFound(RuntimeError):
35 """No solution strategy found.
37 Raised when no viable combination of reformulations and solver to tackle the
38 problem could be found.
39 """
41 pass
44class Strategy:
45 """Optimization problem solution strategy."""
47 def __init__(self, problem, solver, *reforms):
48 """Construct a :class:`Strategy`.
50 :param ~picos.Problem problem:
51 The first step in the solution pipeline; the problem to be solved.
53 :param type solver:
54 The last step in the solution pipeline; the solver class to be used.
56 :param list(~picos.reforms.reformulation.Reformulation) reforms:
57 Intermediate steps in the pipeline; reformulations to be applied.
58 May not include :class:`~picos.reforms.ExtraOptions` which is
59 automatically made the first reformulation.
60 """
61 if not isinstance(problem, Problem):
62 raise TypeError("First argument must be a problem instance.")
64 if not issubclass(solver, Solver):
65 raise TypeError("Second argument must be a solver class.")
67 if not all(issubclass(reform, Reformulation) for reform in reforms):
68 raise TypeError("Extra arguments must be reformulation classes.")
70 if ExtraOptions in reforms:
71 raise TypeError("The ExtraOptions reformulation is implicitly part "
72 "of any strategy and may not be added explicitly.")
74 self.nodes = [problem, ExtraOptions(problem)]
76 for reform in reforms:
77 self.nodes.append(reform(self.nodes[-1]))
79 self.nodes.append(solver(self.nodes[-1]))
81 @property
82 def problem(self):
83 """The problem to be solved."""
84 return self.nodes[0]
86 @property
87 def reforms(self):
88 """All reformulations in use.
90 This includes the implicit :class:`~picos.reforms.ExtraOptions`.
91 """
92 return self.nodes[1:-1]
94 @property
95 def solver(self):
96 """The solver instance in use."""
97 return self.nodes[-1]
99 def __str__(self):
100 return "\n".join(
101 "{}. {}".format(num + 1, node.__class__.__name__)
102 for num, node in enumerate(self.nodes[1:]))
104 def __repr__(self):
105 return glyphs.repr1("Solution strategy for {}".format(self.solver.name))
107 def valid(self, **extra_options):
108 """Whether the solution strategy can be executed.
110 :param extra_options:
111 A keyword parameter sequence of additional options (in addition to
112 those of the problem) to assume used.
113 """
114 problem = self.nodes[0]
115 solver = self.nodes[-1]
117 # Determine the footprint with extra options set.
118 footprint = problem.footprint.with_extra_options(**extra_options)
119 options = footprint.options
121 # Handle a conflicting solver selection.
122 if options.ad_hoc_solver and options.ad_hoc_solver != solver:
123 return False
124 elif options.solver and options.solver != get_solver_name(solver):
125 return False
127 # Skip ExtraOptions but include the solver with the following.
128 for node in self.nodes[2:]:
129 if not node.supports(footprint):
130 return False
132 footprint = node.predict(footprint)
134 return True
136 def execute(self, **extra_options):
137 """Execute the solution strategy.
139 :param extra_options:
140 A keyword parameter sequence of additional options (in addition to
141 those of the problem) to use for this search.
143 :returns:
144 :class:`~picos.modeling.Solution` to the problem.
145 """
146 # Defer solving to the first reformulation, which is responsible for
147 # applying the extra options (i.e. ExtraOptions).
148 solution = self.nodes[1].execute(**extra_options)
150 # Attach the solution to the root problem. Note that reformulations are
151 # allowed to already do this within their 'backward' method, but for
152 # performance reasons it is best to do this just once, here.
153 if isinstance(solution, list):
154 for s in solution:
155 s.attach_to(self.nodes[0])
156 else:
157 solution.attach_to(self.nodes[0])
159 return solution
161 @classmethod
162 def from_problem(cls, problem, **extra_options):
163 """Create a solution strategy for the given problem.
165 :param ~picos.Problem problem:
166 The optimization problem to search a strategy for.
168 :param extra_options:
169 A keyword parameter sequence of additional options (in addition to
170 those of the problem) to assume used.
171 """
172 # Determine the footprint with extra options set.
173 footprint = problem.footprint.with_extra_options(**extra_options)
174 options = footprint.options
176 # Decide on solvers to consider.
177 solvers = []
178 if options.ad_hoc_solver:
179 solvers.append(options.ad_hoc_solver)
180 elif options.solver:
181 solver = get_solver(options.solver)
183 if solver.available():
184 solvers.append(solver)
185 else:
186 raise RuntimeError(
187 "Selected solver {} is not available on the system."
188 .format(solver.get_via_name()))
189 else:
190 for solver_name in available_solvers():
191 solver = get_solver(solver_name)
192 solvers.append(solver)
194 if not solvers:
195 raise RuntimeError("Not even CVXOPT seems to be available. "
196 "Did you blacklist all available solvers?")
198 if len(solvers) == 1 and solvers[0].supports(footprint):
199 if options.verbosity >= 2:
200 print("{} supports the problem directly.".format(
201 solvers[0].get_via_name()))
203 return cls(problem, solvers[0])
205 if options.verbosity >= 2:
206 print("Selected solvers:\n {}".format(", ".join(
207 solver.get_via_name() for solver in solvers)))
209 paths = OrderedDict({footprint: tuple()})
210 new_footprints = [footprint]
212 while new_footprints:
213 if options.max_footprints is not None \
214 and len(paths) >= options.max_footprints:
215 if options.verbosity >= 1:
216 print("Footprint limit reached ({}/{}).".format(
217 len(paths), options.max_footprints))
218 break
220 active_footprints = new_footprints
221 new_footprints = []
223 if options.verbosity >= 3:
224 print("Active footprints:\n{}".format("\n".join(" ({}) {}"
225 .format(len(paths) - len(active_footprints) + i, f)
226 for i, f in enumerate(active_footprints))))
228 for num, footprint in enumerate(active_footprints):
229 if options.verbosity >= 3:
230 print("Prediction for ({}):".format(
231 len(paths) - len(active_footprints) + num))
233 for step in SORTED_REFORMS:
234 if options.verbosity >= 3:
235 print(" {}:".format(step.__name__), end=" ")
237 # Don't apply the same reformulation multiple times.
238 if step in paths[footprint]:
239 if options.verbosity >= 3:
240 print("Already part of current path.")
241 continue
243 # Check if the reformulation applies.
244 if not step.supports(footprint):
245 if options.verbosity >= 3:
246 print("Not supported.")
247 continue
249 # Predict the reformulation outcome.
250 new_footprint = step.predict(footprint)
252 # Remember only the first (shortest) path to any footprint.
253 if new_footprint in paths:
254 if options.verbosity >= 3:
255 print("Resulting footprint already reached.")
256 continue
258 if options.verbosity >= 3:
259 print("Reached new footprint ({}).".format(len(paths)))
261 paths[new_footprint] = paths[footprint] + (step,)
262 new_footprints.append(new_footprint)
264 # Sort footprints by cost. 'paths' being an ordered dict ensures a
265 # deterministic order with respect to same-cost footprints (with shorter
266 # reformulation pipelines taking precedence).
267 footprints = sorted(paths, key=(lambda f: f.cost))
269 if options.verbosity >= 2:
270 print("Reachable footprints:\n{}".format("\n".join(
271 " ({}) [{:.4f}] {}".format(i, f.cost, f)
272 for i, f in enumerate(footprints))))
274 strategies = []
275 costs = []
277 if options.verbosity >= 2:
278 print("Solvable footprints:")
280 for num, footprint in enumerate(footprints):
281 if not solvers:
282 break
284 for solver in tuple(solvers):
285 if solver.supports(footprint):
286 cost = footprint.cost
287 penalty = solver.penalty(options)
288 total_cost = cost + penalty
290 if options.verbosity >= 2:
291 print(" {} supports ({}) at cost {:.2f} + {:.2f} = "
292 "{:.2f}.".format(solver.get_via_name(), num, cost,
293 penalty, total_cost))
295 strategies.append(cls(problem, solver, *paths[footprint]))
296 costs.append(total_cost)
298 solvers.remove(solver)
300 if not strategies:
301 if options.verbosity >= 2:
302 print(" None found.")
304 synopsis = "No problem reformulation strategy found.\nSelected " \
305 "reasons for discarding reachable problem formulations:"
307 solver_reasons = {}
309 for solver in solvers:
310 reasons = OrderedSet()
311 for footprint in paths: # Footprints in original order.
312 supported, reason = solver.supports(footprint, explain=True)
313 assert not supported
314 reasons.add(reason)
315 reasons = tuple(reasons)
317 solver_reasons.setdefault(reasons, [])
318 solver_reasons[reasons].append(solver)
320 for reasons, unsupported_solvers in solver_reasons.items():
321 if len(unsupported_solvers) == 1:
322 synopsis += "\n {} does not support:".format(
323 unsupported_solvers.pop().get_via_name())
324 else:
325 names = tuple(s.get_via_name() for s in unsupported_solvers)
326 synopsis += "\n {} and {} do not support:".format(
327 ", ".join(names[:-1]), names[-1])
329 synopsis += "\n - ".join(("",) + reasons)
331 raise NoStrategyFound(synopsis)
333 return strategies[costs.index(min(costs))]
336# --------------------------------------
337__all__ = api_end(_API_START, globals())