Coverage for picos/modeling/footprint.py: 75.72%

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

173 statements  

1# ------------------------------------------------------------------------------ 

2# Copyright (C) 2019-2020 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 description classes. 

20 

21This module implements a footprint of a single problem, storing number and types 

22of expressions and constraints, and the specification of a problem class. 

23""" 

24 

25import math 

26from inspect import isclass 

27from itertools import chain 

28 

29from .. import constraints, expressions, glyphs 

30from ..apidoc import api_end, api_start 

31from ..caching import cached_property 

32from ..containers import RecordTree 

33from ..expressions import variables 

34# from .options import OPTION_OBJS, Options # Circular import. 

35 

36_API_START = api_start(globals()) 

37# ------------------------------- 

38 

39 

40# Constants used by both Footprint and Specification. 

41_OBJS = tuple(exp for exp in expressions.__dict__.values() if isclass(exp) 

42 and issubclass(exp, expressions.Expression) 

43 and exp != expressions.Expression) # ALl proper Expression subclasses. 

44_DIRS = ("find", "min", "max") 

45_VARS = tuple(var for var in expressions.__dict__.values() if isclass(var) 

46 and issubclass(var, expressions.BaseVariable) 

47 and var != expressions.BaseVariable) # ALl proper BaseVariable subclasses. 

48_CONS = tuple(con for con in constraints.__dict__.values() if isclass(con) 

49 and issubclass(con, constraints.Constraint) 

50 and con != constraints.Constraint) # All proper Constraint subclasses. 

51# _OPTS = tuple(option.name for option in OPTION_OBJS) # All option names. 

52 

53 

54class Footprint(RecordTree): 

55 """Statistics on an optimization problem.""" 

56 

57 _ADD_VALUES = [("var",), ("con",)] 

58 

59 def __init__(self, recordsOrDict): 

60 """Construct a :class:`Footprint` from raw data. 

61 

62 See :class:`picos.containers.RecordTree.__init__`. The ``addValues`` 

63 argument is fixed; only variable and constraint paths are added. 

64 """ 

65 super(Footprint, self).__init__(recordsOrDict, self._ADD_VALUES) 

66 

67 # Sanity check records. 

68 for path, value in self.items: 

69 pathLen = len(path) 

70 category = path[0] if pathLen > 0 else None 

71 suptype = path[1] if pathLen > 1 else None 

72 subtype = path[2] if pathLen > 2 else None 

73 

74 if category == "dir": 

75 if pathLen == 2 and suptype in _DIRS and value is None: 

76 continue 

77 elif category == "obj": 

78 if pathLen == 3 and suptype in _OBJS \ 

79 and isinstance(subtype, suptype.Subtype) and value is None: 

80 continue 

81 elif category == "var": 

82 if pathLen == 3 and suptype in _VARS \ 

83 and isinstance(subtype, suptype.VarSubtype) \ 

84 and isinstance(value, int): 

85 continue 

86 elif category == "con": 

87 if pathLen == 3 and suptype in _CONS \ 

88 and isinstance(subtype, suptype.Subtype) \ 

89 and isinstance(value, int): 

90 continue 

91 elif category == "opt": 

92 # if pathLen == 2 and suptype in _OPTS: 

93 if pathLen == 2 and isinstance(suptype, str): 

94 continue 

95 

96 raise ValueError("Invalid problem footprint record: {} = {}." 

97 .format(path, value)) 

98 

99 # Sanity check for inconsistent duplicates or missing fields. 

100 if len(self["dir"]) != 1: 

101 raise TypeError("Not exactly one optimization direction defined for" 

102 " a problem footprint (but {}).".format(len(self["dir"]))) 

103 elif len(self["obj"]) != 1: 

104 raise TypeError("Not exactly one objective function defined for a " 

105 "problem footprint (but {}).".format(len(self["obj"]))) 

106 

107 def updated(self, recordsOrDict): 

108 """Override :class:`~picos.containers.RecordTree.updated`. 

109 

110 This method, just like :meth:`__init__`, does not take the additional 

111 ``addValues`` argument. 

112 """ 

113 return self.__class__( 

114 chain(self.records, self._record_iterator(recordsOrDict))) 

115 

116 @property 

117 def direction(self): 

118 """Objective function optimization direction.""" 

119 return next(self["dir"].paths)[0] 

120 

121 @property 

122 def objective(self): 

123 """Detailed type of the objective function.""" 

124 clstype, subtype = next(self["obj"].paths) 

125 return expressions.ExpressionType(clstype, subtype) 

126 

127 @cached_property 

128 def variables(self): 

129 """A dictionary mapping detailed variable types to their quantity.""" 

130 return {variables.VariableType(*ts): n 

131 for ts, n in self.get("var").items} 

132 

133 @cached_property 

134 def constraints(self): 

135 """A dictionary mapping detailed constraint types to their quantity.""" 

136 return {constraints.ConstraintType(*ts): n 

137 for ts, n in self.get("con").items} 

138 

139 @cached_property 

140 def nondefault_options(self): 

141 """A dictionary mapping option names to their nondefault values. 

142 

143 .. warning:: 

144 

145 This property is cached for performance reasons, do not modify any 

146 mutable option value (make a deep copy instead)! 

147 """ 

148 return {path[0]: value for path, value in self.get("opt").items} 

149 

150 @cached_property 

151 def options(self): 

152 """An :class:`~.options.Options` object. 

153 

154 .. warning:: 

155 

156 This property is cached for performance reasons, do not modify the 

157 returned object (make a :meth:`~.options.Options.copy` instead)! 

158 """ 

159 from .options import Options 

160 return Options(**self.nondefault_options) 

161 

162 @cached_property 

163 def integer(self): 

164 """Whether an integral variable type is present.""" 

165 return any(("var", vtype) in self for vtype in ( 

166 expressions.BinaryVariable, expressions.IntegerVariable)) 

167 

168 @property 

169 def continuous(self): 

170 """Whether no integral variable type is present.""" 

171 return not self.integer 

172 

173 @cached_property 

174 def nonconvex_quadratic_objective(self): 

175 """Whether the problem has a nonconvex quadratic objective.""" 

176 if issubclass(self.objective.clstype, expressions.QuadraticExpression): 

177 direction = self.direction 

178 subtype = self.objective.subtype 

179 

180 assert direction in ("min", "max") 

181 

182 if self.objective.clstype is expressions.SquaredNorm: 

183 if direction == "max": 

184 return True 

185 else: 

186 if direction == "min" and not subtype.convex: 

187 return True 

188 elif direction == "max" and not subtype.concave: 

189 return True 

190 

191 return False 

192 

193 def __str__(self): 

194 dirStr = self.direction.capitalize() 

195 objStr = str(self.objective) 

196 varStr = ", ".join(sorted("{} {}".format(n, v) 

197 for v, n in self.variables.items())) 

198 conStr = ", ".join(sorted("{} {}".format(n, c) 

199 for c, n in self.constraints.items())) 

200 optStr = ", ".join(sorted("{}={}".format(n, v) 

201 for n, v in self.nondefault_options.items())) 

202 

203 return "{} {} subject to {} using {} and {}.".format( 

204 dirStr, objStr, 

205 conStr if conStr else "no constraints", 

206 varStr if varStr else "no variables", 

207 optStr if optStr else "default options") 

208 

209 def __repr__(self): 

210 return glyphs.repr2("Footprint", str(self)) 

211 

212 @classmethod 

213 def from_problem(cls, problem): 

214 """Create a footprint from a problem instance.""" 

215 return cls(chain( 

216 (("dir", problem.objective.direction, None), 

217 ("obj", problem.objective.normalized.function.type, None)), 

218 (("var", v.var_type, 1) for v in problem.variables.values()), 

219 (("con", con.type, 1) for con in problem.constraints.values()), 

220 (("opt", n, v) for n, v in problem.options.nondefaults.items()))) 

221 

222 @classmethod 

223 def from_types(cls, obj_dir, obj_func, vars=[], cons=[], nd_opts={}): 

224 """Create a footprint from collections of detailed types. 

225 

226 :param str obj_dir: 

227 Objective direction. 

228 

229 :param obj_func: 

230 Detailed objective function type. 

231 

232 :parm list(tuple) vars: 

233 A list of pairs of detailed variable type and occurence count. 

234 

235 :parm list(tuple) cons: 

236 A list of pairs of detailed constraint type and occurence count. 

237 

238 :param list(str) nd_opts: 

239 A dictionary mapping option names to nondefault values. 

240 """ 

241 return cls(chain( 

242 (("dir", obj_dir, None), 

243 ("obj", obj_func, None)), 

244 (("var", vn[0], vn[1]) for vn in vars), 

245 (("con", cn[0], cn[1]) for cn in cons), 

246 (("opt", name, value) for name, value in nd_opts.items()))) 

247 

248 def with_extra_options(self, **extra_options): 

249 """Return a copy with additional solution search options applied.""" 

250 # Determine the new option set. 

251 options = self.options.self_or_updated(**extra_options) 

252 

253 # Delete old nondefault options and set new ones. 

254 return self.updated(chain( 

255 (("opt", self.NONE),), 

256 (("opt", n, v) for n, v in options.nondefaults.items()) 

257 )) 

258 

259 @cached_property 

260 def size(self): 

261 """Return the estimated size of the (dense) scalar constraint matrix.""" 

262 num_vars = 0 

263 num_cons = 0 

264 

265 for dim in self.variables.values(): 

266 num_vars += dim 

267 

268 for con, num in self.constraints.items(): 

269 num_cons += con.clstype._cost(con.subtype)*num 

270 

271 return max(1, num_vars)*max(1, num_cons) 

272 

273 @property 

274 def cost(self): 

275 """A very rough measure on how expensive solving such a problem is. 

276 

277 This is logarithmic in the estimated size of the constraint matrix. 

278 """ 

279 return math.log(self.size, 10) 

280 

281 

282class Specification: 

283 """Representation of a mathematical class of optimization problems.""" 

284 

285 def __init__(self, objectives=None, variables=None, constraints=None, 

286 nondefault_options=None): 

287 """Create a specification from the given features. 

288 

289 The token :obj:`None` means no requirement. 

290 """ 

291 self._objs = objectives 

292 

293 self._tree = RecordTree(chain( 

294 (("dir", RecordTree.ALL),), # Not checked. 

295 (("obj", RecordTree.ALL),), # Checked manually. 

296 

297 (("var", RecordTree.ALL),) if variables is None else 

298 (("var", var, RecordTree.ALL) for var in variables), 

299 

300 (("con", RecordTree.ALL),) if constraints is None else 

301 (("con", con, RecordTree.ALL) for con in constraints), 

302 

303 (("opt", RecordTree.ALL),) if nondefault_options is None else 

304 (("opt", opt, RecordTree.ALL) for opt in nondefault_options) 

305 )) 

306 

307 # TODO: Consider adding a helper method that also gives one string reason 

308 # why the footprint does not match the specification. 

309 def __contains__(self, footprint): 

310 """Whether a problem footprint matches the specification.""" 

311 if not isinstance(footprint, Footprint): 

312 raise TypeError("May only check if a footprint matches the " 

313 "specification, not an object of type {}." 

314 .format(type(footprint).__name__)) 

315 

316 if self._objs is not None: 

317 obj = footprint.objective.clstype 

318 

319 if not any(issubclass(obj, allowed) for allowed in self._objs): 

320 return False 

321 

322 if not footprint << self._tree: 

323 return False 

324 

325 return True 

326 

327 def mismatch_reason(self, footprint): 

328 """Give one string reason why the given footprint does not match.""" 

329 if self._objs is not None: 

330 obj = footprint.objective.clstype 

331 

332 if not any(issubclass(obj, allowed) for allowed in self._objs): 

333 return "Optimizing {}.".format(obj.__name__) 

334 

335 mismatch = footprint.mismatch(self._tree) 

336 

337 for path in mismatch.get("var").paths: 

338 return "Representing {}.".format(path[0].__name__) 

339 

340 for path in mismatch.get("con").paths: 

341 return "Obeying {}.".format(path[0].__name__) 

342 

343 for path in mismatch.get("opt").paths: 

344 return "Setting {}.".format(path[0].__name__) 

345 

346 assert footprint << self._tree 

347 

348 return "No reason." 

349 

350 @staticmethod 

351 def _paths_str(paths): 

352 return ", ".join( 

353 ":".join(p.__name__ if isclass(p) else str(p) for p in path) 

354 for path in paths) 

355 

356 def __str__(self): 

357 dirStr = "Optimize" 

358 

359 if self._objs is None: 

360 objStr = "any objective" 

361 elif not self._objs: 

362 objStr = "no objective" 

363 else: 

364 objStr = ", ".join(o.__name__ for o in self._objs) 

365 

366 vars, cons, opts = (self._tree.get(x) for x in ("var", "con", "opt")) 

367 

368 if not vars: 

369 varStr = "no variables" 

370 elif vars is RecordTree.ALL: 

371 varStr = "any variables" 

372 else: 

373 varStr = self._paths_str(vars.paths) 

374 

375 if not cons: 

376 conStr = "no constraint" 

377 elif cons is RecordTree.ALL: 

378 conStr = "any constraint" 

379 else: 

380 conStr = self._paths_str(cons.paths) 

381 

382 if not opts: 

383 optStr = "default options" 

384 elif opts is RecordTree.ALL: 

385 optStr = "any options" 

386 else: 

387 optStr = "nondefault values for " + self._paths_str(opts.paths) 

388 

389 return "{} {} subject to {} using {} and {}.".format( 

390 dirStr, objStr, conStr, varStr, optStr) 

391 

392 def __repr__(self): 

393 return glyphs.repr2("Specification", str(self)) 

394 

395 

396# -------------------------------------- 

397__all__ = api_end(_API_START, globals())