Source code for mga_surveyor.explore

"""A generic driving loop (`drive`): bootstraps a `Method` from the 2k axis
directions, a known optimum, and any other already-known points/cuts, all
in one `method.bootstrap` call, then drives the main loop until convergence.
Parameterized by which `Method` to use and by external callbacks that
query the true region -- the only place in the package tying a method to
where points/cuts come from; drive/bootstrap a method directly with your
own code if this doesn't fit your use case.
"""
import itertools
import logging
import time
from typing import Protocol

import numpy as np

from .common import SEP_TOL_FACTOR, Halfspace, separates
from .methods.base import Method

logger = logging.getLogger(__name__)


[docs] class FurthestPointFn(Protocol): """Batched support-function query: given `(n, k)` directions, the points in the true region maximizing each `direction @ x`, together with each point's own separating-hyperplane normal (for a furthest-point query, always just the query direction itself).""" def __call__(self, directions: np.ndarray) -> tuple[np.ndarray, np.ndarray]: ...
[docs] class ClosestPointFn(Protocol): """The closest point in the true region to `target` under the method's norm, together with a valid separating-hyperplane normal there. Given a `(k,)` target it returns `(k,)` arrays; `drive`'s pool path (see `max_parallel`) also calls it with an `(n, k)` batch of targets and expects `(n, k)` arrays back.""" def __call__(self, target: np.ndarray) -> tuple[np.ndarray, np.ndarray]: ...
[docs] class OptimalPointFn(Protocol): """Zero-argument query: the true region's own known optimum -- a free extra point to seed the inner approximation with.""" def __call__(self) -> np.ndarray: ...
[docs] def box_directions(k: int) -> np.ndarray: """The `2k` axis directions `+-e_i` `drive`'s bootstrap queries `furthest_point` with -- factored out so anything that needs to presolve/intercept that same batch before `drive` gets to it (e.g. `mga_surveyor.normalize.presolve_box_points`) builds it identically.""" return np.vstack([np.eye(k), -np.eye(k)])
[docs] def drive( method: Method, furthest_point: FurthestPointFn, closest_point: ClosestPointFn, optimal_fn: OptimalPointFn, max_iter: int | None, tol: float, max_parallel: int, verbose: bool = True, extra_points: list[np.ndarray] | None = None, extra_halfspaces: list[Halfspace] | None = None, gap_scale: float = 1.0, gap_unit: str = "", incremental_bootstrap: bool = False, sep_tol: float | None = None, ) -> list[dict]: """Bootstrap `method` from the 2k axis directions +-e_i, `optimal_fn`'s point, and `extra_points`/`extra_halfspaces` if given -- all together in one `method.bootstrap` call, since `Method.bootstrap` must be called exactly once, before any `add_point`/`add_cut`/`find_trial_point` call -- then drive it through the main loop until the gap closes or `max_iter` is hit. No default -- every caller must decide; pass `None` explicitly for no cap (silent non-convergence is exactly what this forces a caller to consciously opt into, rather than getting it for free by omitting the argument). - `furthest_point(directions) -> (points, normals)`: called once, with all `2k` box directions, for bootstrapping only. - `closest_point(target) -> (point, normal)`: called each iteration with the worst-point search's trial point (or, on the pool path, an `(n, k)` batch of them -- see `max_parallel`). - `optimal_fn() -> point`: called once, before bootstrapping. - `extra_points`/`extra_halfspaces`: points/cuts already known from elsewhere (e.g. an earlier, interrupted run), folded into the same bootstrap call as the box directions and `optimal_fn`'s point -- unless `incremental_bootstrap` is set, see below. `incremental_bootstrap` (default `False`, preserving the single-batch behavior above for every existing caller): if `True`, `method.bootstrap` is instead called with ONLY the box directions + `optimal_fn`'s point, and `extra_points`/`extra_halfspaces` are folded in afterward one at a time (`add_point`/`add_cut`, each halfspace immediately followed by a forced `method.max_gap()` refresh) instead of batched into that same call. Exists because `CddMethod`'s single-batch from-scratch build (`cdd.polyhedron_from_matrix` over the WHOLE initial set at once) is far more prone to float mode's "Numerical inconsistency" failure than the same halfspaces appended one at a time -- confirmed against this project's real network: an alphabetically-ordered ~650-halfspace restart-reload crashed from-scratch but never once crashed when replayed incrementally (see `pypsa_ext.generate_mga_files`, the only caller that currently opts into this). Costs one extra `max_gap()` per extra halfspace, so only worth it for a method where that's cheap relative to a single huge from-scratch build -- true for `CddMethod`, almost certainly not for e.g. `BilevelMethod`, whose `max_gap()` solves a full MILP each time, so this is opt-in rather than the default. See `mga_surveyor.tests.lp_region`/`mga_surveyor.tests.synthetic_ball` for example implementations, or `pypsa_ext` for PyPSA-backed ones. Uses the closest-point-plus-dual-normal construction for the main loop: correct for any of the three norms, with no separate argument needed per norm. `gap_scale`/`gap_unit` (default `1.0`/`""`, i.e. no change): every logged gap is multiplied by `gap_scale` and suffixed with `gap_unit` before printing -- purely cosmetic, doesn't touch `tol`/`history`'s own values. Lets a caller display the gap however it originally expressed `tol` (e.g. as a percentage) instead of `drive`'s own internal units. `sep_tol` (default `None` -> `tol * common.SEP_TOL_FACTOR`, same units as `tol`): a closest point more than `sep_tol` from its trial point counts as separating and its cut is added (`common.separates`); at or below it the trial point was already feasible and no cut is added. Returns a history list of dicts, one per POINT processed (see `max_parallel` below for when that can be more than one per loop iteration), with keys "iter", "gap", "trial_point", "new_point", "cut_added", "trial_point_time" (seconds spent inside this iteration's own worst-point search -- the one part of each iteration whose cost scales with the method's own accumulated state, e.g. CddMethod's growing outer_halfspaces, unlike closest_point's cost which is external to `drive` itself; attributed to the first point of a multi-point iteration, `0.0` for the rest of that same iteration, so summing it across `history` still gives the true total search-time cost). If `max_iter` is exhausted before `gap < tol`, logs a warning (the return value itself doesn't flag this -- check `history[-1]["gap"]` against `tol`, or the caller's own `method.max_gap()`, to detect it programmatically). `max_parallel`: no default -- every caller must decide, same reasoning as `max_iter`/`tol` above. When `max_parallel > 1` AND `method` actually supports it (checked via `hasattr` -- currently only `CddMethod.find_pool_trial_points`; anything else, `BBMethod` and `BilevelMethod` included, falls back to the original single-target path, logged when `verbose`), each iteration finds up to `max_parallel` of the worst, still-unconverged candidate trial points at once instead of just the single worst one, and solves all of them in one batched `closest_point` call -- exploiting `closest_point`'s own existing batch/parallel support (see `pypsa_ext.make_closest_point_fn`, whose own worker-pool size this same `max_parallel` also controls) instead of the strictly one-at-a-time solves the sequential path is limited to. Pass `1` for today's original single-target behavior. No extra reconciliation is needed when several candidates land in one round: each one's own `(point, normal)` is an independently valid supporting halfspace of the TRUE region (it comes straight from that candidate's own `closest_point` query against the real system, never from the outer polytope's own current state) -- intersecting halfspaces is commutative/associative, so folding in several at once from one round (all chosen against the same, necessarily slightly stale, pre-round snapshot) is exactly as correct as adding them one at a time would have been. It just isn't necessarily as efficient: a later candidate in the round might not still have been the worst point had the earlier ones already been folded in first -- an exploration-strategy tradeoff, not a correctness one. """ if sep_tol is None: sep_tol = tol * SEP_TOL_FACTOR if not 0 <= sep_tol < tol: # sep_tol >= tol: a trial point whose closest point lies between tol # and sep_tol away would get no cut while its gap stays >= tol, so # drive would pick the same vertex again until max_iter. A negative # one would accept the degenerate normals of already-feasible targets. msg = f"sep_tol must satisfy 0 <= sep_tol < tol, got sep_tol={sep_tol}, tol={tol}" raise ValueError(msg) if verbose: logger.info("[drive] furthest-point queries: bootstrapping %d box direction(s)", 2 * method.k) box_points, box_normals = furthest_point(box_directions(method.k)) box_points = np.asarray(box_points, dtype=float) if incremental_bootstrap: method.bootstrap([*box_points, np.asarray(optimal_fn(), dtype=float)], list(zip(box_normals, box_points))) for point in extra_points or []: method.add_point(point) for direction, point in extra_halfspaces or []: method.add_cut(direction, point) method.max_gap() # forces this cut's own incremental append now, one at a time else: initial_points = [*box_points, np.asarray(optimal_fn(), dtype=float), *(extra_points or [])] initial_halfspaces = [*zip(box_normals, box_points), *(extra_halfspaces or [])] method.bootstrap(initial_points, initial_halfspaces) use_pool = max_parallel > 1 and hasattr(method, "find_pool_trial_points") if max_parallel > 1 and not use_pool and verbose: logger.info( "[drive] max_parallel=%d requested, but %s has no find_pool_trial_points -- " "falling back to the single-target path", max_parallel, type(method).__name__, ) history = [] last_gap = float("nan") if verbose: logger.info("[drive] closest-point queries: main loop starting") iters = itertools.count() if max_iter is None else range(max_iter) for it in iters: trial_point_start = time.perf_counter() if use_pool: trial_points, trial_gaps = method.find_pool_trial_points(max_parallel, tol) trial_point_time = time.perf_counter() - trial_point_start if len(trial_points) == 0: # No gap to report here -- find_pool_trial_points only # returns candidates still above tol, so an empty result # doesn't tell us the actual (necessarily below-tol) gap, # unlike find_trial_point's own always-computed one below. if verbose: logger.info( "[drive] converged at iter %d (find_pool_trial_points: %.3fs)", it, trial_point_time, ) break last_gap = float(trial_gaps[0]) if verbose: logger.info( "[drive] iter %4d: gap=%.4f%s pool_size=%d -- solving (find_pool_trial_points: %.3fs)", it + 1, last_gap * gap_scale, gap_unit, len(trial_points), trial_point_time, ) new_points, normals = closest_point(trial_points) new_points = np.atleast_2d(np.asarray(new_points, dtype=float)) normals = np.atleast_2d(np.asarray(normals, dtype=float)) # No extra reconciliation needed across this round's own # candidates -- see this function's own docstring for why # each one's (point, normal) is independently valid regardless # of the others. for i in range(len(trial_points)): trial_point, new_point, normal = trial_points[i], new_points[i], normals[i] method.add_point(new_point) cut_added = separates(new_point, trial_point, sep_tol, method.norm) if cut_added: method.add_cut(normal, new_point) history.append({ "iter": it + 1, "gap": float(trial_gaps[i]), "trial_point": trial_point, "new_point": new_point, "cut_added": cut_added, "trial_point_time": trial_point_time if i == 0 else 0.0, }) if verbose: n_cuts = sum(h["cut_added"] for h in history[-len(trial_points):]) logger.info( "[drive] iter %4d: done -- cuts_added=%d/%d", it + 1, n_cuts, len(trial_points), ) continue trial_point, gap = method.find_trial_point() trial_point_time = time.perf_counter() - trial_point_start last_gap = gap if trial_point is None or gap < tol: if verbose: logger.info( "[drive] converged at iter %d: gap=%.4f%s (find_trial_point: %.3fs)", it, gap * gap_scale, gap_unit, trial_point_time, ) break new_point, normal = closest_point(trial_point) new_point = np.asarray(new_point, dtype=float) method.add_point(new_point) # Cut only needed if the closest point differs from the trial # point, i.e. the trial point itself was infeasible: more than # sep_tol away (common.separates), not the convergence tol -- # a trial point within tol of the region but outside it still # yields valid, tightening cuts. Measured under method.norm, the # same metric find_trial_point's own gap is measured under, not a # hardcoded L2 distance (up to sqrt(k)x off for L2 vs Linf in k # dimensions). cut_added = separates(new_point, trial_point, sep_tol, method.norm) if cut_added: method.add_cut(normal, new_point) history.append({ "iter": it + 1, "gap": gap, "trial_point": trial_point, "new_point": new_point, "cut_added": cut_added, "trial_point_time": trial_point_time, }) if verbose: logger.info( "[drive] iter %4d: gap=%.4f%s cut_added=%s (find_trial_point: %.3fs)", it + 1, gap * gap_scale, gap_unit, cut_added, trial_point_time, ) else: # for...else: only reached if the loop ran out of iterations # without ever hitting the `break` above -- i.e. max_iter was # exhausted while still above tol. Silent otherwise (no log line, # no exception), so a caller that doesn't inspect the returned # history could easily mistake this for genuine convergence. if max_iter is not None: logger.warning( "[drive] did NOT converge within max_iter=%d iterations: final gap=%.4f%s (tol=%.4f%s)", max_iter, last_gap * gap_scale, gap_unit, tol * gap_scale, gap_unit, ) return history