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-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 self.objective.clstype is expressions.QuadraticExpression: 

177 direction = self.direction 

178 subtype = self.objective.subtype 

179 

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

181 

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

183 return True 

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

185 return True 

186 

187 return False 

188 

189 def __str__(self): 

190 dirStr = self.direction.capitalize() 

191 objStr = str(self.objective) 

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

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

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

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

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

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

198 

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

200 dirStr, objStr, 

201 conStr if conStr else "no constraints", 

202 varStr if varStr else "no variables", 

203 optStr if optStr else "default options") 

204 

205 def __repr__(self): 

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

207 

208 @classmethod 

209 def from_problem(cls, problem): 

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

211 return cls(chain( 

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

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

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

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

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

217 

218 @classmethod 

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

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

221 

222 :param str obj_dir: 

223 Objective direction. 

224 

225 :param obj_func: 

226 Detailed objective function type. 

227 

228 :parm list(tuple) vars: 

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

230 

231 :parm list(tuple) cons: 

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

233 

234 :param list(str) nd_opts: 

235 A dictionary mapping option names to nondefault values. 

236 """ 

237 return cls(chain( 

238 (("dir", obj_dir, None), 

239 ("obj", obj_func, None)), 

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

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

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

243 

244 def with_extra_options(self, **extra_options): 

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

246 # Determine the new option set. 

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

248 

249 # Delete old nondefault options and set new ones. 

250 return self.updated(chain( 

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

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

253 )) 

254 

255 @cached_property 

256 def size(self): 

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

258 num_vars = 0 

259 num_cons = 0 

260 

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

262 num_vars += dim 

263 

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

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

266 

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

268 

269 @property 

270 def cost(self): 

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

272 

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

274 """ 

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

276 

277 

278class Specification: 

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

280 

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

282 nondefault_options=None): 

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

284 

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

286 """ 

287 self._objs = objectives 

288 

289 self._tree = RecordTree(chain( 

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

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

292 

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

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

295 

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

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

298 

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

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

301 )) 

302 

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

304 # why the footprint does not match the specification. 

305 def __contains__(self, footprint): 

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

307 if not isinstance(footprint, Footprint): 

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

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

310 .format(type(footprint).__name__)) 

311 

312 if self._objs is not None: 

313 obj = footprint.objective.clstype 

314 

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

316 return False 

317 

318 if not footprint << self._tree: 

319 return False 

320 

321 return True 

322 

323 def mismatch_reason(self, footprint): 

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

325 if self._objs is not None: 

326 obj = footprint.objective.clstype 

327 

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

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

330 

331 mismatch = footprint.mismatch(self._tree) 

332 

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

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

335 

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

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

338 

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

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

341 

342 assert footprint << self._tree 

343 

344 return "No reason." 

345 

346 @staticmethod 

347 def _paths_str(paths): 

348 return ", ".join( 

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

350 for path in paths) 

351 

352 def __str__(self): 

353 dirStr = "Optimize" 

354 

355 if self._objs is None: 

356 objStr = "any objective" 

357 elif not self._objs: 

358 objStr = "no objective" 

359 else: 

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

361 

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

363 

364 if not vars: 

365 varStr = "no variables" 

366 elif vars is RecordTree.ALL: 

367 varStr = "any variables" 

368 else: 

369 varStr = self._paths_str(vars.paths) 

370 

371 if not cons: 

372 conStr = "no constraint" 

373 elif cons is RecordTree.ALL: 

374 conStr = "any constraint" 

375 else: 

376 conStr = self._paths_str(cons.paths) 

377 

378 if not opts: 

379 optStr = "default options" 

380 elif opts is RecordTree.ALL: 

381 optStr = "any options" 

382 else: 

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

384 

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

386 dirStr, objStr, conStr, varStr, optStr) 

387 

388 def __repr__(self): 

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

390 

391 

392# -------------------------------------- 

393__all__ = api_end(_API_START, globals())