Coverage for picos/reforms/reformulation.py: 85.93%
135 statements
« 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"""Backend for problem reformulation classes."""
21# ------------------------------------------------------------------------------
22# TODO: Make the solver base class inherit from Reformulation, in particular the
23# update related methods.
24# ------------------------------------------------------------------------------
26from abc import ABC, abstractmethod
28from ..apidoc import api_end, api_start
29from ..modeling import Footprint, Problem, Solution
31_API_START = api_start(globals())
32# -------------------------------
35class Reformulation(ABC):
36 """Base class for problem reformulations.
38 Abstract base class for a reformulation from one (possibly already
39 reformulated) problem form to another.
40 """
42 # --------------------------------------------------------------------------
43 # The following section contains the abstract methods, which are exactly the
44 # methods that reformulation implementations are supposed to override.
45 # --------------------------------------------------------------------------
47 @classmethod
48 @abstractmethod
49 def supports(cls, footprint):
50 """Whether the reformulation affects problems with the given footprint.
52 The reformulation must support every problem with such a footprint and
53 the resulting problem should have a changed footprint.
54 """
55 pass
57 @classmethod
58 @abstractmethod
59 def predict(cls, footprint):
60 """Predict the reformulation's effect on a problem footprint.
62 Given a problem footprint, returns another problem footprint that a
63 problem with the former one would be reformulated to.
65 This is used to predict the effects of a reformulation when planning
66 a solution strategy without the cost of actually transforming a problem.
67 """
68 pass
70 @abstractmethod
71 def forward(self):
72 """Perform the initial problem reformulation.
74 Creates a modified copy or clone of the problem in :attr:`input` and
75 stores it as :attr:`output`.
77 See :meth:`~.problem.Problem.copy` and :meth:`~.problem.Problem.clone`
78 for the differences between a copy and a clone.
80 Implementations are supposed to do the necessary bookkeeping so that
81 :meth:`backward` can transform a solution to the new problem back to a
82 solution of the original problem.
83 """
84 pass
86 @abstractmethod
87 def update(self):
88 """Update a previous problem reformulation.
90 Updates :attr:`output` and related bookkeeping information with respect
91 to changes in :attr:`input`.
93 :raises NotImplementedError:
94 If performing an update is not feasible for the reformulation.
95 """
96 pass
98 @abstractmethod
99 def backward(self, solution):
100 """Translate back a solution from reformulated to original problem.
102 Transforms a single :class:`~.solution.Solution` to :attr:`output` to a
103 solution of :attr:`input`.
105 The method is allowed to modify the solution; it is not necessary to
106 work on a copy. In particular, :meth:`~.solution.Solution.attach_to` can
107 be used if :meth:`forward` has created a deep copy of the problem.
108 """
109 pass
111 # --------------------------------------------------------------------------
112 # The following section contains the non-abstract methods, which are exactly
113 # the methods that reformulation implementations are supposed to inherit.
114 # --------------------------------------------------------------------------
116 def _reset_knowns(self):
117 self._knownObjective = None
118 self._knownVariables = set()
119 self._knownConstraints = set()
121 def _set_knowns(self):
122 self._knownObjective = self.input.objective
123 self._knownVariables = set(self.input.variables.values())
124 self._knownConstraints = set(self.input.constraints.values())
126 def __init__(self, theObject):
127 """Initialize :class:`Reformulation` instances.
129 :param theObject: The input to work on; either an optimization problem
130 or the (future) output of another reformulation.
131 :type theObject:
132 ~picos.Problem or ~picos.reforms.reformulation.Reformulation
133 """
134 if isinstance(theObject, Problem):
135 self.predecessor = None
136 self._input = theObject
137 elif isinstance(theObject, Reformulation):
138 self.predecessor = theObject
139 theObject.successor = self
140 elif isinstance(theObject, Footprint):
141 raise TypeError("Reformulations cannot be instanciated using "
142 "problem footprints. Use the predict classmethod.")
143 else:
144 raise TypeError("Cannot reformulate an object of type '{}'."
145 .format(type(theObject).__name__))
147 self.successor = None
148 """The next reformulation in the pipeline."""
150 self.output = None
151 """The output problem."""
153 self._reset_knowns()
155 def reset(self):
156 """Reset the pipeline from this reformulation onward.
158 This is done whenever a reformulation does not implement :meth:`update`
159 so that succeeding reformulations do not attempt to update a problem
160 which was completely rewritten as this may be inefficient.
161 """
162 assert self.successor, \
163 "The reformulation being reset has no successor."
165 self.output = None
166 self._reset_knowns()
168 self.successor.reset()
170 input = property(lambda self:
171 self.predecessor.output if self.predecessor else self._input,
172 doc="The input problem.")
174 verbosity = property(lambda self: self.input.options.verbosity,
175 doc="Verbosity level of the reformulation; same as for input problem.")
177 def _verify_prediction(self):
178 if not self.input.options.verify_prediction:
179 return
181 expectedType = self.predict(Footprint.from_problem(self.input))
182 outputType = Footprint.from_problem(self.output)
184 if outputType != expectedType:
185 raise RuntimeError("{} failed to produce a problem with the "
186 "expected footprint:\nEXPECTED: {}\nOUTCOME : {}\n"
187 "This is a bug; please report it to the PICOS developers. "
188 "You can disable the 'verify_prediction' option to try solving "
189 "anyway.".format(type(self).__name__, expectedType, outputType))
191 def execute(self):
192 """Reformulate the problem and obtain a solution from the result.
194 For this to work there needs to be a solver instance at the end of the
195 reformulation pipeline, which would implement its own version of this
196 method that actually solves the problem and produces the first solution.
197 """
198 assert self.successor, \
199 "The reformulation being executed has no successor."
201 verbose = self.verbosity > 0
203 # Update the output problem if possible.
204 if self.output:
205 if verbose:
206 print("Updating {}.".format(self.__class__.__name__))
208 try:
209 self.update()
210 except NotImplementedError:
211 if verbose:
212 print("Update failed: Not implemented for {}."
213 .format(self.__class__.__name__))
215 self.reset()
217 # Create the output problem if necessary.
218 if not self.output:
219 if verbose:
220 print("Applying {}.".format(self.__class__.__name__))
222 self.forward()
223 self._set_knowns()
225 # Verify that the output problem is of the expected type.
226 self._verify_prediction()
228 # Advance one step.
229 outputSolution = self.successor.execute()
231 # Transform the solution of the output problem for the input problem.
232 if isinstance(outputSolution, Solution):
233 return self.backward(outputSolution)
234 else:
235 return [self.backward(solution) for solution in outputSolution]
237 def _objective_has_changed(self):
238 """Check for an objective function change.
240 :returns: Whether the optimization objective has changed since the last
241 forward or update.
242 """
243 assert self._knownObjective is not None, \
244 "_objective_has_changed may only be used inside _update_problem."
246 objectiveChanged = self._knownObjective != self.input.objective
248 if objectiveChanged:
249 self._knownObjective = self.input.objective
251 return objectiveChanged
253 def _new_variables(self):
254 """Check for new variables.
256 Yields variables that were added to the input problem since the last
257 forward or update.
259 Note that variables received from this method will also be added to the
260 set of known variables, so you can only iterate once within each update.
261 """
262 for variable in self.input.variables.values():
263 if variable not in self._knownVariables:
264 self._knownVariables.add(variable)
265 yield variable
267 def _removed_variables(self):
268 """Check for removed variables.
270 Yields variables that were removed from the input problem since the last
271 forward or update.
273 Note that variables received from this method will also be removed from
274 the set of known variables, so you can only iterate once within each
275 update.
276 """
277 newVariables = set(self.input.variables.values())
278 for variable in self._knownVariables:
279 if variable not in newVariables:
280 yield variable
281 self._knownVariables.intersection_update(newVariables)
283 def _new_constraints(self):
284 """Check for new constraints.
286 Yields constraints that were added to the input problem since the last
287 forward or update.
289 Note that constraints received from this method will also be added to
290 the set of known constraints, so you can only iterate once within each
291 update.
292 """
293 for constraint in self.input.constraints.values():
294 if constraint not in self._knownConstraints:
295 self._knownConstraints.add(constraint)
296 yield constraint
298 def _removed_constraints(self):
299 """Check for removed constraints.
301 Yields constraints that were removed from the input problem since the
302 last forward or update.
304 Note that constraints received from this method will also be removed
305 from the set of known constraints, so you can only iterate once within
306 each update.
307 """
308 newConstraints = set(self.input.constraints.values())
309 for constraint in self._knownConstraints:
310 if constraint not in newConstraints:
311 yield constraint
312 self._knownConstraints.intersection_update(newConstraints)
314 def _pass_updated_objective(self):
315 """Pass changes in the objective function from input to output problem.
317 .. warning::
318 This method resets the objective-has-changed state.
319 """
320 if self._objective_has_changed():
321 self.output.objective = self.input.objective
323 # TODO: Determine if and in which form such a method is needed now that
324 # variables are added to problems implicitly (but still explicitly to
325 # solvers).
326 def _pass_updated_vars(self):
327 """Pass variable changes from input to output problem.
329 Adds all new varibles in the input problem to the output problem, and
330 removes all variables removed from the input problem also from the
331 output problem.
333 .. warning::
334 Variables are passed as with :meth:`Problem.clone`, not copied.
336 .. warning::
337 This method clears the buffers of new and removed variables.
338 """
339 for variable in self._new_variables():
340 pass
342 for variable in self._removed_variables():
343 pass
345 def _pass_updated_cons(self, ignore=type(None)):
346 """Pass constraint changes from input to output problem.
348 Adds all new constraints in the input problem to the output problem, and
349 removes all constraints removed from the input problem also from the
350 output problem.
352 :param type ignore: Constraints of this type are not handled. Instead,
353 the method returns a pair `(added, removed)` that contains the
354 respective constraints that were not handled.
356 .. warning::
357 Constraints are passed as with :meth:`Problem.clone`, not copied.
359 .. warning::
360 This method clears the buffers of new and removed constraints.
361 """
362 added, removed = [], []
364 for constraint in self._new_constraints():
365 assert constraint.id not in self.output.constraints
366 if isinstance(constraint, ignore):
367 added.append(constraint)
368 else:
369 self.output.add_constraint(constraint)
371 for constraint in self._removed_constraints():
372 if isinstance(constraint, ignore):
373 # No assertion in this case, because the reformulation would not
374 # have added such a constraint.
375 removed.append(constraint)
376 else:
377 assert constraint.id in self.output.constraints
378 self.output.remove_constraint(constraint.id)
380 if ignore is not type(None): # noqa: E721
381 return added, removed
383 def _pass_updated_options(self):
384 """Make the output problem use the same options object as the input."""
385 self.output.options = self.input.options
388# --------------------------------------
389__all__ = api_end(_API_START, globals())