Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

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# ------------------------------------------------------------------------------ 

18 

19"""Backend for problem reformulation classes.""" 

20 

21# ------------------------------------------------------------------------------ 

22# TODO: Make the solver base class inherit from Reformulation, in particular the 

23# update related methods. 

24# ------------------------------------------------------------------------------ 

25 

26from abc import ABC, abstractmethod 

27 

28from ..apidoc import api_end, api_start 

29from ..modeling import Footprint, Problem, Solution 

30 

31_API_START = api_start(globals()) 

32# ------------------------------- 

33 

34 

35class Reformulation(ABC): 

36 """Base class for problem reformulations. 

37 

38 Abstract base class for a reformulation from one (possibly already 

39 reformulated) problem form to another. 

40 """ 

41 

42 # -------------------------------------------------------------------------- 

43 # The following section contains the abstract methods, which are exactly the 

44 # methods that reformulation implementations are supposed to override. 

45 # -------------------------------------------------------------------------- 

46 

47 @classmethod 

48 @abstractmethod 

49 def supports(cls, footprint): 

50 """Whether the reformulation affects problems with the given footprint. 

51 

52 The reformulation must support every problem with such a footprint and 

53 the resulting problem should have a changed footprint. 

54 """ 

55 pass 

56 

57 @classmethod 

58 @abstractmethod 

59 def predict(cls, footprint): 

60 """Predict the reformulation's effect on a problem footprint. 

61 

62 Given a problem footprint, returns another problem footprint that a 

63 problem with the former one would be reformulated to. 

64 

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 

69 

70 @abstractmethod 

71 def forward(self): 

72 """Perform the initial problem reformulation. 

73 

74 Creates a modified copy or clone of the problem in :attr:`input` and 

75 stores it as :attr:`output`. 

76 

77 See :meth:`~.problem.Problem.copy` and :meth:`~.problem.Problem.clone` 

78 for the differences between a copy and a clone. 

79 

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 

85 

86 @abstractmethod 

87 def update(self): 

88 """Update a previous problem reformulation. 

89 

90 Updates :attr:`output` and related bookkeeping information with respect 

91 to changes in :attr:`input`. 

92 

93 :raises NotImplementedError: 

94 If performing an update is not feasible for the reformulation. 

95 """ 

96 pass 

97 

98 @abstractmethod 

99 def backward(self, solution): 

100 """Translate back a solution from reformulated to original problem. 

101 

102 Transforms a single :class:`~.solution.Solution` to :attr:`output` to a 

103 solution of :attr:`input`. 

104 

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 

110 

111 # -------------------------------------------------------------------------- 

112 # The following section contains the non-abstract methods, which are exactly 

113 # the methods that reformulation implementations are supposed to inherit. 

114 # -------------------------------------------------------------------------- 

115 

116 def _reset_knowns(self): 

117 self._knownObjective = None 

118 self._knownVariables = set() 

119 self._knownConstraints = set() 

120 

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()) 

125 

126 def __init__(self, theObject): 

127 """Initialize :class:`Reformulation` instances. 

128 

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__)) 

146 

147 self.successor = None 

148 """The next reformulation in the pipeline.""" 

149 

150 self.output = None 

151 """The output problem.""" 

152 

153 self._reset_knowns() 

154 

155 def reset(self): 

156 """Reset the pipeline from this reformulation onward. 

157 

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." 

164 

165 self.output = None 

166 self._reset_knowns() 

167 

168 self.successor.reset() 

169 

170 input = property(lambda self: 

171 self.predecessor.output if self.predecessor else self._input, 

172 doc="The input problem.") 

173 

174 verbosity = property(lambda self: self.input.options.verbosity, 

175 doc="Verbosity level of the reformulation; same as for input problem.") 

176 

177 def _verify_prediction(self): 

178 if not self.input.options.verify_prediction: 

179 return 

180 

181 expectedType = self.predict(Footprint.from_problem(self.input)) 

182 outputType = Footprint.from_problem(self.output) 

183 

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)) 

190 

191 def execute(self): 

192 """Reformulate the problem and obtain a solution from the result. 

193 

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." 

200 

201 verbose = self.verbosity > 0 

202 

203 # Update the output problem if possible. 

204 if self.output: 

205 if verbose: 

206 print("Updating {}.".format(self.__class__.__name__)) 

207 

208 try: 

209 self.update() 

210 except NotImplementedError: 

211 if verbose: 

212 print("Update failed: Not implemented for {}." 

213 .format(self.__class__.__name__)) 

214 

215 self.reset() 

216 

217 # Create the output problem if necessary. 

218 if not self.output: 

219 if verbose: 

220 print("Applying {}.".format(self.__class__.__name__)) 

221 

222 self.forward() 

223 self._set_knowns() 

224 

225 # Verify that the output problem is of the expected type. 

226 self._verify_prediction() 

227 

228 # Advance one step. 

229 outputSolution = self.successor.execute() 

230 

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] 

236 

237 def _objective_has_changed(self): 

238 """Check for an objective function change. 

239 

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." 

245 

246 objectiveChanged = self._knownObjective != self.input.objective 

247 

248 if objectiveChanged: 

249 self._knownObjective = self.input.objective 

250 

251 return objectiveChanged 

252 

253 def _new_variables(self): 

254 """Check for new variables. 

255 

256 Yields variables that were added to the input problem since the last 

257 forward or update. 

258 

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 

266 

267 def _removed_variables(self): 

268 """Check for removed variables. 

269 

270 Yields variables that were removed from the input problem since the last 

271 forward or update. 

272 

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) 

282 

283 def _new_constraints(self): 

284 """Check for new constraints. 

285 

286 Yields constraints that were added to the input problem since the last 

287 forward or update. 

288 

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 

297 

298 def _removed_constraints(self): 

299 """Check for removed constraints. 

300 

301 Yields constraints that were removed from the input problem since the 

302 last forward or update. 

303 

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) 

313 

314 def _pass_updated_objective(self): 

315 """Pass changes in the objective function from input to output problem. 

316 

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 

322 

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. 

328 

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. 

332 

333 .. warning:: 

334 Variables are passed as with :meth:`Problem.clone`, not copied. 

335 

336 .. warning:: 

337 This method clears the buffers of new and removed variables. 

338 """ 

339 for variable in self._new_variables(): 

340 pass 

341 

342 for variable in self._removed_variables(): 

343 pass 

344 

345 def _pass_updated_cons(self, ignore=type(None)): 

346 """Pass constraint changes from input to output problem. 

347 

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. 

351 

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. 

355 

356 .. warning:: 

357 Constraints are passed as with :meth:`Problem.clone`, not copied. 

358 

359 .. warning:: 

360 This method clears the buffers of new and removed constraints. 

361 """ 

362 added, removed = [], [] 

363 

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) 

370 

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) 

379 

380 if ignore is not type(None): # noqa: E721 

381 return added, removed 

382 

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 

386 

387 

388# -------------------------------------- 

389__all__ = api_end(_API_START, globals())