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

20 

21import warnings 

22 

23from .. import glyphs 

24from ..apidoc import api_end, api_start 

25 

26_API_START = api_start(globals()) 

27# ------------------------------- 

28 

29 

30# Solution status strings, as verified by PICOS. 

31VS_UNKNOWN = "unverified" 

32"""PICOS failed to verify the solution.""" 

33 

34VS_DETACHED = "detached" 

35"""The solution is not attached to a problem (it was given by the user).""" 

36 

37VS_EMPTY = "empty" 

38"""The solution is empty; there are neither primals nor duals.""" 

39 

40VS_DETACHED_EMPTY = "detached empty" 

41"""The solution is both detached and empty.""" 

42 

43VS_OUTDATED = "outdated" 

44"""The solution does not fit the problem formulation any more. 

45 

46Variables or constraints were removed from the problem.""" 

47 

48VS_INCOMPLETE = "incomplete" 

49"""The primal (dual) solution does not concern all variables (constraints).""" 

50 

51VS_FEASIBLE = "feasible" 

52"""The solution is primal feasible; there is no dual solution.""" 

53 

54VS_INFEASIBLE = "infeasible" 

55"""The solution is primal infeasible; there is no dual solution.""" 

56 

57VS_PRIMAL_FEASIBLE = "primal feasible" 

58"""The solution is primal feasible; a dual solution was not verified.""" 

59 

60VS_PRIMAL_INFEASIBLE = "primal infeasible" 

61"""The solution is primal infeasible; a dual solution was not verified.""" 

62 

63 

64# Primal or dual solution (or search) status strings, as claimed by the solver. 

65SS_UNKNOWN = "unknown" 

66"""The solver did not make a clear claim about the solution status.""" 

67 

68SS_EMPTY = "empty" 

69"""The solver claims not to have produced a solution.""" 

70 

71SS_OPTIMAL = "optimal" 

72"""The solution is optimal.""" 

73 

74SS_FEASIBLE = "feasible" 

75"""The solution is feasible.""" 

76 

77SS_INFEASIBLE = "infeasible" 

78"""No feasible solution exists. 

79 

80In the case of a primal solution, the problem is infeasible. In the case of a 

81dual solution, the problem is unbounded. 

82""" 

83 

84SS_PREMATURE = "premature" 

85"""The search was prematurely terminated due to some limit.""" 

86 

87SS_FAILURE = "failure" 

88"""The search was termined due to a solver failure.""" 

89 

90 

91# Problem status strings, as claimed by the solver. 

92PS_UNKNOWN = "unknown" 

93"""The solver did not make a clear claim about the problem status.""" 

94 

95PS_FEASIBLE = "feasible" 

96"""The problem is primal (and dual) feasible and bounded.""" 

97 

98PS_INFEASIBLE = "infeasible" 

99"""The problem is primal infeasible (and dual unbounded or infeasible).""" 

100 

101PS_UNBOUNDED = "unbounded" 

102"""The problem is primal unbounded (and dual infeasible).""" 

103 

104PS_INF_OR_UNB = "infeasible or unbounded" 

105"""The problem is primal infeasible or unbounded. 

106 

107Being unbounded is usually infered from being dual infeasible.""" 

108 

109PS_UNSTABLE = "unstable" 

110"""The problem was found numerically unstable or otherwise hard to handle.""" 

111 

112PS_ILLPOSED = "illposed" 

113"""The problem was found to be in a state that is not amenable to solution.""" 

114 

115 

116def _check_type(argument, *types): 

117 """Enforce the type of a method or function argument.""" 

118 for type_ in types: 

119 if type_ is None: 

120 type_ = type(None) 

121 if isinstance(argument, type_): 

122 return 

123 

124 raise TypeError("An argument is of type '{}' but must be instance of {}." 

125 .format(type(argument).__name__, " or ".join("'{}'".format(t.__name__) 

126 for t in types))) 

127 

128 

129# TODO: Make all public fields use snake_case, ensure backwards compatibility. 

130class Solution: 

131 """Assignment of primal and dual values to variables and constraints. 

132 

133 Instances are usually returned by a solver (and thus bound to a 

134 :class:`problem <picos.Problem>` instance), but may be manually created by 

135 the user: 

136 

137 >>> import picos 

138 >>> P = picos.Problem() 

139 >>> x = P.add_variable("x") 

140 >>> s = picos.Solution({x: 1}); s 

141 <detached primal solution from user> 

142 >>> s.apply() 

143 >>> x.value 

144 1.0 

145 

146 If the solution was created by a solver (or attached to a problem via 

147 :func:`attach_to`), more information is available: 

148 

149 >>> C1 = P.add_constraint(x >= 2) 

150 >>> s = P.minimize(x, solver = "cvxopt", duals = False); s 

151 <feasible primal solution (claimed optimal) from cvxopt> 

152 >>> "{:.2f} ms".format(1000.0 * s.searchTime) #doctest: +SKIP 

153 '0.83 ms' 

154 >>> C2 = P.add_constraint(x >= 3); s 

155 <infeasible primal solution (was feasible and claimed optimal) from cvxopt> 

156 """ 

157 

158 def __init__(self, primals, duals=None, problem=None, solver="user", 

159 primalStatus=SS_UNKNOWN, dualStatus=SS_UNKNOWN, 

160 problemStatus=PS_UNKNOWN, searchTime=0.0, info=None, 

161 vectorizedPrimals=False, reportedValue=None): 

162 """Create a solution to an optimization problem. 

163 

164 :param dict(picos.expressions.BaseVariable, object) primals: 

165 A mapping of variables to their primal solution value. 

166 :param dict(picos.constraints.Constraint, object) duals: 

167 A mapping of constraints to their dual solution value. 

168 :param picos.Problem problem: 

169 The problem that was solved to create the solution. If ``None``, 

170 then the solution is "detached". 

171 :param str solver: 

172 The name of the solver that was used to create the solution. 

173 :param str primalStatus: 

174 The primal solution status as reported by the solver. 

175 :param str dualStatus: 

176 The dual solution status as reported by the solver. 

177 :param str problemStatus: 

178 The state of the problem as reported by the solver. 

179 :param float searchTime: 

180 Seconds that the solution process took. 

181 :param dict info: 

182 Additional solution (meta)data. 

183 :param bool vectorizedPrimals: 

184 Whether primal solution values are given with respect to the 

185 variable's special vectorization format as used by PICOS internally. 

186 :param float reportedValue: 

187 Objective value of the solution as reported by the solver. 

188 """ 

189 from ..expressions import BaseVariable 

190 from ..constraints import Constraint 

191 from .problem import Problem 

192 

193 if primals is None: 

194 primals = {} 

195 

196 if duals is None: 

197 duals = {} 

198 

199 if info is None: 

200 info = {} 

201 

202 # Be strict about the arguments as they are handed to the user. 

203 _check_type(primals, dict) 

204 _check_type(duals, dict) 

205 _check_type(problem, None, Problem) 

206 _check_type(solver, str) 

207 _check_type(primalStatus, str) 

208 _check_type(dualStatus, str) 

209 _check_type(problemStatus, str) 

210 _check_type(searchTime, float) 

211 _check_type(info, dict) 

212 _check_type(vectorizedPrimals, bool) 

213 _check_type(reportedValue, None, float) 

214 

215 for variable, _ in primals.items(): 

216 if not isinstance(variable, BaseVariable): 

217 raise TypeError("They keys in the primals argument of " 

218 "Solution.__init__ must be variables.") 

219 

220 for constraint, _ in duals.items(): 

221 if not isinstance(constraint, Constraint): 

222 raise TypeError("They keys in the duals argument of " 

223 "Solution.__init__ must be constraints.") 

224 

225 # Derive a "claimed status" from the claimed primal and dual states. 

226 if primals and duals: 

227 if primalStatus == dualStatus: 

228 claimedStatus = primalStatus 

229 else: 

230 claimedStatus = "primal {} and dual {}".format( 

231 primalStatus, dualStatus) 

232 elif primals: 

233 # Do not warn about correctingdualStatus, because the solver might 

234 # have produced primals but PICOS did not read them. 

235 dualStatus = SS_EMPTY 

236 claimedStatus = primalStatus 

237 elif duals: 

238 # Do not warn about correcting primalStatus, because the solver 

239 # might have produced duals but PICOS did not read them. 

240 primalStatus = SS_EMPTY 

241 claimedStatus = dualStatus 

242 else: 

243 primalStatus = SS_EMPTY 

244 dualStatus = SS_EMPTY 

245 claimedStatus = SS_EMPTY 

246 

247 # Infeasible problem implies infeasible primal. 

248 if problemStatus == PS_INFEASIBLE \ 

249 and primalStatus not in (SS_INFEASIBLE, SS_EMPTY): 

250 warnings.warn( 

251 "{} claims that a problem is infeasible but does not say the " 

252 "same about the nonempty primal solution. Correcting this.". 

253 format(solver), RuntimeWarning) 

254 primalStatus = SS_INFEASIBLE 

255 

256 # Unbounded problem implies infeasible dual. 

257 if problemStatus == PS_UNBOUNDED \ 

258 and dualStatus not in (SS_INFEASIBLE, SS_EMPTY): 

259 warnings.warn( 

260 "{} claims that a problem is unbounded but does not say that " 

261 "the nonempty dual solution is infeasible. Correcting this.". 

262 format(solver), RuntimeWarning) 

263 dualStatus = SS_INFEASIBLE 

264 

265 # Optimal solution implies feasible problem. 

266 if claimedStatus == SS_OPTIMAL and problemStatus != PS_FEASIBLE: 

267 warnings.warn( 

268 "{} claims to have found an optimal solution but does not say " 

269 " that the problem is feasible. Correcting this." 

270 .format(solver), RuntimeWarning) 

271 problemStatus = PS_FEASIBLE 

272 

273 self.problem = problem 

274 """The problem that was solved to produce the solution.""" 

275 

276 self.solver = solver 

277 """The solver that produced the solution.""" 

278 

279 self.searchTime = searchTime 

280 """Time in seconds that the solution search took.""" 

281 

282 self.primals = primals 

283 """The primal solution values returned by the solver.""" 

284 

285 self.duals = duals 

286 """The dual solution values returned by the solver.""" 

287 

288 self.info = info 

289 """Additional information provided by the solver.""" 

290 

291 self.lastStatus = VS_UNKNOWN 

292 """The solution status as verified by PICOS when the solution was 

293 applied to the problem.""" 

294 

295 self.primalStatus = primalStatus 

296 """The primal solution status as claimed by the solver.""" 

297 

298 self.dualStatus = dualStatus 

299 """The dual solution status as claimed by the solver.""" 

300 

301 self.claimedStatus = claimedStatus 

302 """The primal and dual solution status as claimed by the solver.""" 

303 

304 self.problemStatus = problemStatus 

305 """The problem status as claimed by the solver.""" 

306 

307 self.vectorizedPrimals = vectorizedPrimals 

308 """Whether primal values refer to variables' special vectorizations.""" 

309 

310 self.reportedValue = reportedValue 

311 """The objective value of the solution as reported by the solver.""" 

312 

313 def _status_of_problem(self, problem): 

314 """Retrieve the problem's verified solution status. 

315 

316 Requires that the solution has just been applied to the problem. 

317 """ 

318 if not self.primals and not self.duals: 

319 return VS_EMPTY 

320 

321 try: 

322 isFeasible = problem.check_current_value_feasibility()[0] 

323 except LookupError: 

324 return VS_INCOMPLETE 

325 except Exception: 

326 return VS_UNKNOWN 

327 

328 if isFeasible: 

329 return VS_PRIMAL_FEASIBLE if self.duals else VS_FEASIBLE 

330 else: 

331 return VS_PRIMAL_INFEASIBLE if self.duals else VS_INFEASIBLE 

332 

333 @property 

334 def status(self): 

335 """The current solution status as verified by PICOS. 

336 

337 .. warning:: 

338 

339 Accessing this attribute is expensive for large problems as a copy 

340 of the problem needs to be created and valued. If you have just 

341 applied the solution to a :class:`problem <picos.Problem>`, query 

342 the solution's lastStatus attribute instead. 

343 """ 

344 if not self.primals and not self.duals: 

345 if not self.problem: 

346 return VS_DETACHED_EMPTY 

347 else: 

348 return VS_EMPTY 

349 elif not self.problem: 

350 return VS_DETACHED 

351 elif not self.primals: 

352 return VS_UNKNOWN 

353 

354 problemCopy = self.problem.copy() 

355 

356 try: 

357 self.apply(toProblem=problemCopy) 

358 except RuntimeError: 

359 return VS_OUTDATED 

360 

361 return self._status_of_problem(problemCopy) 

362 

363 @property 

364 def value(self): 

365 """The objective value of the solution as computed by PICOS. 

366 

367 .. warning:: 

368 

369 Accessing this attribute is expensive for large problems as a copy 

370 of the problem needs to be created and valued. If you have just 

371 applied the solution to a :class:`problem <picos.Problem>`, query 

372 that problem instead. 

373 """ 

374 if not self.problem: 

375 raise RuntimeError( 

376 "Cannot compute the objective value of a detached solution. " 

377 "Use attach_to to assign the solution to a problem.") 

378 

379 problemCopy = self.problem.copy() 

380 

381 self.apply(toProblem=problemCopy) 

382 

383 return problemCopy.value 

384 

385 @property 

386 def reported_value(self): 

387 """The objective value as reported by the solver, or :obj:`None`.""" 

388 return self.reportedValue 

389 

390 def __str__(self): 

391 verifiedStatus = self.status 

392 lastStatus = self.lastStatus 

393 claimedStatus = self.claimedStatus 

394 problemStatus = self.problemStatus 

395 

396 if self.primals and self.duals: 

397 solutionType = "solution pair" 

398 elif self.primals: 

399 solutionType = "primal solution" 

400 elif self.duals: 

401 solutionType = "dual solution" 

402 else: 

403 solutionType = "solution" # "(detached) empty solution" 

404 

405 # Print the last status if it is known and differs from the current one. 

406 printLastStatus = lastStatus != VS_UNKNOWN and \ 

407 verifiedStatus != lastStatus 

408 

409 # Print the claimed status only if it differs from the initial verified 

410 # one is not implied by a problem status that will be printed. 

411 printClaimedStatus = \ 

412 claimedStatus not in (verifiedStatus, SS_UNKNOWN) and \ 

413 problemStatus not in (PS_INFEASIBLE, PS_UNBOUNDED) 

414 

415 # Print the problem status only if it is interesting. 

416 printProblemStatus = \ 

417 problemStatus not in (PS_UNKNOWN, PS_FEASIBLE) 

418 

419 if printLastStatus and printClaimedStatus: 

420 unverifiedStatus = " (was {} and claimed {})".format( 

421 lastStatus, claimedStatus) 

422 elif printLastStatus: 

423 unverifiedStatus = " (was {})".format(lastStatus) 

424 elif printClaimedStatus: 

425 unverifiedStatus = " (claimed {})".format(claimedStatus) 

426 else: 

427 unverifiedStatus = "" 

428 

429 if printProblemStatus: 

430 unverifiedStatus += \ 

431 " for a problem claimed {}".format(problemStatus) 

432 

433 return "{} {}{} from {}".format(verifiedStatus, solutionType, 

434 unverifiedStatus, self.solver) 

435 

436 def __repr__(self): 

437 return glyphs.repr1(self.__str__()) 

438 

439 def apply(self, primals=True, duals=True, clearOnNone=True, toProblem=None, 

440 snapshotStatus=False): 

441 """Apply the solution to the involved variables and constraints. 

442 

443 :param bool primals: Whether to apply the primal solution. 

444 :param bool duals: Whether to apply the dual solution. 

445 :param bool clearOnNone: Whether to clear the value of a variable or 

446 constraint if the solution has it set to None. This could happen in 

447 case of an error or shortcoming of the solver or PICOS. 

448 :param picos.Problem toProblem: If set to a copy of the problem that was 

449 used to produce the solution, will apply the solution to that copy's 

450 variables and constraints instead. 

451 :param bool snapshotStatus: Whether to update the lastStatus attribute 

452 with the new (verified) solution status. PICOS enables this whenever 

453 it applies a solution returned by a solver. 

454 """ 

455 if toProblem: 

456 if primals: 

457 thePrimals = {} 

458 try: 

459 for variable, primal in self.primals.items(): 

460 thePrimals[toProblem.variables[variable.name]] = primal 

461 except KeyError as error: 

462 raise RuntimeError( 

463 "Cannot apply solution to specified problem as not all " 

464 "variables for which primal values exist were found.") \ 

465 from error 

466 

467 if duals: 

468 theDuals = {} 

469 try: 

470 for constraint, dual in self.duals.items(): 

471 theDuals[toProblem.constraints[constraint.id]] = dual 

472 except KeyError as error: 

473 raise RuntimeError( 

474 "Cannot apply solution to specified problem as not all " 

475 "constraints for which dual values exist were found.") \ 

476 from error 

477 else: 

478 thePrimals = self.primals 

479 theDuals = self.duals 

480 

481 if primals: 

482 for variable, primal in thePrimals.items(): 

483 if primal is None and not clearOnNone: 

484 continue 

485 

486 if self.vectorizedPrimals: 

487 variable.internal_value = primal 

488 else: 

489 variable.value = primal 

490 

491 if duals: 

492 for constraint, dual in theDuals.items(): 

493 if dual is None and not clearOnNone: 

494 continue 

495 constraint.dual = dual 

496 

497 if snapshotStatus: 

498 if toProblem: 

499 self.lastStatus = self._status_of_problem(toProblem) 

500 elif self.problem: 

501 self.lastStatus = self._status_of_problem(self.problem) 

502 else: # detached solution 

503 self.lastStatus = self.status 

504 

505 if toProblem: 

506 toProblem._last_solution = self 

507 elif self.problem: 

508 self.problem._last_solution = self 

509 

510 def attach_to(self, problem, snapshotStatus=False): 

511 """Attach (or move) the solution to a problem. 

512 

513 Only variables and constraints that exist on the problem (same name or 

514 ID, respectively) are kept. 

515 

516 :param bool snapshotStatus: Whether to set the lastStatus attribute 

517 of the copy to match the new problem. 

518 """ 

519 self.problem = problem 

520 

521 # Find variables of same name in the problem and assign primals. 

522 oldPrimals, self.primals = self.primals, {} 

523 for variable, primal in oldPrimals.items(): 

524 if variable.name in problem.variables: 

525 self.primals[problem.variables[variable.name]] = primal 

526 

527 # Find constraints of same ID in the problem and assign duals. 

528 oldDuals, self.duals = self.duals, {} 

529 for constraint, dual in oldDuals.items(): 

530 if constraint.id in problem.constraints: 

531 self.duals[problem.constraints[constraint.id]] = dual 

532 

533 # Update the last (verified) status. 

534 if snapshotStatus: 

535 self.lastStatus = problem.status 

536 else: 

537 self.lastStatus = VS_UNKNOWN 

538 

539 

540# -------------------------------------- 

541__all__ = api_end(_API_START, globals())