Source code for mga_surveyor.methods.cdd

"""``CddMethod``.

- Uses cdd's (Fukuda's) Double Description method for the outer polytope's
  vertex set.
- Two arithmetic backends, selected via ``backend``: ``'float'`` (default)
  uses cdd's native C double arithmetic; ``'gmp'`` uses ``cdd.gmp``'s exact
  rational (GMP) arithmetic instead, at higher per-call cost, immune to the
  float backend's documented numerical-inconsistency failure mode on
  degenerate/near-degenerate accumulated halfspaces (see
  ``disdyakis_triacontahedron.py``'s module docstring for a real instance
  of that failure). Every halfspace coefficient is converted to
  ``fractions.Fraction`` before being handed to ``cdd.gmp`` -- an exact,
  lossless reinterpretation of whatever binary float value it already was,
  not a new source of imprecision, and not an attempt to recover exactness
  the upstream float computation (LP duals, etc.) never had in the first
  place.
- :meth:`CddMethod.add_cut` folds a new halfspace in incrementally --
  resuming cddlib's own Double Description computation instead of
  recomputing the whole polytope -- via ``polyhedron_append_halfspaces``
  (present on both the ``cdd`` and ``cdd.gmp`` modules), when the installed
  ``cdd``/``cdd.gmp`` has it. That function is a local patch on top of
  pycddlib/cddlib (vendored, with the patch, under ``vendor/cdd`` -- see
  ``vendor/cdd/README.md``) that isn't part of any upstream pycddlib
  release: cddlib's own public incremental-looking
  entry point, ``dd_DDInputAppend``, is an admitted stub ("This is
  incomplete. It simply solves the problem from scratch.") that just
  reruns the whole Double Description method. When
  ``polyhedron_append_halfspaces`` either isn't present (a stock
  ``pycddlib`` install) or raises (its own restrictions on the append
  aren't met for this polytope -- see its docstring), :meth:`_vertices_with_ids`
  transparently falls back to a full rebuild from ``self.outer_halfspaces``
  -- still correct either way, just not incremental for that one step. So
  this class keeps the strongest correctness guarantee of the three
  methods (cdd is a mature, independent implementation) regardless of
  which ``cdd`` build is installed; only the cost profile changes.
- The per-vertex closest-inner-point solve is cached across refreshes by
  generator identity: ``copy_generators_with_ids`` (also part of the local
  patch) tags every vertex with a persistent integer id that survives an
  incremental append unchanged, so :meth:`_refresh` can tell "this is the
  same vertex as last time" by exact id match instead of geometric
  comparison, reuse its cached closest point/normal, and only solve for
  vertices whose id is new. A full rebuild's ids are NOT comparable to a
  previous build's (cddlib restarts its id counter from scratch every
  time), so every vertex is treated as new whenever that path runs. When
  ``copy_generators_with_ids`` isn't available, every vertex is solved
  every refresh, exactly as before this caching existed.
"""
import time
from concurrent.futures import Executor
from fractions import Fraction
from types import ModuleType
from typing import Literal, Protocol

import numpy as np

from ..common import Halfspace, Norm, gaps, check_norm
from ..gurobi_projection import closest_point_on_hull
from .base import Method

#: Which cdd arithmetic backend to use -- ``'float'`` (cdd's native C
#: double arithmetic) or ``'gmp'`` (cdd.gmp's exact rational arithmetic).
CddBackend = Literal["float", "gmp"]


[docs] class ProjectionFn(Protocol): """Contract for `projection_fn`: project `point` onto `conv(points)` under `norm`, returning `(closest_point, normal)` -- exactly what `gurobi_projection.closest_point_on_hull` / `highs_projection. closest_point_on_hull` implement (see either's docstring). """ def __call__(self, point: np.ndarray, points: np.ndarray, norm: Norm) -> tuple[np.ndarray, np.ndarray]: ...
[docs] def check_cdd_backend(backend: str) -> None: """Validate an untrusted ``backend`` value at a package boundary -- the ``cdd``-specific counterpart of :func:`~mga_surveyor.common.check_norm`. """ if backend not in ("float", "gmp"): raise ValueError(f"backend must be 'float' or 'gmp', got {backend!r}")
def _cdd_module(backend: CddBackend) -> ModuleType: """Import and return the cdd module for ``backend`` -- ``cdd`` itself for ``'float'``, ``cdd.gmp`` for ``'gmp'``. A separate function (rather than inlining the import) so every call site imports lazily, keeping ``cdd``/``cdd.gmp`` genuinely optional dependencies -- see the ``cdd`` extra's note in ``pyproject.toml``. """ check_cdd_backend(backend) if backend == "float": import cdd return cdd else: import cdd.gmp return cdd.gmp def _halfspace_row(direction: np.ndarray, point: np.ndarray, backend: CddBackend) -> list: """One row of cdd's ``[b | A]`` H-representation for the halfspace ``{x : direction@x <= direction@point}``. ``direction`` is unit-normalized (divided by its own Euclidean norm) before the row is built -- scaling a halfspace's defining vector by any positive constant doesn't change the halfspace itself (``a@x<=b`` and ``(a/|a|)@x<=(b/|a|)`` are the same set), so this is free geometrically. It matters because cddlib's float-mode sign tests compare against one fixed ABSOLUTE tolerance (``dd_zero``, cddlib's own ``dd_almostzero``) -- if different cuts' rows come out at very different natural magnitudes (which they do here: `normal_to_normalized`'s per-dimension rescaling and this network's genuinely different-scale dimensions easily produce that), the same fixed tolerance is effectively far looser for large-magnitude rows and far tighter for small ones. Putting every row on the same (unit) scale removes that per-cut inconsistency. Confirmed empirically to bring float-mode's outer polytope into close agreement with gmp on this project's real network, where un-normalized float mode was badly wrong. A no-op for correctness under ``gmp`` (exact arithmetic has no tolerance to be inconsistent about), so applying it unconditionally to both backends is safe. Under ``backend='gmp'``, every entry is converted to an exact ``Fraction`` -- required by ``cdd.gmp`` (it rejects plain ``float`` input outright, since silently rounding would defeat the point of requesting exact arithmetic) and lossless: ``Fraction(x)`` on a float ``x`` is the exact rational value of that float's own binary representation, not a new approximation of it. """ direction = np.asarray(direction, dtype=float) direction_norm = np.linalg.norm(direction) if direction_norm > 0: # A zero direction is a degenerate/vacuous halfspace (0@x<=0@point, # trivially true everywhere) -- dividing by its own (zero) norm # would just turn it into a row of NaNs, which cddlib's linearity # detection can't handle at all (worse than the harmless all-zero # row this preserves instead). direction = direction / direction_norm b = float(direction @ np.asarray(point)) row = [b] + [-float(c) for c in direction] if backend == "gmp": return [Fraction(x) for x in row] return row def _extract_vertices(cdd_mod: ModuleType, poly) -> np.ndarray: """Pull the finite vertices (as opposed to rays) out of a cdd ``Polyhedron``'s generators -- a generator row is a vertex iff its leading column is ``1`` rather than ``0`` (cdd's homogeneous V-representation convention). Backend-agnostic: ``round()``/``float()`` both work the same on a ``gmp`` row's ``Fraction`` entries as on a ``float`` row's plain floats. :param cdd_mod: The cdd module (``cdd`` or ``cdd.gmp``) ``poly`` was built with. :param poly: A cdd ``Polyhedron`` in H-representation with its generators already computed. :returns: The polyhedron's vertices, as an ``(m, k)`` array. :rtype: numpy.ndarray """ gens = cdd_mod.copy_generators(poly) verts = [ [float(x) for x in row[1:]] for row in gens.array if round(row[0]) == 1 ] return np.array(verts) def _extract_vertices_with_ids(cdd_mod: ModuleType, poly) -> tuple[np.ndarray, list[int] | None]: """Like :func:`_extract_vertices`, but also returns each vertex's persistent generator id -- via ``copy_generators_with_ids`` -- when the installed cdd module has that function and it accepts ``poly`` (it shares ``polyhedron_append_halfspaces``'s own restrictions: H-repr, full column rank; otherwise it raises -- documented as :exc:`ValueError`, but the vendored build actually raises :exc:`RuntimeError` through cddlib's error path, so both are caught -- e.g. for a not-yet-fully-bounded polytope). Returns ``ids=None`` whenever id tracking isn't available for this call, signalling the caller to fall back to solving every vertex fresh, same as if this function didn't exist at all. :param cdd_mod: The cdd module (``cdd`` or ``cdd.gmp``) ``poly`` was built with. :param poly: A cdd ``Polyhedron`` in H-representation with its generators already computed. :returns: ``(vertices, ids)`` -- ``vertices`` as an ``(m, k)`` array; ``ids`` a length-``m`` list aligned with its rows, or ``None``. :rtype: tuple """ if not hasattr(cdd_mod, "copy_generators_with_ids"): return _extract_vertices(cdd_mod, poly), None try: gens, gen_ids = cdd_mod.copy_generators_with_ids(poly) except (ValueError, RuntimeError): return _extract_vertices(cdd_mod, poly), None verts = [] ids = [] for row, gid in zip(gens.array, gen_ids): if round(row[0]) == 1: verts.append([float(x) for x in row[1:]]) ids.append(gid) return np.array(verts), ids
[docs] def cdd_vertices_of(outer_halfspaces: list[Halfspace], backend: CddBackend = "float") -> np.ndarray: """Ground-truth V-representation of the outer polytope defined by ``outer_halfspaces``, via a fresh cdd double description computation from scratch (all-at-once, not incremental). Used independently of any :class:`CddMethod` instance's own incremental state -- e.g. as a from-scratch ground-truth cross-check against a live instance's incrementally-maintained vertex set (see ``tests/test_cdd_incremental.py``), where reusing incremental state would defeat the point. :param outer_halfspaces: ``(direction, point)`` pairs, each defining a supporting hyperplane of the outer polytope. :param backend: ``'float'`` (default) or ``'gmp'`` -- see module docstring. :returns: The polytope's vertices, as an ``(m, k)`` array. :rtype: numpy.ndarray """ cdd_mod = _cdd_module(backend) rows = [_halfspace_row(direction, point, backend) for direction, point in outer_halfspaces] mat = cdd_mod.matrix_from_array(rows, rep_type=cdd_mod.RepType.INEQUALITY) poly = cdd_mod.polyhedron_from_matrix(mat) return _extract_vertices(cdd_mod, poly)
[docs] class CddMethod(Method): """See module docstring. :param k: Dimension of the exploratory variables. :param norm: Distance metric, one of ``'l1'``, ``'l2'``, or ``'linf'``. :type norm: str :param executor: Used to run the independent per-vertex ``closest_point_on_hull`` solves concurrently after each refresh. A fresh ``ThreadPoolExecutor`` is created if none is given. :type executor: concurrent.futures.Executor, optional :param backend: ``'float'`` (default) or ``'gmp'`` -- see module docstring. Unrelated to ``projection_backend``/``projection_fn`` below: this picks cdd's own outer-polytope arithmetic, not the inner-hull projection's solver. :type backend: str :param projection_fn: Lower-level override of the inner-hull projection callable itself, signature ``(point, points, norm) -> (closest_point, normal)`` -- takes precedence over ``projection_backend`` if given. Every call site goes through ``self.projection_fn``, so any callable matching that contract works, not just the two built-in backends. :param projection_backend: Which persistent solver to use for the inner-hull projection -- ``'gurobi'`` (default, all three norms) or ``'highs'`` (open-source, no license required; L1/Linf only -- HiGHS has no quadratic-objective support). Same choice this project's now-removed incremental-vertex-enumeration method used to expose as its own ``backend`` parameter -- named differently here since ``backend`` on this class already means cdd's arithmetic. :type projection_backend: str :raises ValueError: If ``projection_backend`` is not ``'gurobi'`` or ``'highs'``. """ def __init__( self, k: int, norm: Norm, executor: Executor | None = None, backend: CddBackend = "float", projection_fn: ProjectionFn | None = None, projection_backend: Literal["gurobi", "highs"] = "gurobi", ) -> None: check_norm(norm) check_cdd_backend(backend) super().__init__(k, norm) if executor is None: from concurrent.futures import ThreadPoolExecutor executor = ThreadPoolExecutor(max_workers=8) self.executor = executor self.backend = backend self.projection_backend = projection_backend if projection_fn is not None: self.projection_fn = projection_fn elif projection_backend == "highs": # aliased on import: gurobi_projection.py/highs_projection.py both # name their projection function `closest_point_on_hull` -- see # either's own docstring -- so an alias is needed here to avoid # shadowing the one this module already imported for the # 'gurobi' default. from ..highs_projection import closest_point_on_hull as closest_point_on_hull_highs self.projection_fn = closest_point_on_hull_highs elif projection_backend == "gurobi": self.projection_fn = closest_point_on_hull else: raise ValueError(f"projection_backend must be 'gurobi' or 'highs', got {projection_backend!r}") self.inner_vertices = None self.outer_halfspaces = [] self._poly = None # persistent cdd.Polyhedron, folded into incrementally by add_cut; None until first built self._pending_rows = [] # halfspace rows from add_cut not yet folded into self._poly self._outer_vertices = None self._vertex_ids = None # generator ids aligned with self._outer_vertices, or None if unsupported self._closest_points = None self._closest_normals = None # aligned with self._outer_vertices; None whenever self._vertex_ids is None self._gap = None self._dirty = True self.stats: dict[str, float | int | None] = {} self.reset_stats()
[docs] def reset_stats(self) -> None: """Zero the instrumentation counters in :attr:`stats` -- purely additive bookkeeping, no effect on any other method's behavior or return value. :meth:`_refresh`/:meth:`_refresh_stale_closest_points` ACCUMULATE into these on every call (so several ``add_cut``s folded into one refresh, or a stale-point check plus a refresh, both add up rather than overwrite); call this to scope the running totals to whatever the caller considers one logical "iteration" (e.g. one `add_point` + its `add_cut`(s) + one `max_gap()`), then read :attr:`stats` after that iteration's calls are done. - ``cdd_time``/``projection_time``: seconds spent inside cdd's own append/rebuild call, and inside ``self.projection_fn`` solves, respectively (the latter summed across both :meth:`_refresh_stale_closest_points` and :meth:`_refresh`'s own solve step). - ``n_total``: the outer vertex count as of the last :meth:`_refresh` (a snapshot, not a delta -- last write wins even across several refreshes since the last reset). - ``n_new``/``n_removed``: vertices whose generator id appeared/ disappeared since the previous refresh's id set. ``None`` instead of an int whenever id tracking itself isn't available at all for this cdd install (see module docstring) -- distinct from ``0``, which means id tracking IS available and nothing actually changed. A full-rebuild fallback (id numbering restarts, so no previous id is comparable) counts as every previous vertex removed and every current one new, not a bug. - ``n_stale_checked``/``n_stale_failed``: from :meth:`_refresh_stale_closest_points`'s own cache-validity check -- how many previously-cached closest-point/normal pairs were checked against a newly added inner point, and how many of those failed (needed re-solving). - ``n_stale_failed_improved``: of the ones that failed and got re-solved, how many landed on a STRICTLY smaller gap than their stale cached value (rather than an equal one, e.g. a tie at the solver's own tolerance). """ self.stats = { "cdd_time": 0.0, "projection_time": 0.0, "n_total": 0, "n_new": 0, "n_removed": 0, "n_stale_checked": 0, "n_stale_failed": 0, "n_stale_failed_improved": 0, }
[docs] def bootstrap(self, initial_points: list[np.ndarray], initial_halfspaces: list[Halfspace]) -> None: self.inner_vertices = np.array(initial_points, dtype=float) self.outer_halfspaces = list(initial_halfspaces) self._poly = None self._pending_rows = [] self._dirty = True
[docs] def add_point(self, point: np.ndarray) -> bool: point = np.asarray(point, dtype=float) is_new = np.linalg.norm(self.inner_vertices - point, axis=1).min() > 1e-6 if is_new: self.inner_vertices = np.vstack([self.inner_vertices, point]) if self._closest_normals is not None: self._refresh_stale_closest_points(point) self._dirty = True return is_new
def _refresh_stale_closest_points(self, new_inner_vertex: np.ndarray) -> None: """After the inner approximation grows, some cached closest-point/ normal pairs (keyed by generator id -- see :meth:`_refresh`) may no longer be optimal -- exactly those whose cached separating hyperplane ``new_inner_vertex`` violates. Recompute only those (cheap ``O(outer_vertices)`` check first). Only called when ``self._closest_normals`` is populated, i.e. the last refresh actually had id-tracked caching to keep valid -- with no such cache, the next :meth:`_refresh` recomputes every vertex unconditionally anyway, so doing this check would be pure waste. :param new_inner_vertex: The newly added inner vertex. """ if self._outer_vertices is None or len(self._outer_vertices) == 0: return rhs = new_inner_vertex[None, :] - self._closest_points still_valid = np.einsum("ij,ij->i", self._closest_normals, rhs) <= 1e-9 stale_positions = np.where(~still_valid)[0] self.stats["n_stale_checked"] += len(still_valid) self.stats["n_stale_failed"] += len(stale_positions) if len(stale_positions) == 0: return stale_points = self._outer_vertices[stale_positions] old_closest = self._closest_points[stale_positions].copy() t0 = time.perf_counter() results = list(self.executor.map( lambda p: self.projection_fn(p, self.inner_vertices, norm=self.norm), stale_points )) self.stats["projection_time"] += time.perf_counter() - t0 new_closest = np.array([c for c, _ in results]) old_gap = gaps(stale_points, old_closest, norm=self.norm) new_gap = gaps(stale_points, new_closest, norm=self.norm) self.stats["n_stale_failed_improved"] += int(np.sum(new_gap < old_gap - 1e-12)) for pos, (c, n) in zip(stale_positions.tolist(), results): self._closest_points[pos] = c self._closest_normals[pos] = n
[docs] def add_cut(self, direction: np.ndarray, point: np.ndarray) -> None: direction = np.asarray(direction, dtype=float) point = np.asarray(point, dtype=float) self.outer_halfspaces = self.outer_halfspaces + [(direction, point)] self._pending_rows.append(_halfspace_row(direction, point, self.backend)) self._dirty = True
def _vertices_with_ids(self) -> tuple[np.ndarray, list[int] | None, bool]: """The outer polytope's current vertex set, with each vertex's persistent generator id when available. Appends whatever :meth:`add_cut` has queued in ``self._pending_rows`` onto the persistent ``self._poly`` via ``polyhedron_append_halfspaces`` (resuming cddlib's Double Description computation) when that function is available and succeeds; rebuilds ``self._poly`` from the complete ``self.outer_halfspaces`` from scratch otherwise -- on the first call, when the installed cdd module predates the incremental-append patch, or when the append itself raised (its own restrictions -- see its docstring -- weren't met for this polytope). Either path leaves ``self._poly`` holding the correct, fully up to date polyhedron. :returns: ``(vertices, ids, is_fresh_build)``. ``is_fresh_build`` is ``True`` whenever a rebuild ran this call -- cddlib restarts its id numbering from scratch on every fresh ``dd_DDMatrix2Poly``, so ``ids`` (if not ``None``) are NOT comparable to whatever :class:`CddMethod` cached from a previous call in that case; the caller must treat every vertex as new rather than attempt id-based reuse. :rtype: tuple """ cdd_mod = _cdd_module(self.backend) def full_rebuild() -> tuple[np.ndarray, list[int] | None]: rows = [_halfspace_row(d, p, self.backend) for d, p in self.outer_halfspaces] mat = cdd_mod.matrix_from_array(rows, rep_type=cdd_mod.RepType.INEQUALITY) self._poly = cdd_mod.polyhedron_from_matrix(mat) self._pending_rows = [] return _extract_vertices_with_ids(cdd_mod, self._poly) if self._poly is None or not hasattr(cdd_mod, "polyhedron_append_halfspaces"): verts, ids = full_rebuild() return verts, ids, True if self._pending_rows: mat = cdd_mod.matrix_from_array(self._pending_rows, rep_type=cdd_mod.RepType.INEQUALITY) try: cdd_mod.polyhedron_append_halfspaces(self._poly, mat) except RuntimeError: verts, ids = full_rebuild() return verts, ids, True self._pending_rows = [] verts, ids = _extract_vertices_with_ids(cdd_mod, self._poly) return verts, ids, False def _refresh(self) -> None: """Recompute the cached outer vertex set, per-vertex closest inner points, and per-vertex gap if stale, i.e. if ``self._dirty`` is set (by :meth:`bootstrap`, :meth:`add_point`, or :meth:`add_cut` since the last refresh); a no-op otherwise. Called at the top of every :meth:`find_trial_point` / :meth:`max_gap`, so back-to-back calls to either (with no state change in between) reuse this same cached `_gap` array instead of recomputing it from `_outer_vertices`/ `_closest_points` each time. Solves ``closest_point_on_hull`` only for vertices whose generator id is new since the last refresh -- see :meth:`_vertices_with_ids` and the module docstring -- reusing the cached closest point/normal for every id that survived unchanged. Falls back to solving every vertex (the pre-caching behavior) whenever ids aren't available at all, or this call's vertex set came from a fresh rebuild whose ids aren't comparable to what was cached. Also accumulates into :attr:`stats` -- see :meth:`reset_stats`. """ if not self._dirty and self._outer_vertices is not None: return prev_ids = self._vertex_ids t0 = time.perf_counter() verts, ids, is_fresh = self._vertices_with_ids() self.stats["cdd_time"] += time.perf_counter() - t0 can_reuse = ids is not None and not is_fresh and prev_ids is not None if can_reuse: old_index_of_id = {vid: i for i, vid in enumerate(prev_ids)} new_id_set = set(ids) # None once a refresh without ids has made the counts unknown, until reset_stats(). if self.stats["n_new"] is not None: self.stats["n_new"] += sum(1 for vid in new_id_set if vid not in old_index_of_id) self.stats["n_removed"] += sum(1 for vid in prev_ids if vid not in new_id_set) closest = np.zeros((len(verts), self.k)) normals = np.zeros((len(verts), self.k)) to_solve = [i for i, vid in enumerate(ids) if vid not in old_index_of_id] for i, vid in enumerate(ids): old_i = old_index_of_id.get(vid) if old_i is not None: closest[i] = self._closest_points[old_i] normals[i] = self._closest_normals[old_i] if to_solve: t1 = time.perf_counter() results = list(self.executor.map( lambda i: self.projection_fn(verts[i], self.inner_vertices, norm=self.norm), to_solve )) self.stats["projection_time"] += time.perf_counter() - t1 for i, (c, n) in zip(to_solve, results): closest[i] = c normals[i] = n elif len(verts): if ids is not None: # A fresh rebuild's ids aren't comparable to prev_ids at all # (cddlib restarts id numbering) -- every current vertex # counts as new, every previous one as removed. if self.stats["n_new"] is not None: self.stats["n_new"] += len(verts) self.stats["n_removed"] += len(prev_ids) if prev_ids is not None else 0 else: self.stats["n_new"] = None self.stats["n_removed"] = None t1 = time.perf_counter() results = list(self.executor.map( lambda v: self.projection_fn(v, self.inner_vertices, norm=self.norm), verts )) self.stats["projection_time"] += time.perf_counter() - t1 closest = np.array([r[0] for r in results]) normals = np.array([r[1] for r in results]) if ids is not None else None else: if ids is not None: self.stats["n_removed"] += len(prev_ids) if prev_ids is not None else 0 else: self.stats["n_new"] = None self.stats["n_removed"] = None closest = np.zeros((0, self.k)) normals = np.zeros((0, self.k)) if ids is not None else None self.stats["n_total"] = len(verts) self._outer_vertices = verts self._vertex_ids = ids self._closest_points = closest self._closest_normals = normals self._gap = gaps(verts, closest, norm=self.norm) self._dirty = False
[docs] def find_trial_point(self) -> tuple[np.ndarray | None, float]: self._refresh() if len(self._outer_vertices) == 0: return None, 0.0 i = int(np.argmax(self._gap)) return self._outer_vertices[i], float(self._gap[i])
[docs] def find_trial_points_above_tol(self, tol: float) -> tuple[np.ndarray, np.ndarray]: """Like :meth:`find_trial_point`, but returns every outer vertex whose gap is at least `tol` (not just the single worst one), together with each one's own gap -- the first stage of solving several candidate closest-point targets in parallel instead of just one per iteration (see :mod:`mga_surveyor.explore`'s own docstring for why the single-target version can't be batched as-is: each iteration's target currently depends on the previous one's result). `tol` uses the same cutoff `explore.drive`'s own main loop applies before ever dispatching a solve for the single worst point: `gap < tol` means converged there, so `gap >= tol` (not the stricter `gap > tol`) is the matching "still worth solving" condition here -- a candidate right at `tol` exactly is still one `explore.drive` itself would have dispatched a solve for. Not part of the `Method` interface: `explore.drive` reaches it through :meth:`find_pool_trial_points`, found via `hasattr`. `BilevelMethod` has no analogous notion of "every other vertex above tol" to offer (its MILP reformulation finds the single worst point directly, without ever enumerating a vertex set), and `BBMethod` -- which does keep a vertex set -- doesn't implement it (yet), so this lives on `CddMethod` alone rather than on the shared base class. :param tol: The same convergence tolerance `explore.drive` itself is called with. No default -- see `explore.drive`'s own docstring on why it takes no default either. :returns: `(points, gaps)`, sorted by gap descending -- index 0 is the same point/gap `find_trial_point` itself would return. Both empty if the outer polytope has no vertices yet, or none are at least `tol`. """ self._refresh() if len(self._outer_vertices) == 0: return np.empty((0, self.k)), np.empty(0) above_tol = np.where(self._gap >= tol)[0] if len(above_tol) == 0: return np.empty((0, self.k)), np.empty(0) idx = above_tol[np.argsort(self._gap[above_tol])[::-1]] return self._outer_vertices[idx], self._gap[idx]
[docs] def find_pool_trial_points( self, max_parallel: int, tol: float, ) -> tuple[np.ndarray, np.ndarray]: """Batched stand-in for :meth:`find_trial_point`: up to `max_parallel` above-`tol` candidate trial points to solve in parallel instead of just the single worst one -- the `max_parallel` worst ones, since :meth:`find_trial_points_above_tol` already returns them sorted by gap descending. `explore.drive` calls this (found via `hasattr`) whenever its `max_parallel > 1`, solving the returned points in one batched `closest_point` call; with `max_parallel == 1`, or for a method without it, `drive` uses :meth:`find_trial_point` instead. :param max_parallel: Upper bound on how many points are returned -- meant to match however many parallel workers will actually solve them. :param tol: Passed straight to `find_trial_points_above_tol`. No default, for the same reason it has none there. :returns: `(points, gaps)`, capped at `max_parallel`, both empty if `find_trial_points_above_tol` itself returns nothing. """ above_tol_points, above_tol_gaps = self.find_trial_points_above_tol(tol) return above_tol_points[:max_parallel], above_tol_gaps[:max_parallel]
[docs] def max_gap(self) -> float: self._refresh() if len(self._outer_vertices) == 0: return 0.0 return float(self._gap.max())