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"""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.names()[1])) 

189 else: 

190 for solver_name in available_solvers(): 

191 solver = get_solver(solver_name) 

192 solvers.append(solver) 

193 

194 assert solvers, "Not even CVXOPT seems to be available." 

195 

196 if len(solvers) == 1 and solvers[0].supports(footprint): 

197 if options.verbosity >= 2: 

198 print("{} supports the problem directly.".format( 

199 solvers[0].names()[1])) 

200 

201 return cls(problem, solvers[0]) 

202 

203 if options.verbosity >= 2: 

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

205 solver.names()[1] for solver in solvers))) 

206 

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

208 new_footprints = [footprint] 

209 

210 while new_footprints: 

211 if options.max_footprints is not None \ 

212 and len(paths) >= options.max_footprints: 

213 if options.verbosity >= 1: 

214 print("Footprint limit reached ({}/{}).".format( 

215 len(paths), options.max_footprints)) 

216 break 

217 

218 active_footprints = new_footprints 

219 new_footprints = [] 

220 

221 if options.verbosity >= 3: 

222 print("Active footprints:\n{}".format("\n".join(" ({}) {}" 

223 .format(len(paths) - len(active_footprints) + i, f) 

224 for i, f in enumerate(active_footprints)))) 

225 

226 for num, footprint in enumerate(active_footprints): 

227 if options.verbosity >= 3: 

228 print("Prediction for ({}):".format( 

229 len(paths) - len(active_footprints) + num)) 

230 

231 for step in SORTED_REFORMS: 

232 if options.verbosity >= 3: 

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

234 

235 # Don't apply the same reformulation multiple times. 

236 if step in paths[footprint]: 

237 if options.verbosity >= 3: 

238 print("Already part of current path.") 

239 continue 

240 

241 # Check if the reformulation applies. 

242 if not step.supports(footprint): 

243 if options.verbosity >= 3: 

244 print("Not supported.") 

245 continue 

246 

247 # Predict the reformulation outcome. 

248 new_footprint = step.predict(footprint) 

249 

250 # Remember only the first (shortest) path to any footprint. 

251 if new_footprint in paths: 

252 if options.verbosity >= 3: 

253 print("Resulting footprint already reached.") 

254 continue 

255 

256 if options.verbosity >= 3: 

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

258 

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

260 new_footprints.append(new_footprint) 

261 

262 # Sort footprints by cost. 'paths' being an ordered dict ensures a 

263 # deterministic order with respect to same-cost footprints (with shorter 

264 # reformulation pipelines taking precedence). 

265 footprints = sorted(paths, key=(lambda f: f.cost)) 

266 

267 if options.verbosity >= 2: 

268 print("Reachable footprints:\n{}".format("\n".join( 

269 " ({}) [{:.4f}] {}".format(i, f.cost, f) 

270 for i, f in enumerate(footprints)))) 

271 

272 strategies = [] 

273 costs = [] 

274 

275 if options.verbosity >= 2: 

276 print("Solvable footprints:") 

277 

278 for num, footprint in enumerate(footprints): 

279 if not solvers: 

280 break 

281 

282 for solver in tuple(solvers): 

283 if solver.supports(footprint): 

284 cost = footprint.cost 

285 penalty = solver.penalty(options) 

286 total_cost = cost + penalty 

287 

288 if options.verbosity >= 2: 

289 print(" {} supports ({}) at cost {:.2f} + {:.2f} = " 

290 "{:.2f}.".format(solver.names()[1], num, cost, 

291 penalty, total_cost)) 

292 

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

294 costs.append(total_cost) 

295 

296 solvers.remove(solver) 

297 

298 if not strategies: 

299 if options.verbosity >= 2: 

300 print(" None found.") 

301 

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

303 "reasons for discarding reachable problem formulations:" 

304 

305 solver_reasons = {} 

306 

307 for solver in solvers: 

308 reasons = OrderedSet() 

309 for footprint in paths: # Footprints in original order. 

310 supported, reason = solver.supports(footprint, explain=True) 

311 assert not supported 

312 reasons.add(reason) 

313 reasons = tuple(reasons) 

314 

315 solver_reasons.setdefault(reasons, []) 

316 solver_reasons[reasons].append(solver) 

317 

318 for reasons, unsupported_solvers in solver_reasons.items(): 

319 if len(unsupported_solvers) == 1: 

320 synopsis += "\n {} does not support:".format( 

321 unsupported_solvers.pop().names()[1]) 

322 else: 

323 names = tuple(s.names()[1] for s in unsupported_solvers) 

324 synopsis += "\n {} and {} do not support:".format( 

325 ", ".join(names[:-1]), names[-1]) 

326 

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

328 

329 raise NoStrategyFound(synopsis) 

330 

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

332 

333 

334# -------------------------------------- 

335__all__ = api_end(_API_START, globals())