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 >>> x = picos.RealVariable("x") 

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

140 <detached primal solution from user> 

141 >>> s.apply() 

142 >>> x.value 

143 1.0 

144 

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

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

147 

148 >>> P = picos.Problem() 

149 >>> P.minimize = x 

150 >>> P += x >= 2 

151 >>> s = P.solve(solver = "cvxopt", duals = False); s 

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

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

154 '0.83 ms' 

155 >>> P += x >= 3; s 

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

157 """ 

158 

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

160 primalStatus=SS_UNKNOWN, dualStatus=SS_UNKNOWN, 

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

162 vectorizedPrimals=False, reportedValue=None): 

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

164 

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

166 A mapping of variables to their primal solution value. 

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

168 A mapping of constraints to their dual solution value. 

169 :param picos.Problem problem: 

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

171 then the solution is "detached". 

172 :param str solver: 

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

174 :param str primalStatus: 

175 The primal solution status as reported by the solver. 

176 :param str dualStatus: 

177 The dual solution status as reported by the solver. 

178 :param str problemStatus: 

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

180 :param float searchTime: 

181 Seconds that the solution process took. 

182 :param dict info: 

183 Additional solution (meta)data. 

184 :param bool vectorizedPrimals: 

185 Whether primal solution values are given with respect to the 

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

187 :param float reportedValue: 

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

189 """ 

190 from ..expressions import BaseVariable 

191 from ..constraints import Constraint 

192 from .problem import Problem 

193 

194 if primals is None: 

195 primals = {} 

196 

197 if duals is None: 

198 duals = {} 

199 

200 if info is None: 

201 info = {} 

202 

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

204 _check_type(primals, dict) 

205 _check_type(duals, dict) 

206 _check_type(problem, None, Problem) 

207 _check_type(solver, str) 

208 _check_type(primalStatus, str) 

209 _check_type(dualStatus, str) 

210 _check_type(problemStatus, str) 

211 _check_type(searchTime, float) 

212 _check_type(info, dict) 

213 _check_type(vectorizedPrimals, bool) 

214 _check_type(reportedValue, None, float) 

215 

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

217 if not isinstance(variable, BaseVariable): 

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

219 "Solution.__init__ must be variables.") 

220 

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

222 if not isinstance(constraint, Constraint): 

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

224 "Solution.__init__ must be constraints.") 

225 

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

227 if primals and duals: 

228 if primalStatus == dualStatus: 

229 claimedStatus = primalStatus 

230 else: 

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

232 primalStatus, dualStatus) 

233 elif primals: 

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

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

236 dualStatus = SS_EMPTY 

237 claimedStatus = primalStatus 

238 elif duals: 

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

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

241 primalStatus = SS_EMPTY 

242 claimedStatus = dualStatus 

243 else: 

244 primalStatus = SS_EMPTY 

245 dualStatus = SS_EMPTY 

246 claimedStatus = SS_EMPTY 

247 

248 # Infeasible problem implies infeasible primal. 

249 if problemStatus == PS_INFEASIBLE \ 

250 and primalStatus not in (SS_INFEASIBLE, SS_EMPTY): 

251 warnings.warn( 

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

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

254 format(solver), RuntimeWarning) 

255 primalStatus = SS_INFEASIBLE 

256 

257 # Unbounded problem implies infeasible dual. 

258 if problemStatus == PS_UNBOUNDED \ 

259 and dualStatus not in (SS_INFEASIBLE, SS_EMPTY): 

260 warnings.warn( 

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

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

263 format(solver), RuntimeWarning) 

264 dualStatus = SS_INFEASIBLE 

265 

266 # Optimal solution implies feasible problem. 

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

268 warnings.warn( 

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

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

271 .format(solver), RuntimeWarning) 

272 problemStatus = PS_FEASIBLE 

273 

274 self.problem = problem 

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

276 

277 self.solver = solver 

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

279 

280 self.searchTime = searchTime 

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

282 

283 self.primals = primals 

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

285 

286 self.duals = duals 

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

288 

289 self.info = info 

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

291 

292 self.lastStatus = VS_UNKNOWN 

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

294 applied to the problem.""" 

295 

296 self.primalStatus = primalStatus 

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

298 

299 self.dualStatus = dualStatus 

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

301 

302 self.claimedStatus = claimedStatus 

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

304 

305 self.problemStatus = problemStatus 

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

307 

308 self.vectorizedPrimals = vectorizedPrimals 

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

310 

311 self.reportedValue = reportedValue 

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

313 

314 def _status_of_problem(self, problem): 

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

316 

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

318 """ 

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

320 return VS_EMPTY 

321 

322 try: 

323 isFeasible = problem.check_current_value_feasibility()[0] 

324 except LookupError: 

325 return VS_INCOMPLETE 

326 except Exception: 

327 return VS_UNKNOWN 

328 

329 if isFeasible: 

330 return VS_PRIMAL_FEASIBLE if self.duals else VS_FEASIBLE 

331 else: 

332 return VS_PRIMAL_INFEASIBLE if self.duals else VS_INFEASIBLE 

333 

334 @property 

335 def status(self): 

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

337 

338 .. warning:: 

339 

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

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

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

343 the solution's lastStatus attribute instead. 

344 """ 

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

346 if not self.problem: 

347 return VS_DETACHED_EMPTY 

348 else: 

349 return VS_EMPTY 

350 elif not self.problem: 

351 return VS_DETACHED 

352 elif not self.primals: 

353 return VS_UNKNOWN 

354 

355 problemCopy = self.problem.copy() 

356 

357 try: 

358 self.apply(toProblem=problemCopy) 

359 except RuntimeError: 

360 return VS_OUTDATED 

361 

362 return self._status_of_problem(problemCopy) 

363 

364 @property 

365 def value(self): 

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

367 

368 .. warning:: 

369 

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

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

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

373 that problem instead. 

374 """ 

375 if not self.problem: 

376 raise RuntimeError( 

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

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

379 

380 problemCopy = self.problem.copy() 

381 

382 self.apply(toProblem=problemCopy) 

383 

384 return problemCopy.value 

385 

386 @property 

387 def reported_value(self): 

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

389 return self.reportedValue 

390 

391 def __str__(self): 

392 verifiedStatus = self.status 

393 lastStatus = self.lastStatus 

394 claimedStatus = self.claimedStatus 

395 problemStatus = self.problemStatus 

396 

397 if self.primals and self.duals: 

398 solutionType = "solution pair" 

399 elif self.primals: 

400 solutionType = "primal solution" 

401 elif self.duals: 

402 solutionType = "dual solution" 

403 else: 

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

405 

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

407 printLastStatus = lastStatus != VS_UNKNOWN and \ 

408 verifiedStatus != lastStatus 

409 

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

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

412 printClaimedStatus = \ 

413 claimedStatus not in (verifiedStatus, SS_UNKNOWN) and \ 

414 problemStatus not in (PS_INFEASIBLE, PS_UNBOUNDED) 

415 

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

417 printProblemStatus = \ 

418 problemStatus not in (PS_UNKNOWN, PS_FEASIBLE) 

419 

420 if printLastStatus and printClaimedStatus: 

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

422 lastStatus, claimedStatus) 

423 elif printLastStatus: 

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

425 elif printClaimedStatus: 

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

427 else: 

428 unverifiedStatus = "" 

429 

430 if printProblemStatus: 

431 unverifiedStatus += \ 

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

433 

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

435 unverifiedStatus, self.solver) 

436 

437 def __repr__(self): 

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

439 

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

441 snapshotStatus=False): 

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

443 

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

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

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

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

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

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

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

451 variables and constraints instead. 

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

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

454 it applies a solution returned by a solver. 

455 """ 

456 if toProblem: 

457 if primals: 

458 thePrimals = {} 

459 try: 

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

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

462 except KeyError as error: 

463 raise RuntimeError( 

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

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

466 from error 

467 

468 if duals: 

469 theDuals = {} 

470 try: 

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

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

473 except KeyError as error: 

474 raise RuntimeError( 

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

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

477 from error 

478 else: 

479 thePrimals = self.primals 

480 theDuals = self.duals 

481 

482 if primals: 

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

484 if primal is None and not clearOnNone: 

485 continue 

486 

487 if self.vectorizedPrimals: 

488 variable.internal_value = primal 

489 else: 

490 variable.value = primal 

491 

492 if duals: 

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

494 if dual is None and not clearOnNone: 

495 continue 

496 constraint.dual = dual 

497 

498 if snapshotStatus: 

499 if toProblem: 

500 self.lastStatus = self._status_of_problem(toProblem) 

501 elif self.problem: 

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

503 else: # detached solution 

504 self.lastStatus = self.status 

505 

506 if toProblem: 

507 toProblem._last_solution = self 

508 elif self.problem: 

509 self.problem._last_solution = self 

510 

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

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

513 

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

515 ID, respectively) are kept. 

516 

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

518 of the copy to match the new problem. 

519 """ 

520 self.problem = problem 

521 

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

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

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

525 if variable.name in problem.variables: 

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

527 

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

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

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

531 if constraint.id in problem.constraints: 

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

533 

534 # Update the last (verified) status. 

535 if snapshotStatus: 

536 self.lastStatus = problem.status 

537 else: 

538 self.lastStatus = VS_UNKNOWN 

539 

540 

541# -------------------------------------- 

542__all__ = api_end(_API_START, globals())