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) 2017-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"""Backend for solver interface implementations.""" 

20 

21import importlib.util 

22import os 

23import sys 

24import time 

25from abc import ABC, abstractmethod 

26from contextlib import contextmanager 

27 

28from .. import settings 

29from ..apidoc import api_end, api_start 

30from ..formatting import solver_box 

31from ..modeling.solution import Solution 

32 

33_API_START = api_start(globals()) 

34# ------------------------------- 

35 

36 

37class SolverError(Exception): 

38 """Base class for solver-specific exceptions.""" 

39 

40 pass 

41 

42 

43class ProblemUpdateError(SolverError): 

44 """Changes to the problem could not be forward to the solver. 

45 

46 Raised by implementations of ``_update_problem`` to signal to the method 

47 ``_load_problem`` that the problem needs to be re-imported. 

48 """ 

49 

50 pass 

51 

52 

53class OptionError(SolverError): 

54 """Base class for solver option related errors.""" 

55 

56 pass 

57 

58 

59class UnsupportedOptionError(OptionError): 

60 """The solver does not support an option. 

61 

62 Raised by implementations of ``_solve`` to signal to the user that an option 

63 they specified is not supported by the solver or the requested sub-solver, 

64 or in conjunction with the given problem type or with another option. If the 

65 option is valid but not supported by PICOS, then NotImplementedError should 

66 be raised instead. The exception is only raised if the ``strictOptions`` 

67 option is set, otherwise a warning is printed. 

68 """ 

69 

70 pass 

71 

72 

73# TODO: Handle conflicting options globally, instead of within solver 

74# implementations. (Should not inherit from SolverError then.) 

75class ConflictingOptionsError(OptionError): 

76 """Two solver options are in conflict. 

77 

78 Raised by implementations of ``_solve`` to signal to the user that two 

79 options they specified cannot be used in conjunction. 

80 """ 

81 

82 pass 

83 

84 

85# TODO: Handle dependent options globally, instead of within solver 

86# implementations. (Should not inherit from SolverError then.) 

87class DependentOptionError(OptionError): 

88 """A solver option is invalid due to another option not being set. 

89 

90 Raised by implementations of ``_solve`` to signal to the user that an option 

91 they specified needs another option to also be set. 

92 """ 

93 

94 pass 

95 

96 

97# TODO: Handle option value errors globally, instead of within solver 

98# implementations. (Should not inherit from SolverError then.) 

99class OptionValueError(OptionError, ValueError): 

100 """A solver option has an invalid value. 

101 

102 Raised by implementations of ``_solve`` to signal to the user that they have 

103 set an option to an invalid value. 

104 """ 

105 

106 pass 

107 

108 

109# TODO: Add a write function that interfaces the solver's export to file. 

110# TODO: Potentially make this inherit from Reformulation. 

111class Solver(ABC): 

112 """Base class for an interface to an optimization solver.""" 

113 

114 # -------------------------------------------------------------------------- 

115 # Static methods. 

116 # -------------------------------------------------------------------------- 

117 

118 @staticmethod 

119 def check_import(importName): 

120 """Asserts that a module is available without actually importing it. 

121 

122 :raises ModuleNotFoundError: 

123 If the module could not be found. 

124 """ 

125 if importlib.util.find_spec(importName) is None: 

126 raise ModuleNotFoundError( 

127 "Python module '{}' not found.".format(importName)) 

128 

129 # -------------------------------------------------------------------------- 

130 # Abstract class methods. 

131 # -------------------------------------------------------------------------- 

132 

133 @classmethod 

134 @abstractmethod 

135 def supports(cls, footprint, explain=False): 

136 """Whether a type of problem, given by footprint, is supported. 

137 

138 The default implementation ensures that all reformulations required by 

139 user's choice have been performed before the problem is handed to the 

140 solver. Solver implementations are thus required to incorporate it. 

141 

142 :param bool explain: 

143 If :obj:`True`, then this returns a :class:`tuple` where the first 

144 element is this method's regular return value and where the second 

145 element is a string naming one reason why the footprint is not 

146 supported (:obj:`None` if it is). 

147 """ 

148 if footprint.options.dualize: 

149 if explain: 

150 return False, "Variants of the primal problem (dualize=True)." 

151 else: 

152 return False 

153 

154 return (True, None) if explain else True 

155 

156 @classmethod 

157 @abstractmethod 

158 def default_penalty(cls): 

159 """Report the default penalty for the solver. 

160 

161 See :class:`~picos.Options` for the scale. 

162 """ 

163 pass 

164 

165 @classmethod 

166 @abstractmethod 

167 def test_availability(cls): 

168 """Raise an exception if the solver is not installed on the system. 

169 

170 Checks whether the solver is installed on the system, and raises an 

171 appropriate exception (usually :exc:`ModuleNotFoundError` or 

172 :exc:`ImportError`) if not. Does not return anything. 

173 """ 

174 pass 

175 

176 @classmethod 

177 @abstractmethod 

178 def names(cls): 

179 """Returns a triple ``(name, display_name, long_display_name)``.""" 

180 pass 

181 

182 @classmethod 

183 @abstractmethod 

184 def is_free(cls): 

185 """Report whether the solver is free software. 

186 

187 This allows users to prevent PICOS from using non-free solvers at all, 

188 including for internal use, via the :data:`~.settings.NONFREE_SOLVERS` 

189 setting. 

190 """ 

191 pass 

192 

193 # -------------------------------------------------------------------------- 

194 # __init__ and instance properties. 

195 # -------------------------------------------------------------------------- 

196 

197 def __init__(self, problem): 

198 """Instanciate a solver interface with an optimization problem. 

199 

200 An exception is raised when the solver is not available on the user's 

201 platform. No exception is raised when the problem type is not supported 

202 as the problem is first imported when a solution is requested. 

203 

204 Solver implementations are supposed to also implement :meth:`__init__`, 

205 but with ``problem`` as its only positional argument, and using 

206 :obj:`super` to provide fixed values for this method's additional 

207 parameters. 

208 

209 :param problem: A PICOS optimization problem. 

210 :type problem: :class:`Problem <picos.Problem>` 

211 """ 

212 # Make sure the solver is available. 

213 self.test_availability() 

214 

215 # The external (PICOS) problem represenation. 

216 # HACK: Quick and dirty conversion to accept reformulations as input. 

217 from ..modeling import Problem 

218 from ..reforms import Reformulation 

219 if isinstance(problem, Reformulation): 

220 problem.successor = self 

221 self.predecessor = problem 

222 self._ext = None 

223 else: 

224 assert isinstance(problem, Problem) 

225 self._ext = problem 

226 

227 # The solver's internal problem representation, which the advanced user 

228 # may access at their own risk. 

229 self.int = None 

230 

231 # The last optimization objective that was imported. 

232 self._knownObjective = None 

233 

234 # The PICOS variables that are currently imported. 

235 self._knownVariables = set() 

236 

237 # The PICOS constraints that are currently imported. 

238 self._knownConstraints = set() 

239 

240 @property 

241 def ext(self): 

242 """The "external" (input) problem.""" 

243 return self._ext if self._ext else self.predecessor.output 

244 

245 @property 

246 def name(self): 

247 """Keyword string of the solver.""" 

248 return self.names()[0] 

249 

250 @property 

251 def display_name(self): 

252 """Short display name of the solver.""" 

253 return self.names()[1] 

254 

255 @property 

256 def long_display_name(self): 

257 """Long display name of the solver.""" 

258 return self.names()[2] 

259 

260 # -------------------------------------------------------------------------- 

261 # Abstract instance methods. 

262 # -------------------------------------------------------------------------- 

263 

264 @abstractmethod 

265 def reset_problem(self): 

266 """Reset the solver's internal problem representation and related data. 

267 

268 Method implementations are supposed to 

269 

270 - set ``int`` to None (after performing any garbage collection), and 

271 - reset all additional problem metadata to the state it had after 

272 :meth:`__init__`, in particular the data stored for 

273 ``_update_problem``. 

274 

275 Solver implementations should not call :meth:`reset_problem` directly, 

276 except from within :meth:`__init__` if this is convenient. 

277 

278 The user may call this method at any time if they wish to solve the 

279 problem from scratch. 

280 """ 

281 pass 

282 

283 @abstractmethod 

284 def _import_problem(self): 

285 """Convert a PICOS problem to the solver's internal representation. 

286 

287 Method implementations can assume to be run directly after either 

288 :meth:`__init__` or :meth:`reset_problem`, and before ``_solve``. The 

289 method is supposed to transform only the problem formulation itself; 

290 solver configuration options are passed inside ``_solve`` instead. 

291 """ 

292 pass 

293 

294 @abstractmethod 

295 def _update_problem(self): 

296 """Update the solver's internal problem representation, if possible. 

297 

298 Method implementations should make use of ``_objective_has_changed``, 

299 ``_new_variables``, ``_removed_variables``, ``_new_constraints`` and 

300 ``_removed_constraints``. Note that you can use each of the latter four 

301 generators only once each update as they will update the sets of known 

302 variables and constraints, respectively. 

303 

304 Method implementations may raise 

305 

306 - :exc:`NotImplementedError`, if updates to the internal problem 

307 instance of the solver are not supported (not at all or just not by 

308 PICOS), or 

309 - :exc:`ProblemUpdateError`, if an update to the solver's internal 

310 problem instance is not possible for the particular set of changes in 

311 the problem formulation. 

312 

313 In both cases, the user will receive a warning and the problem will be 

314 re-imported instead of updated. In the case of 

315 :exc:`ProblemUpdateError`, a reason should be given and will be included 

316 in the warning. 

317 

318 Solver implementations should not call ``_update_problem`` directly, but 

319 instead call ``_load_problem``. 

320 """ 

321 pass 

322 

323 @abstractmethod 

324 def _solve(self): 

325 """Solve the problem and return the solution. 

326 

327 Method implementations can assume to be run after ``_load_problem``, 

328 which attempts to run ``_update_problem`` and falls back to 

329 ``_import_problem``. The method is supposed to pass options to the 

330 solver, run it within the ``_stopwatch`` context, and return the 

331 solution. The solution object should be created via ``_make_solution``. 

332 

333 An InappropriateSolverError should be raised if the solver (or its 

334 requested sub-solver) does not support the given problem type. 

335 

336 :returns picos.modeling.Solution: The solution found by the solver. 

337 """ 

338 pass 

339 

340 # -------------------------------------------------------------------------- 

341 # Non-abstract class methods. 

342 # -------------------------------------------------------------------------- 

343 

344 @classmethod 

345 def penalty(cls, options): 

346 """Report solver penalty given an :class:`~picos.Options` object.""" 

347 return options["penalty_{}".format(cls.names()[0])] 

348 

349 @classmethod 

350 def available(cls, verbose=False): 

351 """Whether the solver is properly installed on the system.""" 

352 name, display_name, _ = cls.names() 

353 

354 if name in settings.SOLVER_BLACKLIST: 

355 if verbose: 

356 print("The solver {} is blacklisted.".format(display_name)) 

357 return False 

358 

359 if settings.SOLVER_WHITELIST and name not in settings.SOLVER_WHITELIST: 

360 if verbose: 

361 print("The solver {} is not whitelisted.".format(display_name)) 

362 return False 

363 

364 if not settings.NONFREE_SOLVERS and not cls.is_free(): 

365 if verbose: 

366 print("The solver {} is non-free.".format(display_name)) 

367 return False 

368 

369 try: 

370 cls.test_availability() 

371 except Exception as error: 

372 if verbose: 

373 print(error) 

374 return False 

375 

376 return True 

377 

378 @classmethod 

379 def predict(cls, footprint): 

380 """Return the solver class. 

381 

382 This mimics the behavior of 

383 :meth:`Reformulation.predict <picos.reforms.Reformulation>` so that 

384 solvers can be the last pipeline node in a reformulation strategy. 

385 """ 

386 return cls 

387 

388 # -------------------------------------------------------------------------- 

389 # Non-abstract instance methods (except for __init__ and properties). 

390 # ------------------------------------------------------------------------- 

391 

392 def __str__(self): 

393 return "# wrapper around a " + self.display_name + " problem instance #" 

394 

395 def reset(self): 

396 """A shorthand for :meth:`reset_problem`. 

397 

398 This is defined for consistency with 

399 :meth:`Reformulation.reset <.reformulation.Reformulation.reset>`. 

400 """ 

401 self.reset_problem() 

402 

403 def external_problem(self): 

404 """Return the external (PICOS) problem represenation.""" 

405 return self.ext 

406 

407 def internal_problem(self): 

408 """Return the solver's internal problem represenation.""" 

409 return self.int 

410 

411 def verbosity(self): 

412 """Return the problem's current verbosity level.""" 

413 return self.ext.options.verbosity 

414 

415 def _verbosity_printer(self, minLevel, message=None): 

416 """Print a message if the verbosity level reaches a threshold. 

417 

418 :returns: Whether messages are printed. 

419 """ 

420 condition = self.ext.options.verbosity >= minLevel 

421 if condition and message is not None: 

422 print(message) 

423 return condition 

424 

425 def _warn(self, message=None): 

426 """Print a warning message, if the verbosity level allows for it. 

427 

428 :returns: Whether warning messages are printed. 

429 """ 

430 return self._verbosity_printer(0, message) 

431 

432 def _verbose(self, message=None): 

433 """Print an informative message, if the verbosity level allows for it. 

434 

435 :returns: Whether informative messages are printed. 

436 """ 

437 return self._verbosity_printer(1, message) 

438 

439 def _debug(self, message=None): 

440 """Print a debug message, if the verbosity level allows for it. 

441 

442 :returns: Whether debug messages are printed. 

443 """ 

444 return self._verbosity_printer(2, message) 

445 

446 def _handle_unsupported_option(self, option, customMessage=None): 

447 """Inform the user about an unsupported option. 

448 

449 The manner depends on the ``strict_options`` option; either a warning is 

450 printed or an exception is raised. 

451 """ 

452 assert option in self.ext.options, \ 

453 "The option '{}' does not exist.".format(option) 

454 

455 if self.ext.options[option] in (None, False): 

456 return 

457 

458 if customMessage: 

459 message = customMessage 

460 else: 

461 message = "{} does not support the '{}' option." \ 

462 .format(self.display_name, option) 

463 

464 if self.ext.options.strict_options: 

465 raise UnsupportedOptionError(message) 

466 else: 

467 self._warn(message) 

468 

469 def _handle_unsupported_options(self, *options): 

470 """Handle a number of unsupported options at once.""" 

471 for option in options: 

472 self._handle_unsupported_option(option) 

473 

474 def _handle_bad_solver_specific_option(self, key, value, error): 

475 picos_option = "{}_params".format(self.name) 

476 assert picos_option in self.ext.options, \ 

477 "The PICOS option '{}' does not exist.".format(picos_option) 

478 

479 raise OptionValueError( 

480 "Either the {} option '{}' set via '{}' does not exist or the given" 

481 " value '{}' is not valid for that option.".format( 

482 self.display_name, key, picos_option, value)) from error 

483 

484 def _handle_bad_solver_specific_option_key(self, key, error=None): 

485 picos_option = "{}_params".format(self.name) 

486 assert picos_option in self.ext.options, \ 

487 "The PICOS option '{}' does not exist.".format(picos_option) 

488 

489 raise OptionValueError( 

490 "The {} option '{}' set via '{}' does not exist.".format( 

491 self.display_name, key, picos_option)) from error 

492 

493 def _handle_bad_solver_specific_option_value(self, key, value, error=None): 

494 picos_option = "{}_params".format(self.name) 

495 assert picos_option in self.ext.options, \ 

496 "The PICOS option '{}' does not exist.".format(picos_option) 

497 

498 raise OptionValueError( 

499 "Invalid value '{}' for {} option '{}' set via '{}'.".format( 

500 value, self.display_name, key, picos_option)) from error 

501 

502 def _handle_continuous_nonconvex_error(self, error): 

503 """Raise a descriptive :exc:`ArithmeticError`.""" 

504 raise ArithmeticError("{0} refuses the problem as (continuous) " 

505 "nonconvex even though PICOS ensures convexity of (continuous) " 

506 "problems given to {0}. The most likely cause is that some " 

507 "quadratic form is numerically on the verge of being semidefinite, " 

508 "with PICOS' and {0}'s judgement differing. You could try a slight " 

509 "perturbation of your data such that all quadratic forms become " 

510 "definite.".format(self.display_name)) from error 

511 

512 def _load_problem(self): 

513 """(Re-)import or update the solver's problem state for solving.""" 

514 # Make sure the problem is supported. 

515 footprint = self.ext.footprint 

516 assert self.supports(footprint), \ 

517 "PICOS gave {} an unsupported problem to load: {}".format( 

518 self.display_name, footprint) 

519 

520 # Import or update the problem. 

521 if self.int is None: 

522 self._verbose("Building a {} problem instance." 

523 .format(self.display_name)) 

524 self._import_problem() 

525 else: 

526 try: 

527 self._verbose("Updating the {} problem instance." 

528 .format(self.display_name)) 

529 self._update_problem() 

530 except (NotImplementedError, ProblemUpdateError) as error: 

531 if type(error) is NotImplementedError: 

532 reason = "Not supported with {}.".format(self.display_name) 

533 else: 

534 reason = str(error) 

535 if reason == "": 

536 reason = "Unknown reason." 

537 self._verbose("Update failed: {}".format(reason)) 

538 self._verbose("Rebuilding the {} problem instance." 

539 .format(self.display_name)) 

540 self.reset_problem() 

541 self._import_problem() 

542 

543 # Remember which objective and what constraints were imported. 

544 self._knownObjective = self.ext.objective 

545 self._knownVariables = set(self.ext.variables.values()) 

546 self._knownConstraints = set(self.ext.constraints.values()) 

547 

548 def _objective_has_changed(self): 

549 """Check for an objective function change. 

550 

551 :returns: Whether the optimization objective has changed since the last 

552 forward or update. 

553 """ 

554 assert self._knownObjective is not None, \ 

555 "_objective_has_changed may only be used inside _update_problem." 

556 

557 objectiveChanged = self._knownObjective != self.ext.objective 

558 

559 if objectiveChanged: 

560 self._knownObjective = self.ext.objective 

561 

562 return objectiveChanged 

563 

564 def _new_variables(self): 

565 """Check for new variables. 

566 

567 Yields PICOS variables that were added to the external problem 

568 representation since the last import or update. 

569 

570 Note that variables received from this method will also be added to the 

571 set of known variables, so you can only iterate once within each update. 

572 """ 

573 for variable in self.ext.variables.values(): 

574 if variable not in self._knownVariables: 

575 self._knownVariables.add(variable) 

576 yield variable 

577 

578 def _removed_variables(self): 

579 """Check for removed variables. 

580 

581 Yields PICOS variables that were removed from the external problem 

582 representation since the last import or update. 

583 

584 Note that variables received from this method will also be removed from 

585 the set of known variables, so you can only iterate once within each 

586 update. 

587 """ 

588 newVariables = set(self.ext.variables.values()) 

589 for variable in self._knownVariables: 

590 if variable not in newVariables: 

591 yield variable 

592 self._knownVariables.intersection_update(newVariables) 

593 

594 def _new_constraints(self): 

595 """Check for new constraints. 

596 

597 Yields PICOS constraints that were added to the external problem 

598 representation since the last import or update. 

599 

600 Note that constraints received from this method will also be added to 

601 the set of known constraints, so you can only iterate once within each 

602 update. 

603 """ 

604 for constraint in self.ext.constraints.values(): 

605 if constraint not in self._knownConstraints: 

606 self._knownConstraints.add(constraint) 

607 yield constraint 

608 

609 def _removed_constraints(self): 

610 """Check for removed constraints. 

611 

612 Yields PICOS constraints that were removed from the external problem 

613 representation since the last import or update. 

614 

615 Note that constraints received from this method will also be removed 

616 from the set of known constraints, so you can only iterate once within 

617 each update. 

618 """ 

619 newConstraints = set(self.ext.constraints.values()) 

620 for constraint in self._knownConstraints: 

621 if constraint not in newConstraints: 

622 yield constraint 

623 self._knownConstraints.intersection_update(newConstraints) 

624 

625 @contextmanager 

626 def _stopwatch(self): 

627 """Store the time spent within the context in ``timer``. 

628 

629 Solver implementations should use this context around the call to the 

630 solution routine to measure its search time. 

631 """ 

632 startTime = time.time() 

633 yield 

634 endTime = time.time() 

635 self.timer = endTime - startTime 

636 

637 def _reset_stopwatch(self): 

638 """Reset the timer of the ``_stopwatch`` context manager.""" 

639 self.timer = None 

640 

641 def _make_solution(self, value, primals, duals, primalStatus, dualStatus, 

642 problemStatus, info=None, vectorizedPrimals=True): 

643 """Create a solution problem from within :meth:`_solve`. 

644 

645 Note that the default value for ``vectorizedPrimals`` is :obj:`True`, 

646 unlike that of 

647 :meth:`Solution.__init__ <picos.modeling.Solution.__init__>`. This is 

648 because users are expected to create manual solutions from matrix data 

649 while solvers usually work with the vectorized variables. 

650 """ 

651 from ..modeling import Solution 

652 from . import get_solver_name 

653 

654 assert self.timer is not None, \ 

655 "Solvers must measure search time via _stopwatch." 

656 

657 return Solution( 

658 primals=primals, 

659 duals=duals, 

660 problem=self.ext, 

661 solver=get_solver_name(self), 

662 primalStatus=primalStatus, 

663 dualStatus=dualStatus, 

664 problemStatus=problemStatus, 

665 searchTime=self.timer, 

666 info=info, 

667 vectorizedPrimals=vectorizedPrimals, 

668 reportedValue=value) 

669 

670 def execute(self): 

671 """Solve the problem and return the solution. 

672 

673 :returns picos.Solution or list(picos.Solution): A solution object or 

674 list thereof. 

675 """ 

676 self._load_problem() 

677 self._reset_stopwatch() 

678 

679 self._verbose("Starting solution search.") 

680 

681 solution = self._solve() 

682 

683 if isinstance(solution, list): 

684 assert all(isinstance(s, Solution) for s in solution) 

685 else: 

686 assert isinstance(solution, Solution) 

687 

688 return solution 

689 

690 @contextmanager 

691 def _header(self, subsolver=None): 

692 """Print both a header and a footer.""" 

693 with solver_box(self.long_display_name, self.display_name, 

694 subsolver, self._verbose()): 

695 yield 

696 

697 @property 

698 def _license_warnings(self): 

699 """Whether license related warnings may ignore verbosity.""" 

700 return settings.LICENSE_WARNINGS and self.ext.options.license_warnings 

701 

702 @contextmanager 

703 def _enforced_verbosity(self, noStdOutAt=0, noStdErrAt=-1): 

704 """Enfoce the user-specified verbosity within the context. 

705 

706 :param int noStdOutAt: Don't print to stdout at or below this verbosity. 

707 :param int noStdErrAt: Don't print to stderr at or below this verbosity. 

708 

709 .. warning:: 

710 

711 This context manager monkey-patches the :mod:`sys` module and is not 

712 thread safe. 

713 """ 

714 verbosity = self.ext.verbosity() 

715 

716 if verbosity <= max(noStdOutAt, noStdErrAt): 

717 devNull = open(os.devnull, "w") 

718 

719 if verbosity <= noStdOutAt: 

720 oldOut = sys.stdout 

721 sys.stdout = devNull 

722 

723 if verbosity <= noStdErrAt: 

724 oldErr = sys.stderr 

725 sys.stderr = devNull 

726 

727 try: 

728 yield 

729 finally: 

730 if verbosity <= noStdOutAt: 

731 sys.stdout = oldOut 

732 

733 if verbosity <= noStdErrAt: 

734 sys.stderr = oldErr 

735 

736 

737# -------------------------------------- 

738__all__ = api_end(_API_START, globals())