Coverage for picos/modeling/strategy.py: 79.87%

Shortcuts on this page

r m x   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

159 statements  

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"""Optimization problem solution strategy search.""" 

20 

21from collections import OrderedDict 

22 

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 

29 

30_API_START = api_start(globals()) 

31# ------------------------------- 

32 

33 

34class NoStrategyFound(RuntimeError): 

35 """No solution strategy found. 

36 

37 Raised when no viable combination of reformulations and solver to tackle the 

38 problem could be found. 

39 """ 

40 

41 pass 

42 

43 

44class Strategy: 

45 """Optimization problem solution strategy.""" 

46 

47 def __init__(self, problem, solver, *reforms): 

48 """Construct a :class:`Strategy`. 

49 

50 :param ~picos.Problem problem: 

51 The first step in the solution pipeline; the problem to be solved. 

52 

53 :param type solver: 

54 The last step in the solution pipeline; the solver class to be used. 

55 

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

63 

64 if not issubclass(solver, Solver): 

65 raise TypeError("Second argument must be a solver class.") 

66 

67 if not all(issubclass(reform, Reformulation) for reform in reforms): 

68 raise TypeError("Extra arguments must be reformulation classes.") 

69 

70 if ExtraOptions in reforms: 

71 raise TypeError("The ExtraOptions reformulation is implicitly part " 

72 "of any strategy and may not be added explicitly.") 

73 

74 self.nodes = [problem, ExtraOptions(problem)] 

75 

76 for reform in reforms: 

77 self.nodes.append(reform(self.nodes[-1])) 

78 

79 self.nodes.append(solver(self.nodes[-1])) 

80 

81 @property 

82 def problem(self): 

83 """The problem to be solved.""" 

84 return self.nodes[0] 

85 

86 @property 

87 def reforms(self): 

88 """All reformulations in use. 

89 

90 This includes the implicit :class:`~picos.reforms.ExtraOptions`. 

91 """ 

92 return self.nodes[1:-1] 

93 

94 @property 

95 def solver(self): 

96 """The solver instance in use.""" 

97 return self.nodes[-1] 

98 

99 def __str__(self): 

100 return "\n".join( 

101 "{}. {}".format(num + 1, node.__class__.__name__) 

102 for num, node in enumerate(self.nodes[1:])) 

103 

104 def __repr__(self): 

105 return glyphs.repr1("Solution strategy for {}".format(self.solver.name)) 

106 

107 def valid(self, **extra_options): 

108 """Whether the solution strategy can be executed. 

109 

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] 

116 

117 # Determine the footprint with extra options set. 

118 footprint = problem.footprint.with_extra_options(**extra_options) 

119 options = footprint.options 

120 

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 

126 

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 

131 

132 footprint = node.predict(footprint) 

133 

134 return True 

135 

136 def execute(self, **extra_options): 

137 """Execute the solution strategy. 

138 

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. 

142 

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) 

149 

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

158 

159 return solution 

160 

161 @classmethod 

162 def from_problem(cls, problem, **extra_options): 

163 """Create a solution strategy for the given problem. 

164 

165 :param ~picos.Problem problem: 

166 The optimization problem to search a strategy for. 

167 

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 

175 

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) 

182 

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) 

193 

194 if not solvers: 

195 raise RuntimeError("Not even CVXOPT seems to be available. " 

196 "Did you blacklist all available solvers?") 

197 

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

202 

203 return cls(problem, solvers[0]) 

204 

205 if options.verbosity >= 2: 

206 print("Selected solvers:\n {}".format(", ".join( 

207 solver.get_via_name() for solver in solvers))) 

208 

209 paths = OrderedDict({footprint: tuple()}) 

210 new_footprints = [footprint] 

211 

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 

219 

220 active_footprints = new_footprints 

221 new_footprints = [] 

222 

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

227 

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

232 

233 for step in SORTED_REFORMS: 

234 if options.verbosity >= 3: 

235 print(" {}:".format(step.__name__), end=" ") 

236 

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 

242 

243 # Check if the reformulation applies. 

244 if not step.supports(footprint): 

245 if options.verbosity >= 3: 

246 print("Not supported.") 

247 continue 

248 

249 # Predict the reformulation outcome. 

250 new_footprint = step.predict(footprint) 

251 

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 

257 

258 if options.verbosity >= 3: 

259 print("Reached new footprint ({}).".format(len(paths))) 

260 

261 paths[new_footprint] = paths[footprint] + (step,) 

262 new_footprints.append(new_footprint) 

263 

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

268 

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

273 

274 strategies = [] 

275 costs = [] 

276 

277 if options.verbosity >= 2: 

278 print("Solvable footprints:") 

279 

280 for num, footprint in enumerate(footprints): 

281 if not solvers: 

282 break 

283 

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 

289 

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

294 

295 strategies.append(cls(problem, solver, *paths[footprint])) 

296 costs.append(total_cost) 

297 

298 solvers.remove(solver) 

299 

300 if not strategies: 

301 if options.verbosity >= 2: 

302 print(" None found.") 

303 

304 synopsis = "No problem reformulation strategy found.\nSelected " \ 

305 "reasons for discarding reachable problem formulations:" 

306 

307 solver_reasons = {} 

308 

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) 

316 

317 solver_reasons.setdefault(reasons, []) 

318 solver_reasons[reasons].append(solver) 

319 

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

328 

329 synopsis += "\n - ".join(("",) + reasons) 

330 

331 raise NoStrategyFound(synopsis) 

332 

333 return strategies[costs.index(min(costs))] 

334 

335 

336# -------------------------------------- 

337__all__ = api_end(_API_START, globals())