Source code for mga_surveyor.methods.bb

"""``BBMethod``.

- Uses SciPy's ``ConvexHull`` (Qhull) on the polar dual of the outer
  polytope's halfspaces to compute the outer polytope's vertex set
  (H-to-V enumeration) -- an alternative engine to :class:`~mga_surveyor.
  methods.cdd.CddMethod`'s cddlib Double Description method. See
  :mod:`mga_surveyor.methods.base` for the general ``Method`` contract this
  mirrors; this class implements the same ``bootstrap``/``add_point``/``add_cut``/
  ``find_trial_point``/``max_gap`` interface, just backed by a different
  vertex-enumeration algorithm.

- Named for the incremental algorithm, not the one-off initial build:
  Qhull only runs its usual divide-and-conquer quickhull ONCE, the first
  time enough dual points have accumulated to form an initial simplex
  hull (see :meth:`_add_halfspace`). Every subsequent dual point --
  i.e. every :meth:`add_cut` for the rest of this object's life, which in
  production usage is the overwhelming majority of calls -- goes through
  ``ConvexHull.add_points`` on that already-built hull, which Qhull
  documents as switching to a beneath-and-beyond insertion (find the
  facets the new point sees "beyond", remove them, stitch in new facets
  from the point to the resulting horizon ridge -- see Preparata & Shamos)
  rather than rerunning quickhull from scratch. That incremental step is
  what this class actually spends its time doing, hence the name.

- The polar-dual construction requires a fixed reference point ``x0``
  strictly inside every halfspace registered so far (a standard
  requirement of this technique -- see e.g. Preparata & Shamos): a
  halfspace ``{x : direction@(x-point) <= 0}``, recentered at ``x0``, maps
  to the dual point ``direction / b`` where ``b = direction@(point-x0)``,
  which is only well-defined (and the resulting dual facet/primal vertex
  correspondence only valid) when ``b > 0``, i.e. ``x0`` strictly satisfies
  the halfspace. By default, :meth:`BBMethod.bootstrap` uses the
  centroid (mean) of ``initial_points`` as ``x0`` and keeps it fixed for
  the method's lifetime; pass ``origin`` to :meth:`__init__` instead when
  a specific point is *known* to be strictly (and durably, not just
  barely) interior -- see that parameter's own docstring. Either way this
  is a heuristic, not a guarantee: the ``Method`` interface doesn't
  designate any one of ``initial_points`` as "the" interior reference
  point, and no fixed choice is guaranteed interior for every possible
  caller. If a later :meth:`add_cut` (or the initial halfspaces
  themselves) violates ``x0``'s interiority, :func:`_dual_point` raises
  ``ValueError`` immediately rather than silently returning a wrong vertex
  set -- in practice this hasn't triggered for the box-plus-optimal-point
  bootstrap pattern :mod:`mga_surveyor.explore` actually uses, since the
  centroid of a box's extreme points plus one interior (near-optimal)
  point lands well inside the box.

- As with :func:`~mga_surveyor.methods.cdd._halfspace_row`, each
  halfspace's ``direction`` is unit-normalized (divided by its own
  Euclidean norm) before its dual point is computed. Scaling a halfspace's
  defining vector by any positive constant doesn't change the halfspace
  itself, so this is free geometrically; it matters here for the same
  reason it matters for cdd's float backend: Qhull's own degeneracy/
  coplanarity tests compare against a fixed relative tolerance internally,
  and cuts arriving at wildly different natural magnitudes (as they do on
  this project's real networks) make that tolerance inconsistently loose
  or tight from cut to cut. Putting every cut on the same (unit) scale
  before dualizing removes that inconsistency.

- Unlike ``CddMethod``, Qhull's incremental ``add_points`` doesn't expose
  any persistent per-vertex identity across an update (cddlib's patched
  ``copy_generators_with_ids`` has no Qhull equivalent), so this class
  can't tell "this is the same vertex as before the last cut" by a true
  id. It approximates one instead: :func:`_vertex_hash` rounds a vertex's
  coordinates to :data:`_VERTEX_HASH_DECIMALS` places and uses the
  resulting tuple as a stand-in identity, on the empirical grounds (see
  ``qhull_survival_check.py`` in project notes) that on this project's
  real networks, 80-98% of a refresh's vertices reproduce bit-identical
  coordinates (well past 1e-9, tighter than the 1e-8 used here) from one
  ``add_cut`` to the next -- only the vertices a cut actually creates or
  destroys change at all. :meth:`_refresh` uses this hash exactly the way
  ``CddMethod._refresh`` uses a real id: build a hash->index lookup from
  the PREVIOUS refresh's vertices, and for the new vertex set, reuse the
  cached closest point/normal for every hash that survived unchanged,
  solving ``closest_point_on_hull`` only for the ones that didn't. A
  false-positive hash collision (two geometrically distinct vertices
  rounding to the same tuple) would silently reuse the wrong cached
  value -- :data:`_VERTEX_HASH_DECIMALS` (a ``1e-8`` grid) is chosen
  coarser than the ``~1e-9`` roundoff a surviving vertex's coordinates can
  pick up between refreshes, yet far finer than the spacing of genuinely
  distinct vertices, so that doesn't happen in practice; a false negative (a survived vertex hashing
  differently by tiny roundoff) only costs an avoidable re-solve, never
  correctness. :meth:`add_point` still uses its own, separate,
  non-hash-based reuse for the same reason it always has -- growing the
  inner approximation never changes the outer vertex set at all, so
  :meth:`_refresh_stale_closest_points` can just re-use the existing
  arrays directly, no identity of any kind needed.
"""
from concurrent.futures import Executor
from typing import Literal, Protocol

import numpy as np
from scipy.spatial import ConvexHull, QhullError

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


[docs] class ProjectionFn(Protocol): """Contract for `projection_fn` -- see `mga_surveyor.methods.cdd.ProjectionFn`.""" def __call__(self, point: np.ndarray, points: np.ndarray, norm: Norm) -> tuple[np.ndarray, np.ndarray]: ...
#: Rounding precision used by :func:`_vertex_hash` -- see the module #: docstring's note on hash-based vertex identity. Matches #: ``_compute_outer_vertices``'s own internal dedup rounding, so hashing #: its output loses no additional precision beyond what that step already #: commits to. _VERTEX_HASH_DECIMALS = 8 def _vertex_hash(vertex: np.ndarray) -> tuple: """A vertex's coordinates, rounded to :data:`_VERTEX_HASH_DECIMALS` places, as a hashable stand-in for a persistent id -- see module docstring. """ return tuple(np.round(vertex, decimals=_VERTEX_HASH_DECIMALS)) def _dual_point(direction: np.ndarray, point: np.ndarray, origin: np.ndarray) -> np.ndarray: """Maps the halfspace ``{x : direction@(x-point) <= 0}`` to its polar dual point relative to ``origin``. ``direction`` is unit-normalized first -- see the module docstring. Recentering at ``origin`` rewrites the halfspace as ``direction@(x-origin) <= direction@(point-origin)``, i.e. ``A@y <= b`` with ``y = x-origin``, ``A = direction``, ``b = direction@(point-origin)``; the dual point is ``A/b``. :raises ValueError: if ``b <= 0``, i.e. ``origin`` doesn't lie strictly inside this halfspace -- meaning ``origin`` isn't a valid interior reference point for the dual construction (see module docstring). """ direction = np.asarray(direction, dtype=float) direction_norm = np.linalg.norm(direction) if direction_norm > 0: direction = direction / direction_norm b = float(direction @ (np.asarray(point, dtype=float) - origin)) if b <= 0: raise ValueError( f"origin must lie strictly inside every halfspace for the polar-dual " f"construction; got b={b} for this one (origin is on the boundary or " f"outside it)" ) return direction / b
[docs] class BBMethod(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 projection_fn: Lower-level override of the inner-hull projection callable itself -- takes precedence over ``projection_backend`` if given. See ``CddMethod``'s own docstring for the exact contract. :param projection_backend: Which persistent solver to use for the inner-hull projection -- ``'gurobi'`` (default) or ``'highs'``. :type projection_backend: str :param origin: Fixed interior reference point for the polar-dual construction (see module docstring) -- overrides the default centroid-of-``initial_points`` heuristic :meth:`bootstrap` would otherwise use. Pick this explicitly whenever a specific point is *known* to be strictly interior to every halfspace for the whole run. Neither :mod:`mga_surveyor.explore` nor ``pypsa_ext`` passes one, and the cost-optimal point is not automatically safe (it can sit on a box face, e.g. a capacity at its lower bound, giving ``b = 0``) -- the centroid of a caller's initial points is only a heuristic and isn't guaranteed interior, and even when it is, staying strictly interior isn't the same as staying *well inside*: as cuts accumulate and the true region shrinks around a FIXED origin over many iterations, some halfspace's ``b = direction@ (point-origin)`` can shrink towards zero even while staying positive, degrading that halfspace's dual point ``direction/b`` (and hence the vertices it participates in) numerically -- a plausible explanation if this class's vertex set/gap ever starts drifting from ``CddMethod``'s on the same problem after many iterations. A point known to stay comfortably interior throughout (rather than one recomputed once from whatever happens to be in ``initial_points``) avoids that. No default -- ``None`` keeps the centroid heuristic. :raises ValueError: If ``projection_backend`` is not ``'gurobi'`` or ``'highs'``. """ def __init__( self, k: int, norm: Norm, executor: Executor | None = None, projection_fn: ProjectionFn | None = None, projection_backend: Literal["gurobi", "highs"] = "gurobi", origin: np.ndarray | None = None, ) -> None: check_norm(norm) super().__init__(k, norm) self._origin_override = None if origin is None else np.asarray(origin, dtype=float) if executor is None: from concurrent.futures import ThreadPoolExecutor executor = ThreadPoolExecutor(max_workers=8) self.executor = executor self.projection_backend = projection_backend if projection_fn is not None: self.projection_fn = projection_fn elif projection_backend == "highs": 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._origin = None self._dual_points = [] # aligned with outer_halfspaces self._hull = None # incremental scipy.spatial.ConvexHull over self._dual_points, or None until enough points self._outer_vertices = None self._vertex_hashes = None # hash-based stand-in ids, aligned with self._outer_vertices -- see module docstring self._closest_points = None self._closest_normals = None self._gap = None self._outer_stale = True # True whenever the outer vertex set itself may have changed since last refresh self._dirty = True
[docs] def bootstrap(self, initial_points: list[np.ndarray], initial_halfspaces: list[Halfspace]) -> None: self.inner_vertices = np.array(initial_points, dtype=float) self._origin = self._origin_override if self._origin_override is not None else self.inner_vertices.mean(axis=0) self.outer_halfspaces = [] self._dual_points = [] self._hull = None self._outer_vertices = None self._vertex_hashes = None self._closest_points = None self._closest_normals = None self._outer_stale = True self._dirty = True for direction, point in initial_halfspaces: self._add_halfspace(direction, point)
[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: """Identical in spirit to ``CddMethod``'s own: after the inner approximation grows, recompute only the cached closest-point/normal pairs that ``new_inner_vertex`` actually invalidates, not every vertex. Valid without any persistent vertex identity because the outer vertex set itself (``self._outer_vertices``, aligned with ``self._closest_points``/``self._closest_normals``) doesn't change between :meth:`add_cut` calls -- only :meth:`add_cut` rebuilds it. :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] if len(stale_positions) == 0: return stale_points = list(self._outer_vertices[stale_positions]) results = list(self.executor.map( lambda p: self.projection_fn(p, self.inner_vertices, norm=self.norm), stale_points )) for pos, (c, n) in zip(stale_positions.tolist(), results): self._closest_points[pos] = c self._closest_normals[pos] = n def _add_halfspace(self, direction: np.ndarray, point: np.ndarray) -> None: direction = np.asarray(direction, dtype=float) point = np.asarray(point, dtype=float) dual = _dual_point(direction, point, self._origin) self.outer_halfspaces.append((direction, point)) self._dual_points.append(dual) num_points = len(self._dual_points) if num_points <= self.k: return # Qhull needs at least k+1 points to form an initial d-simplex hull if self._hull is None: try: self._hull = ConvexHull(np.array(self._dual_points), incremental=True) except QhullError: pass # initial dual points are coplanar/degenerate; try again once more have accumulated else: self._hull.add_points(dual.reshape(1, -1))
[docs] def add_cut(self, direction: np.ndarray, point: np.ndarray) -> None: self._add_halfspace(direction, point) self._outer_stale = True self._dirty = True
def _compute_outer_vertices(self) -> np.ndarray: """The outer polytope's current vertex set, recovered from the dual hull's facets -- cheap: reads ``self._hull.equations`` as it already stands, doesn't trigger any new Qhull computation (that happens in :meth:`_add_halfspace` instead, via ``add_points``). """ if self._hull is None: return np.zeros((0, self.k)) equations = self._hull.equations # shape (num_facets, k+1): [normal | offset] normals = equations[:, :-1] offsets = equations[:, -1] valid_mask = ~np.isclose(offsets, 0) # a facet through the dual origin has no primal image primal = -normals[valid_mask] / offsets[valid_mask, np.newaxis] unique = np.unique(np.round(primal, decimals=_VERTEX_HASH_DECIMALS), axis=0) return unique + self._origin def _refresh(self) -> None: """Recompute the cached outer vertex set (if stale) and per-vertex closest inner points/gap (if the outer vertex set changed, or an inner point invalidated some of the cache) -- if stale, solves ``closest_point_on_hull`` only for vertices whose hash (see module docstring) is new since the last refresh, reusing the cached closest point/normal for every hash that survived unchanged -- the same shape of optimization ``CddMethod._refresh`` does with a real id, here keyed by rounded coordinates instead. """ if not self._dirty and self._outer_vertices is not None: return if self._outer_stale or self._outer_vertices is None: verts = self._compute_outer_vertices() new_hashes = [_vertex_hash(v) for v in verts] old_index_of_hash = ( {h: i for i, h in enumerate(self._vertex_hashes)} if self._vertex_hashes is not None else {} ) if len(verts): closest = np.zeros((len(verts), self.k)) normals = np.zeros((len(verts), self.k)) to_solve = [] for i, h in enumerate(new_hashes): old_i = old_index_of_hash.get(h) if old_i is not None: closest[i] = self._closest_points[old_i] normals[i] = self._closest_normals[old_i] else: to_solve.append(i) if to_solve: results = list(self.executor.map( lambda i: self.projection_fn(verts[i], self.inner_vertices, norm=self.norm), to_solve )) for i, (c, n) in zip(to_solve, results): closest[i] = c normals[i] = n else: closest = np.zeros((0, self.k)) normals = np.zeros((0, self.k)) self._outer_vertices = verts self._vertex_hashes = new_hashes self._closest_points = closest self._closest_normals = normals self._outer_stale = False self._gap = gaps(self._outer_vertices, self._closest_points, norm=self.norm) self._dirty = False def _check_hull_built(self) -> None: # An empty vertex set is only legitimate before bootstrap: once # halfspaces have been added, no hull means Qhull failed on every # build so far, and returning (None, 0.0) would let drive report # convergence at iteration 0. if self._hull is None and self.outer_halfspaces: msg = ( f"BBMethod has {len(self.outer_halfspaces)} halfspace(s) but no dual hull -- the outer " "polytope is unbounded (k or fewer halfspaces) or Qhull failed on every build so far" ) raise RuntimeError(msg)
[docs] def find_trial_point(self) -> tuple[np.ndarray | None, float]: self._refresh() self._check_hull_built() 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 max_gap(self) -> float: self._refresh() self._check_hull_built() if len(self._outer_vertices) == 0: return 0.0 return float(self._gap.max())