Coverage for picos/modeling/solution.py: 85.88%

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

21import warnings

23from .. import glyphs

24from ..apidoc import api_end, api_start

26_API_START = api_start(globals())

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

30# Solution status strings, as verified by PICOS.

31VS_UNKNOWN = "unverified"

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

34VS_DETACHED = "detached"

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

37VS_EMPTY = "empty"

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

40VS_DETACHED_EMPTY = "detached empty"

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

43VS_OUTDATED = "outdated"

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

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

48VS_INCOMPLETE = "incomplete"

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

51VS_FEASIBLE = "feasible"

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

54VS_INFEASIBLE = "infeasible"

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

57VS_PRIMAL_FEASIBLE = "primal feasible"

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

60VS_PRIMAL_INFEASIBLE = "primal infeasible"

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

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

68SS_EMPTY = "empty"

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

71SS_OPTIMAL = "optimal"

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

74SS_FEASIBLE = "feasible"

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

77SS_INFEASIBLE = "infeasible"

78"""No feasible solution exists.

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

81dual solution, the problem is unbounded.

82"""

84SS_PREMATURE = "premature"

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

87SS_FAILURE = "failure"

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

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

95PS_FEASIBLE = "feasible"

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

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