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# Based on the original picos.expressions module by Guillaume Sagnol. 

4# 

5# This file is part of PICOS. 

6# 

7# PICOS is free software: you can redistribute it and/or modify it under the 

8# terms of the GNU General Public License as published by the Free Software 

9# Foundation, either version 3 of the License, or (at your option) any later 

10# version. 

11# 

12# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY 

13# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 

14# A PARTICULAR PURPOSE. See the GNU General Public License for more details. 

15# 

16# You should have received a copy of the GNU General Public License along with 

17# this program. If not, see <http://www.gnu.org/licenses/>. 

18# ------------------------------------------------------------------------------ 

19 

20"""Implements all mathematical variable types and their base class.""" 

21 

22from collections import namedtuple 

23 

24import cvxopt 

25 

26from .. import glyphs, settings 

27from ..apidoc import api_end, api_start 

28from ..caching import cached_property 

29from ..containers import DetailedType 

30from .data import cvxopt_equals, cvxopt_maxdiff, load_shape 

31from .exp_affine import AffineExpression, ComplexAffineExpression 

32from .mutable import Mutable 

33from .vectorizations import (ComplexVectorization, FullVectorization, 

34 HermitianVectorization, 

35 LowerTriangularVectorization, 

36 SkewSymmetricVectorization, 

37 SymmetricVectorization, 

38 UpperTriangularVectorization) 

39 

40_API_START = api_start(globals()) 

41# ------------------------------- 

42 

43 

44class VariableType(DetailedType): 

45 """The detailed type of a variable for predicting reformulation outcomes.""" 

46 

47 pass 

48 

49 

50class BaseVariable(Mutable): 

51 """Primary base class for all variable types. 

52 

53 Variables need to inherit this class with priority (first class listed) and 

54 :class:`~.exp_affine.ComplexAffineExpression` or 

55 :class:`~.exp_affine.AffineExpression` without priority. 

56 """ 

57 

58 # TODO: Document changed variable bound behavior: Only full bounds can be 

59 # given but they may contain (-)float("inf"). 

60 def __init__(self, name, vectorization, lower=None, upper=None): 

61 """Perform basic initialization for :class:`BaseVariable` instances. 

62 

63 :param str name: 

64 Name of the variable. A leading `"__"` denotes a private variable 

65 and is replaced by a sequence containing the variable's unique ID. 

66 

67 :param vectorization: 

68 Vectorization format used to store the value. 

69 :type vectorization: 

70 ~picos.expressions.vectorizations.BaseVectorization 

71 

72 :param lower: 

73 Constant lower bound on the variable. May contain ``float("-inf")`` 

74 to denote unbounded elements. 

75 

76 :param upper: 

77 Constant upper bound on the variable. May contain ``float("inf")`` 

78 to denote unbounded elements. 

79 """ 

80 Mutable.__init__(self, name, vectorization) 

81 

82 self._lower = None if lower is None else self._load_vectorized(lower) 

83 self._upper = None if upper is None else self._load_vectorized(upper) 

84 

85 def copy(self, new_name=None): 

86 """Return an independent copy of the variable.""" 

87 name = self.name if new_name is None else new_name 

88 

89 if self._lower is not None or self._upper is not None: 

90 return self.__class__(name, self.shape, self._lower, self._upper) 

91 else: 

92 return self.__class__(name, self.shape) 

93 

94 VarSubtype = namedtuple("VarSubtype", ("dim", "bnd")) 

95 

96 @classmethod 

97 def make_var_type(cls, *args, **kwargs): 

98 """Create a detailed variable type from subtype parameters. 

99 

100 See also :attr:`var_type`. 

101 """ 

102 return VariableType(cls, cls.VarSubtype(*args, **kwargs)) 

103 

104 @property 

105 def var_subtype(self): 

106 """The subtype part of the detailed variable type. 

107 

108 See also :attr:`var_type`. 

109 """ 

110 return self.VarSubtype(self.dim, self.num_bounds) 

111 

112 @property 

113 def var_type(self): 

114 """The detailed variable type. 

115 

116 This intentionally does not override 

117 :meth:`Expression.type <.expression.Expression.type>` so that the 

118 variable still behaves as the affine expression that it represents when 

119 prediction constraint outcomes. 

120 """ 

121 return VariableType(self.__class__, self.var_subtype) 

122 

123 @cached_property 

124 def long_string(self): 

125 """Long string representation for printing a :meth:`~picos.Problem`.""" 

126 lower, upper = self.bound_dicts 

127 if lower and upper: 

128 bound_str = " (clamped)" 

129 elif lower: 

130 bound_str = " (bounded below)" 

131 elif upper: 

132 bound_str = " (bounded above)" 

133 else: 

134 bound_str = "" 

135 

136 return "{}{}".format(super(BaseVariable, self).long_string, bound_str) 

137 

138 @cached_property 

139 def bound_dicts(self): 

140 """Variable bounds as a pair of mappings from index to scalar bound. 

141 

142 The indices and bound values are with respect to the internal 

143 representation of the variable, whose value can be accessed with 

144 :attr:`~.mutable.Mutable.internal_value`. 

145 

146 Upper and lower bounds set to ``float("inf")`` and ``float("-inf")`` 

147 on variable creation, respectively, are not included. 

148 """ 

149 posinf = float("+inf") 

150 neginf = float("-inf") 

151 

152 if self._lower is None: 

153 lower = {} 

154 else: 

155 lower = {i: self._lower[i] for i in range(self.dim) 

156 if self._lower[i] != neginf} 

157 

158 if self._upper is None: 

159 upper = {} 

160 else: 

161 upper = {i: self._upper[i] for i in range(self.dim) 

162 if self._upper[i] != posinf} 

163 

164 return (lower, upper) 

165 

166 @property 

167 def num_bounds(self): 

168 """Number of scalar bounds associated with the variable.""" 

169 lower, upper = self.bound_dicts 

170 return len(lower) + len(upper) 

171 

172 @cached_property 

173 def bound_constraint(self): 

174 """The variable bounds as a PICOS constraint, or :obj:`None`.""" 

175 lower, upper = self.bound_dicts 

176 

177 I, J, V, b = [], [], [], [] 

178 

179 for i, bound in upper.items(): 

180 I.append(i) 

181 J.append(i) 

182 V.append(1.0) 

183 b.append(bound) 

184 

185 offset = len(I) 

186 

187 for i, bound in lower.items(): 

188 I.append(offset + i) 

189 J.append(i) 

190 V.append(-1.0) 

191 b.append(-bound) 

192 

193 if not I: 

194 return None 

195 

196 A = cvxopt.spmatrix(V, I, J, size=(len(I), self.dim), tc="d") 

197 

198 Ax = AffineExpression(string=glyphs.Fn("bnd_con_lhs")(self.name), 

199 shape=len(I), coefficients={self: A}) 

200 

201 return Ax <= b 

202 

203 

204class RealVariable(BaseVariable, AffineExpression): 

205 """A real-valued variable.""" 

206 

207 def __init__(self, name, shape=(1, 1), lower=None, upper=None): 

208 """Create a :class:`RealVariable`. 

209 

210 :param str name: The variable's name, used for both string description 

211 and identification. 

212 :param shape: The shape of a vector or matrix variable. 

213 :type shape: int or tuple or list 

214 :param lower: Constant lower bound on the variable. May contain 

215 ``float("-inf")`` to denote unbounded elements. 

216 :param upper: Constant upper bound on the variable. May contain 

217 ``float("inf")`` to denote unbounded elements. 

218 """ 

219 shape = load_shape(shape) 

220 vec = FullVectorization(shape) 

221 BaseVariable.__init__(self, name, vec, lower, upper) 

222 AffineExpression.__init__(self, self.name, shape, {self: vec.identity}) 

223 

224 @classmethod 

225 def _get_type_string_base(cls): 

226 return "Real Variable" 

227 

228 

229class IntegerVariable(BaseVariable, AffineExpression): 

230 """An integer-valued variable.""" 

231 

232 def __init__(self, name, shape=(1, 1), lower=None, upper=None): 

233 """Create an :class:`IntegerVariable`. 

234 

235 :param str name: The variable's name, used for both string description 

236 and identification. 

237 :param shape: The shape of a vector or matrix variable. 

238 :type shape: int or tuple or list 

239 :param lower: Constant lower bound on the variable. May contain 

240 ``float("-inf")`` to denote unbounded elements. 

241 :param upper: Constant upper bound on the variable. May contain 

242 ``float("inf")`` to denote unbounded elements. 

243 """ 

244 shape = load_shape(shape) 

245 vec = FullVectorization(shape) 

246 BaseVariable.__init__(self, name, vec, lower, upper) 

247 AffineExpression.__init__(self, self.name, shape, {self: vec.identity}) 

248 

249 @classmethod 

250 def _get_type_string_base(cls): 

251 return "Integer Variable" 

252 

253 def _check_internal_value(self, value): 

254 fltData = list(value) 

255 

256 if not fltData: 

257 return # All elements are exactly zero. 

258 

259 intData = cvxopt.matrix([round(x) for x in fltData]) 

260 fltData = cvxopt.matrix(fltData) 

261 

262 if not cvxopt_equals(intData, fltData, 

263 absTol=settings.ABSOLUTE_INTEGRALITY_TOLERANCE): 

264 raise ValueError("Data is not near-integral with absolute tolerance" 

265 " {:.1e}: Largest difference is {:.1e}.".format( 

266 settings.ABSOLUTE_INTEGRALITY_TOLERANCE, 

267 cvxopt_maxdiff(intData, fltData))) 

268 

269 

270class BinaryVariable(BaseVariable, AffineExpression): 

271 r"""A :math:`\{0,1\}`-valued variable.""" 

272 

273 def __init__(self, name, shape=(1, 1)): 

274 """Create a :class:`BinaryVariable`. 

275 

276 :param str name: The variable's name, used for both string description 

277 and identification. 

278 :param shape: The shape of a vector or matrix variable. 

279 :type shape: int or tuple or list 

280 """ 

281 shape = load_shape(shape) 

282 vec = FullVectorization(shape) 

283 BaseVariable.__init__(self, name, vec) 

284 AffineExpression.__init__(self, self.name, shape, {self: vec.identity}) 

285 

286 @classmethod 

287 def _get_type_string_base(cls): 

288 return "Binary Variable" 

289 

290 def _check_internal_value(self, value): 

291 fltData = list(value) 

292 

293 if not fltData: 

294 return # All elements are exactly zero. 

295 

296 binData = cvxopt.matrix([float(bool(round(x))) for x in fltData]) 

297 fltData = cvxopt.matrix(fltData) 

298 

299 if not cvxopt_equals(binData, fltData, 

300 absTol=settings.ABSOLUTE_INTEGRALITY_TOLERANCE): 

301 raise ValueError("Data is not near-binary with absolute tolerance" 

302 " {:.1e}: Largest difference is {:.1e}.".format( 

303 settings.ABSOLUTE_INTEGRALITY_TOLERANCE, 

304 cvxopt_maxdiff(binData, fltData))) 

305 

306 

307class ComplexVariable(BaseVariable, ComplexAffineExpression): 

308 """A complex-valued variable. 

309 

310 Passed to solvers as a real variable vector with :math:`2mn` entries. 

311 """ 

312 

313 def __init__(self, name, shape=(1, 1)): 

314 """Create a :class:`ComplexVariable`. 

315 

316 :param str name: The variable's name, used for both string description 

317 and identification. 

318 :param shape: The shape of a vector or matrix variable. 

319 :type shape: int or tuple or list 

320 """ 

321 shape = load_shape(shape) 

322 vec = ComplexVectorization(shape) 

323 BaseVariable.__init__(self, name, vec) 

324 ComplexAffineExpression.__init__( 

325 self, self.name, shape, {self: vec.identity}) 

326 

327 @classmethod 

328 def _get_type_string_base(cls): 

329 return "Complex Variable" 

330 

331 

332class SymmetricVariable(BaseVariable, AffineExpression): 

333 r"""A symmetric matrix variable. 

334 

335 Stored internally and passed to solvers as a symmetric vectorization with 

336 only :math:`\frac{n(n+1)}{2}` entries. 

337 """ 

338 

339 def __init__(self, name, shape=(1, 1), lower=None, upper=None): 

340 """Create a :class:`SymmetricVariable`. 

341 

342 :param str name: The variable's name, used for both string description 

343 and identification. 

344 :param shape: The shape of the matrix. 

345 :type shape: int or tuple or list 

346 :param lower: Constant lower bound on the variable. May contain 

347 ``float("-inf")`` to denote unbounded elements. 

348 :param upper: Constant upper bound on the variable. May contain 

349 ``float("inf")`` to denote unbounded elements. 

350 """ 

351 shape = load_shape(shape, squareMatrix=True) 

352 vec = SymmetricVectorization(shape) 

353 BaseVariable.__init__(self, name, vec, lower, upper) 

354 AffineExpression.__init__(self, self.name, shape, {self: vec.identity}) 

355 

356 @classmethod 

357 def _get_type_string_base(cls): 

358 return "Symmetric Variable" 

359 

360 

361class SkewSymmetricVariable(BaseVariable, AffineExpression): 

362 r"""A skew-symmetric matrix variable. 

363 

364 Stored internally and passed to solvers as a skew-symmetric vectorization 

365 with only :math:`\frac{n(n-1)}{2}` entries. 

366 """ 

367 

368 def __init__(self, name, shape=(1, 1), lower=None, upper=None): 

369 """Create a :class:`SkewSymmetricVariable`. 

370 

371 :param str name: The variable's name, used for both string description 

372 and identification. 

373 :param shape: The shape of the matrix. 

374 :type shape: int or tuple or list 

375 :param lower: Constant lower bound on the variable. May contain 

376 ``float("-inf")`` to denote unbounded elements. 

377 :param upper: Constant upper bound on the variable. May contain 

378 ``float("inf")`` to denote unbounded elements. 

379 """ 

380 shape = load_shape(shape, squareMatrix=True) 

381 vec = SkewSymmetricVectorization(shape) 

382 BaseVariable.__init__(self, name, vec, lower, upper) 

383 AffineExpression.__init__(self, self.name, shape, {self: vec.identity}) 

384 

385 @classmethod 

386 def _get_type_string_base(cls): 

387 return "Skew-symmetric Variable" 

388 

389 

390class HermitianVariable(BaseVariable, ComplexAffineExpression): 

391 r"""A hermitian matrix variable. 

392 

393 Stored internally and passed to solvers as the horizontal concatenation of 

394 a real symmetric vectorization with :math:`\frac{n(n+1)}{2}` entries and a 

395 real skew-symmetric vectorization with :math:`\frac{n(n-1)}{2}` entries, 

396 resulting in a real vector with only :math:`n^2` entries total. 

397 """ 

398 

399 def __init__(self, name, shape): 

400 """Create a :class:`HermitianVariable`. 

401 

402 :param str name: The variable's name, used for both string description 

403 and identification. 

404 :param shape: The shape of the matrix. 

405 :type shape: int or tuple or list 

406 """ 

407 shape = load_shape(shape, squareMatrix=True) 

408 vec = HermitianVectorization(shape) 

409 BaseVariable.__init__(self, name, vec) 

410 ComplexAffineExpression.__init__( 

411 self, self.name, shape, {self: vec.identity}) 

412 

413 @classmethod 

414 def _get_type_string_base(cls): 

415 return "Hermitian Variable" 

416 

417 

418class LowerTriangularVariable(BaseVariable, AffineExpression): 

419 r"""A lower triangular matrix variable. 

420 

421 Stored internally and passed to solvers as a lower triangular vectorization 

422 with only :math:`\frac{n(n+1)}{2}` entries. 

423 """ 

424 

425 def __init__(self, name, shape=(1, 1), lower=None, upper=None): 

426 """Create a :class:`LowerTriangularVariable`. 

427 

428 :param str name: The variable's name, used for both string description 

429 and identification. 

430 :param shape: The shape of the matrix. 

431 :type shape: int or tuple or list 

432 :param lower: Constant lower bound on the variable. May contain 

433 ``float("-inf")`` to denote unbounded elements. 

434 :param upper: Constant upper bound on the variable. May contain 

435 ``float("inf")`` to denote unbounded elements. 

436 """ 

437 shape = load_shape(shape, squareMatrix=True) 

438 vec = LowerTriangularVectorization(shape) 

439 BaseVariable.__init__(self, name, vec) 

440 AffineExpression.__init__(self, self.name, shape, {self: vec.identity}) 

441 

442 @classmethod 

443 def _get_type_string_base(cls): 

444 return "Lower Triangular Variable" 

445 

446 

447class UpperTriangularVariable(BaseVariable, AffineExpression): 

448 r"""An upper triangular matrix variable. 

449 

450 Stored internally and passed to solvers as an upper triangular vectorization 

451 with only :math:`\frac{n(n+1)}{2}` entries. 

452 """ 

453 

454 def __init__(self, name, shape=(1, 1), lower=None, upper=None): 

455 """Create a :class:`UpperTriangularVariable`. 

456 

457 :param str name: The variable's name, used for both string description 

458 and identification. 

459 :param shape: The shape of the matrix. 

460 :type shape: int or tuple or list 

461 :param lower: Constant lower bound on the variable. May contain 

462 ``float("-inf")`` to denote unbounded elements. 

463 :param upper: Constant upper bound on the variable. May contain 

464 ``float("inf")`` to denote unbounded elements. 

465 """ 

466 shape = load_shape(shape, squareMatrix=True) 

467 vec = UpperTriangularVectorization(shape) 

468 BaseVariable.__init__(self, name, vec) 

469 AffineExpression.__init__(self, self.name, shape, {self: vec.identity}) 

470 

471 @classmethod 

472 def _get_type_string_base(cls): 

473 return "Lower Triangular Variable" 

474 

475 

476CONTINUOUS_VARTYPES = (RealVariable, ComplexVariable, SymmetricVariable, 

477 SkewSymmetricVariable, HermitianVariable, 

478 LowerTriangularVariable, UpperTriangularVariable) 

479 

480 

481# -------------------------------------- 

482__all__ = api_end(_API_START, globals())