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

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

4# This file is part of PICOS.

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

19"""Optimization problem description classes.

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

25import math

26from inspect import isclass

27from itertools import chain

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.

36_API_START = api_start(globals())

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

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.

54class Footprint(RecordTree):

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

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

59 def __init__(self, recordsOrDict):

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

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)

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

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

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

97 .format(path, value))

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