MGA Surveyor API¶
Exploration loop¶
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.
- class mga_surveyor.explore.FurthestPointFn(*args, **kwargs)[source]¶
Bases:
ProtocolBatched support-function query: given
(n, k)directions, the points in the true region maximizing eachdirection @ x, together with each point’s own separating-hyperplane normal (for a furthest-point query, always just the query direction itself).
- class mga_surveyor.explore.ClosestPointFn(*args, **kwargs)[source]¶
Bases:
ProtocolThe closest point in the true region to
targetunder the method’s norm, together with a valid separating-hyperplane normal there. Given a(k,)target it returns(k,)arrays;drive’s pool path (seemax_parallel) also calls it with an(n, k)batch of targets and expects(n, k)arrays back.
- class mga_surveyor.explore.OptimalPointFn(*args, **kwargs)[source]¶
Bases:
ProtocolZero-argument query: the true region’s own known optimum – a free extra point to seed the inner approximation with.
- mga_surveyor.explore.box_directions(k)[source]¶
The
2kaxis directions+-e_idrive’s bootstrap queriesfurthest_pointwith – factored out so anything that needs to presolve/intercept that same batch beforedrivegets to it (e.g.mga_surveyor.normalize.presolve_box_points) builds it identically.
- mga_surveyor.explore.drive(method, furthest_point, closest_point, optimal_fn, max_iter, tol, max_parallel, verbose=True, extra_points=None, extra_halfspaces=None, gap_scale=1.0, gap_unit='', incremental_bootstrap=False, sep_tol=None)[source]¶
Bootstrap
methodfrom the 2k axis directions +-e_i,optimal_fn’s point, andextra_points/extra_halfspacesif given – all together in onemethod.bootstrapcall, sinceMethod.bootstrapmust be called exactly once, before anyadd_point/add_cut/find_trial_pointcall – then drive it through the main loop until the gap closes ormax_iteris hit. No default – every caller must decide; passNoneexplicitly 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 all2kbox 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 – seemax_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 andoptimal_fn’s point – unlessincremental_bootstrapis set, see below.
incremental_bootstrap(defaultFalse, preserving the single-batch behavior above for every existing caller): ifTrue,method.bootstrapis instead called with ONLY the box directions +optimal_fn’s point, andextra_points/extra_halfspacesare folded in afterward one at a time (add_point/add_cut, each halfspace immediately followed by a forcedmethod.max_gap()refresh) instead of batched into that same call. Exists becauseCddMethod’s single-batch from-scratch build (cdd.polyhedron_from_matrixover 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 (seepypsa_ext.generate_mga_files, the only caller that currently opts into this). Costs one extramax_gap()per extra halfspace, so only worth it for a method where that’s cheap relative to a single huge from-scratch build – true forCddMethod, almost certainly not for e.g.BilevelMethod, whosemax_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_ballfor example implementations, orpypsa_extfor 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(default1.0/"", i.e. no change): every logged gap is multiplied bygap_scaleand suffixed withgap_unitbefore printing – purely cosmetic, doesn’t touchtol/history’s own values. Lets a caller display the gap however it originally expressedtol(e.g. as a percentage) instead ofdrive’s own internal units.sep_tol(defaultNone->tol * common.SEP_TOL_FACTOR, same units astol): a closest point more thansep_tolfrom 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_parallelbelow 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 todriveitself; attributed to the first point of a multi-point iteration,0.0for the rest of that same iteration, so summing it acrosshistorystill gives the true total search-time cost). Ifmax_iteris exhausted beforegap < tol, logs a warning (the return value itself doesn’t flag this – checkhistory[-1]["gap"]againsttol, or the caller’s ownmethod.max_gap(), to detect it programmatically).max_parallel: no default – every caller must decide, same reasoning asmax_iter/tolabove. Whenmax_parallel > 1ANDmethodactually supports it (checked viahasattr– currently onlyCddMethod.find_pool_trial_points; anything else,BBMethodandBilevelMethodincluded, falls back to the original single-target path, logged whenverbose), each iteration finds up tomax_parallelof the worst, still-unconverged candidate trial points at once instead of just the single worst one, and solves all of them in one batchedclosest_pointcall – exploitingclosest_point’s own existing batch/parallel support (seepypsa_ext.make_closest_point_fn, whose own worker-pool size this samemax_parallelalso controls) instead of the strictly one-at-a-time solves the sequential path is limited to. Pass1for 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 ownclosest_pointquery 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.- Parameters:
method (Method)
furthest_point (FurthestPointFn)
closest_point (ClosestPointFn)
optimal_fn (OptimalPointFn)
max_iter (int | None)
tol (float)
max_parallel (int)
verbose (bool)
gap_scale (float)
gap_unit (str)
incremental_bootstrap (bool)
sep_tol (float | None)
- Return type:
PyPSA integration¶
Run PyPSA’s Modelling-to-Generate-Alternatives (MGA) against a real, already-solved network, optionally caching each solved point as NetCDF.
make_optimality_fn builds a callable that solves and caches n’s own cost-minimizing optimum at output_dir/optimal.nc, returning its point in dimensions space – the precondition every other function here assumes. Also pins that point’s coordinates and re-solves for real per-dimension duals, cached in n.meta[“duals”] – same pinned-resolve idea as make_furthest_point_fn/make_closest_point_fn’s own resolve_main_objective.
make_furthest_point_fn solves MGA in one or more directions: a batched support-function query against n’s near-optimal feasible region. Always returns (points, normals) – normal is just the query direction, free. resolve_main_objective=True (default) additionally does the pinned-coordinate re-solve for real duals/obj, cached in n.meta but not part of the return value (pass False to skip that extra solve). Has its own dedicated solver/worker/cache (_build_furthest_point_solver/_init_furthest_point_worker/ _solve_furthest_point_direction), reused across a whole batch instead of rebuilt per direction.
make_closest_point_fn finds the closest point in n’s near-optimal region to a target, plus a separating-hyperplane normal – PyPSA has no built-in equivalent. Always solves fresh – output_dir, if given, is export-only, never read back to skip a solve. resolve_main_objective=True (default) also pins that point’s coordinates and re-solves the original objective for real per-dimension duals, exported in n.meta but not part of the return value (still just (point, normal), matching explore.ClosestPointFn); pass False to skip that re-solve. A single-target call reuses one persistent in-process model; a batch spreads targets across a multiprocessing.Pool, each worker building its own solver once. Only l1/linf supported (l2 needs a quadratic objective, Gurobi-only).
Both batch paths pass the PyPSA Network directly to worker processes (picklable as of PyPSA 1.3.0, github.com/PyPSA/PyPSA/pull/1889) instead of exporting to NetCDF and reloading. make_closest_point_fn’s batch path also snapshots n via pickle before any solve can mutate it, since Network.copy() refuses on a network with an attached solver model.
make_oracle_fns builds all three of the above in one call, sharing n/dimensions/output_dir – a convenience for feeding explore.drive’s three callback parameters directly.
generate_mga_files runs a BBMethod or CddMethod (float) (vertex_method) per slack level (via explore.drive) against a real network, writing every result to .nc files under output_dir – resuming from whatever’s already there (cached optimal/furthest-point solves are read back, and existing closest-point results are folded into each slack level’s own explore.drive call as its extra_points/extra_halfspaces). mga_surveyor.export is the other half: given just an output_dir, collect_near_optimal_set reads every result .nc file there back as a near-optimal set (mga_format), independent of a live run.
- mga_surveyor.pypsa_ext.make_optimality_fn(n, dimensions, output_dir, **kwargs)[source]¶
Build a callable that solves
n’s own cost-minimizing optimum, caches it atoutput_dir/optimal.nc, and returns its point indimensionsspace – structurally mirrorsmake_furthest_point_fn/make_closest_point_fn.After solving, the optimal point’s coordinates are pinned and the same cost objective is re-solved to read real per-dimension duals off those pinned constraints – the marginal cost of each dimension at the optimum – cached alongside the point in
n.meta["duals"], same idea asmake_furthest_point_fn/make_closest_point_fn’s ownresolve_main_objective. The optimum’s own cost is cached too, inn.meta["obj"], same as every other result file this module writes – soexport.collect_near_optimal_setnever needs to recompute it.dimensionsitself is cached inn.meta["dimensions"]too – the one piece of per-run metadata every other.ncfile inoutput_dirneeds to be interpreted, soexport.collect_near_optimal_setcan read it back from here instead of needing it passed in again.If
output_dir/optimal.ncalready exists, its point is read back fromn.meta["coordinates"](stashed there on save, same as everywhere else in this module) instead of re-solving.- Raises:
RuntimeError – If a solve does not reach
status="ok".- Parameters:
- Return type:
Callable[[], np.ndarray]
- mga_surveyor.pypsa_ext.make_furthest_point_fn(n, dimensions, slack, output_dir=None, resolve_main_objective=True, snapshots=None, multi_investment_periods=False, model_kwargs=None, max_parallel=4, on_solve=None, **kwargs)[source]¶
Build a batched MGA-direction query against a real, already-solved PyPSA network
n.The returned callable takes
directions– an(n_directions, k)array (a single(k,)direction is promoted to a length-1 batch) – and always returns(points, normals): each direction’s point inn’s near-optimal feasible region ((n_directions, k), not shape-preserving – a single direction still comes back as a length-1 array) and its separating-hyperplane normal, which for a furthest-point query is just the query direction itself, echoed back (free – no extra solve).resolve_main_objective=True(default) additionally pins each found point’s queried coordinate(s) (the direction’s nonzero entries) and re-solves the original cost objective – the cheapest system with that extreme coordinate. Its point is cached asn.meta["coordinates"], with its capex+opex cost inn.meta["obj"]and the pins’ duals inn.meta["duals"](0 for every unpinned dimension); the furthest point itself goes ton.meta["support_point"](see_cache_furthest_point_result). Neither is part of the return value (kept fixed at(points, normals)either way, so callers – e.g.explore.drive– don’t need to know which was used). PassFalseto skip that extra solve.dimensions’ key order fixes the axis order ofdirections/points/normals.Caching: pass a persistent
output_dirto cache each direction’s result atoutput_dir/mga_furthest_result_{key}.nc, content-addressed by the direction itself (seeencode_cache_key).None(default) disables caching. A cache hit on the single-direction path skips solving entirely, sonis NOT mutated by a call that only reads a cache hit.on_solve(point, normal, obj, duals)(defaultNone): called once per direction actually reported here – fresh solve or cache hit alike – with data that’s otherwise discarded from the return value:pointis the cachedcoordinates(the pointobj/dualsdescribe, not necessarily the returned support point), plusobjandduals(dualsisNonewhen that direction’s ownresolve_main_objectivewasFalse, cached or not). Lets a caller (e.g. one wanting objective cuts from these points – notgenerate_mga_files, which deliberately excludes box-point objective cuts) tap into the same solve without changingfurthest_points’ own(points, normals)contract. Always called back in this process, never inside a worker – the batch path’s Pool results are collected here first.- Raises:
RuntimeError – If a solve does not reach
status="ok"(see_build_furthest_point_solver).- Parameters:
n (Network)
dimensions (dict)
slack (float)
output_dir (str | Path | None)
resolve_main_objective (bool)
snapshots (Sequence | None)
multi_investment_periods (bool)
model_kwargs (dict | None)
max_parallel (int)
on_solve (Callable[[np.ndarray, np.ndarray, float, np.ndarray | None], None] | None)
kwargs (Any)
- Return type:
Callable[[np.ndarray], tuple[np.ndarray, np.ndarray]]
- mga_surveyor.pypsa_ext.make_closest_point_fn(n, dimensions, norm, slack, output_dir=None, resolve_main_objective=True, snapshots=None, multi_investment_periods=False, model_kwargs=None, max_parallel=4, weights=None, on_solve=None, **kwargs)[source]¶
Build a
mga_surveyor.explore.ClosestPointFnagainst a real, already-solved PyPSA networkn: the closest point inn’s near-optimal feasible region to a giventarget, plus a valid separating-hyperplane normal there.Export only, not a cache: pass a persistent
output_dirand every call solves fresh and then writes its result tooutput_dir/mga_closest_result_{key}.nc, content-addressed by the target itself (seeencode_cache_key) – but an existing file there is never read back or used to skip solving; re-running with the same target just re-solves and overwrites it.None(default) disables exporting entirely. Each exported.ncalso stashes the found point’s own capex+opex cost inn.meta["obj"], same asmake_furthest_point_fn’s own export.weights(defaultNone, i.e. every dimension weighted1.0– the plain unweighted norm): scales each dimension’s residual in the closest-point objective before it enters the L1/Linf norm, so “closest” means closest under a per-dimension-scaled metric instead of raw real units – seemga_surveyor.normalize.normalize_oracle_fns, which is what actually needs this (pass itsAffineMap.weightshere to make the point found consistent with the cube-normalized geometryexplore.driveis exploring). Points/normals returned are still always in real units regardless ofweights– only the objective used to find them changes.If
resolve_main_objective: after finding the closest point, its coordinates are pinned and the network’s original cost objective is re-solved to get real per-dimension duals, cached alongsidepoint/normalinn.meta["duals"]– same idea asmake_furthest_point_fn’s ownresolve_main_objective. This is extra work cached as a side effect only:closest_point’s own return value is unaffected, always(point, normal), so it still matchesexplore.ClosestPointFn.on_solve(point, normal, obj, duals, target)(defaultNone): called once per target actually solved – single or each one of a batch – with data that’s otherwise discarded from the return value (obj,duals;dualsisNonewhenresolve_main_objectiveisFalse), plus thetargetthat was queried (unlikemake_furthest_point_fn’s ownon_solve, which has no equivalent – a support-function query has no “target” a found point could be compared against). Always called back in this process, never inside a worker.- Raises:
NotImplementedError – If
normis not'l1'or'linf'.RuntimeError – If a call’s solve does not reach
status="ok".
- Parameters:
n (Network)
dimensions (dict)
norm (str)
slack (float)
output_dir (str | Path | None)
resolve_main_objective (bool)
snapshots (Sequence | None)
multi_investment_periods (bool)
model_kwargs (dict | None)
max_parallel (int)
on_solve (Callable[[np.ndarray, np.ndarray, float, np.ndarray | None, np.ndarray], None] | None)
kwargs (Any)
- Return type:
- mga_surveyor.pypsa_ext.make_oracle_fns(n, dimensions, slack, norm, output_dir, resolve_main_objective=True, snapshots=None, multi_investment_periods=False, model_kwargs=None, max_parallel=4, **kwargs)[source]¶
Build all three oracle callables
explore.driveneeds in one call against a real, already-solved PyPSA networkn, sharingn/dimensions/output_dir– just callsmake_furthest_point_fn,make_closest_point_fn, andmake_optimality_fnwith their common arguments and returns the three results.Each gets its own independent
picklecopy ofn, notnitself:create_model()stores its model atn.model, a single slot, so three factories built directly against one sharednwould silently overwrite each other’s model there, leaving at most one of the three actually usable.Returns
(furthest_point, closest_point, solve_optimal), in that order –explore.drive’s own parameter order.- Parameters:
- Return type:
tuple[Callable, ClosestPointFn, Callable[[], np.ndarray]]
- mga_surveyor.pypsa_ext.generate_mga_files(n, dimensions, output_dir, norm, slack_levels, solver_name, max_iter, tol, max_parallel, sep_tol=None, verbose=True, normalize=True, use_objective_cuts=True, vertex_method='bb', **kwargs)[source]¶
Run a
BBMethodorCddMethod(float arithmetic) (seevertex_method) per slack level (explore.drive, up tomax_iteriterations each) against a real, already-solved PyPSA networkn, writing every result to.ncfiles underoutput_dir. Doesn’t collect them into a near-optimal set – callexport.collect_near_optimal_set(orexport_near_optimal_set) afterward for that.max_parallel: no default – must be chosen explicitly for every run, same asmax_iter/tol. Dual-purpose: spreadsfurthest_point/closest_point’s own solves across this many worker processes (seemake_furthest_point_fn/make_closest_point_fn), AND is passed straight through to each slack level’s ownexplore.drivecall as its ownmax_parallel– when greater than1, every iteration there solves up to that many of the worst candidate closest-points at once instead of just the single worst one, spread across the very same worker pool (CddMethodonly:BBMethodhas nofind_pool_trial_points, sodrivesolves one target per iteration with it) – seeexplore.drive’s own docstring for the full picture, including why no extra reconciliation is needed across a round’s own results.tol/max_iterare each either a single value (used for every slack level) or a sequence with one entry perslack_levels(raises if the length doesn’t match).normalize(defaultTrue): ifTrue, each slack level’s Method explores a[-1, 1]^k-normalized cube instead of raw dimension units, viamga_surveyor.normalize.normalize_oracle_fns– see that module for why (mixing e.g. MW and MWh dimensions in one unweighted polytope means the ones with the larger natural range dominate; on by default since that’s true of most real networks, not a narrow edge case). Computed fresh per slack level (each one’s own achievable box can differ), from that level’s ownfurthest_point’s box-point solves – raises if any dimension turns out fixed (no achievable range) under that slack budget, seenormalize.compute_affine_map. Everything on disk (.ncfiles, the near-optimal set collected from them) is completely unaffected – still real units throughout, since the oracle functions themselves are unchanged; only whatexplore.drive/the Method sees is normalized. PassFalseto explore raw units instead.`tol` is interpreted differently depending on `normalize`, on purpose – there is no unit that’s natural in both modes at once: -
normalize=False:tolis a plain real-unit distance, exactly asit always was.
normalize=True:tolis instead a percentage (tol=1means1%), converted internally (tol_cube = tol / 100 * 2, since each dimension’s real range maps onto a normalized width of2) before being used as the actual[-1, 1]^k-cube stopping distance. What that percentage bounds depends onnorm– each is the same norm, just applied to the vector of per-dimension percentage errors instead of raw values:norm="linf"bounds every dimension’s own error individually (each is at mosttol`%, not just their average); `norm="l1"bounds their sum (tol`% split across dimensions however the worst case demands); `norm="l2"bounds their root-sum-square. All three are exact, provable bounds, not heuristics – just different ways of combining per-dimension percentages into one stopping number.
Same per-slack-level broadcasting as
max_iter.sep_tol(defaultNone->tol * common.SEP_TOL_FACTOR): the separation threshold, separate from the convergencetoland in the same units (a percentage undernormalize=True), same per-slack-level broadcasting. A closest-point solve whose point is more thansep_tolfrom its target is separating, and its geometric and objective cuts are added (live and on a restart’s read-back); at or below it, only the point is kept (common.separates).use_objective_cuts(defaultTrue; measured ~5x fewer iterations to converge attol=2%onmodel_energy, and the degenerate-dual/ scale-inconsistency bugs that once made this risky are now fixed – passFalseto fall back to plain geometric cuts only): also add amga_surveyor.common.linearized_objective_cutfor every point the main loop finds (resolve_main_objective=True, the default) – both live (method.add_cut, same as its geometric cut) and for any existingmga_closest_result_*.ncfile read back on a restart (passed asextra_halfspaceswith everything else read back there, replayed after bootstrap – see “Resumable” below). Reusesduals/objthat are already computed for caching and otherwise never used again. These are provably valid cuts (see that function’s docstring: convexity of the achievable-cost-at-x value function makes each one a global underestimator, not a heuristic), so this is free extra tightening, no new solves. Composes withnormalize=True: every cut is derived in real units first, then transformed the same way any other halfspace is.Also adds one free extra cut per slack level from
n’s own optimum (optimal.nc’s own cachedduals/obj) – unconditionally, since it has no same-run geometric normal to check it against (the optimum isn’t a support-function/closest-point query) and, unlike a box-direction point (see below), there’s no structural reason for its achievable-cost gradient to align with any single axis.Deliberately NOT derived from any box-direction point, even though those are also solved with
resolve_main_objective=Trueand havedualssitting right there unused – a box-direction point’s own objective cut is always exactly parallel to its own box halfspace: its pinned re-solve (make_furthest_point_fn) pins only the queried dimensioni, so its duals are zero in every other dimension and the cut’s direction is proportional toe_i– and nearly-coincident hyperplanes are a real degeneracy risk regardless of which method processes them. Confirmed in practice against the incremental edge-walking construction this project used beforeCddMethodbecame the production method: unfiltered, this reliably exploded into hundreds of thousands of spurious crossing vertices and an out-of-memory crash – kept excluded here as a precaution, not re-validated againstCddMethod’s own construction. Closest-point and optimum cuts don’t share that structural alignment (confirmed empirically: their angles to any same-run geometric normal are scattered across the whole range, not clustered near 0/180 the way box cuts are), so unlike box cuts, they’re never filtered for near-parallelism – an earlier version of this function did check each closest-point cut against its own same-solve geometric normal (cosine similarity, threshold 0.95) before adding it, but that check turned out to be net-negative: on the real test network it discarded cuts that still carried real tightening value, costing extra main-loop iterations (7 iterations with the check vs. 4 without, same network/slack/tolerance) for no compensating safety benefit – cddlib’s own Double Description construction already discards any genuinely duplicate/redundant cut for free, regardless.One more thing every candidate cut from the main loop (or a restart’s existing files) is checked against before being added, skip-only (never turns a bad cut into a good one, just avoids adding one that isn’t useful) – the optimum’s own cut above is exempt, since it’s added unconditionally: - Already feasible: if the point this cut came from was itself
already feasible (nothing was separated – same test
explore.driveitself uses for its own geometric cut, itscut_addedcheck), the objective cut is skipped too, not just the geometric one.n’s own optimum is slack-independent, so it’s solved/cached once (output_dir/optimal.nc), not once per slack level, even though each slack level’s owndrive()call still calls it (as its requiredoptimal_fn) to seed that slack level’s inner approximation.Resumable:
optimal_fn’s andfurthest_point’s.ncfiles (underoutput_dir/optimal.ncandoutput_dir/slack_{slack}/) are read back on a restart instead of re-solved (seemake_optimality_fn/make_furthest_point_fn).closest_pointitself has no such cache – it always solves fresh (seemake_closest_point_fn) – but everymga_closest_result_*.ncalready under a slack level’s own directory (from an earlier, interrupted run) is read back and passed as that slack level’s owndrive()call’sextra_points/extra_halfspaces– replayed one at a time after bootstrap (drive’sincremental_bootstrap=True), so those points/cuts don’t need to be rediscovered. Assumes those earlier results are genuine near-optimal points forn/dimensions/this slack level – a wildly incompatible stray file (e.g. from a different network or corrupted by hand) could otherwise seed the Method with points/halfspaces that don’t describe a coherent region.vertex_method(default"bb"):"bb"runsBBMethod(Qhull’s polar dual),"cdd"runsCddMethodwith its float backend."bb"is the default because on PyPSA-Eur it matched exact (rational) vertex enumeration at every iteration at about the same speed, whereas cdd’s float backend dropped vertices as cuts accumulated and underestimated the gap in later iterations, which can stop a run before it has converged (see the G-ORACLE paper, arXiv:2610.32759)."cdd"remains the only choice that batches trial points (find_pool_trial_points) whenmax_parallel > 1; with"bb",drivesolves one target per iteration.solver_namealso becomes each slack level’s Method’sprojection_backend(the inner-hull projection solver), so it must be'gurobi'or'highs'.**kwargs(e.g.solver_options) is forwarded to every oracle factory.- Raises:
ValueError – If
normis not'l1'/'linf'(the closest-point solver supports only those),vertex_methodis not'cdd'/'bb', or anysep_tolis not in[0, tol); iftol,max_iterorsep_tolis a sequence whose length doesn’t matchslack_levels; or ifnormalize=Trueand any dimension has no achievable range under some slack level’s own budget (seenormalize.compute_affine_map).- Parameters:
- Return type:
None
- mga_surveyor.pypsa_ext.encode_cache_key(vec)[source]¶
Filename-safe cache key for a numeric vector: SHA-256 of its raw float64 bytes, truncated to 10 hex characters (40 bits – collision risk is negligible at the scale of a project’s cached files). Not reversible – unlike a rounding-based encoding, this hashes the exact bytes, so it’s only meant for vectors that are exactly reproducible bit-for-bit across calls (e.g.
np.eye-derived directions), not ones that might differ by float noise.-0.0is normalized to0.0first, since IEEE 754 gives it a different bit pattern despite being numerically equal to0.0(e.g.-np.eye(k)’s off-diagonal entries).
Export¶
Export a generate_mga_files run as a near-optimal set (mga_format).
export_near_optimal_set reads the result files generate_mga_files wrote to
its output_dir and writes them in the format MGA Compass reads: one point per
result file (the optimum, the box points and the nearest points of every slack
level), with its cost and duals and the cache key in its file name (key), plus the PoI definitions, the optimal cost,
each slack level’s run summary and the network’s fingerprint.
- mga_surveyor.export.network_fingerprint(n)[source]¶
The sha256 of
n’s input data: its snapshots and their weightings, and every component’s static attributes and time series that PyPSA marks as input. Optimization results are left out, so solvingnagain does not change the fingerprint, while changing any cost, limit or time series does.
- mga_surveyor.export.export_near_optimal_set(output_dir, directory, *, units, cost_unit, cost_name='cost', descriptions=None)[source]¶
Write the results of a
generate_mga_filesrun inoutput_diras a near-optimal set in the new directorydirectory, and return its manifest. The set has no outputs; to add some, usecollect_near_optimal_set()and write the set withmga_format.writeyourself.unitsgives every PoI’s unit,cost_unitthe cost’s;descriptionscan describe the PoIs. The cost column is namedcost_name.- Raises:
FileNotFoundError – If
output_dirhas nooptimal.nc, or a slack level has no run summary (its run did not finish; resuminggenerate_mga_fileswrites it).ValueError – If a PoI has no unit, or a result has no duals (it was solved with
resolve_main_objective=False).
- Parameters:
- Return type:
- mga_surveyor.export.collect_near_optimal_set(output_dir, *, units, cost_unit, cost_name='cost', descriptions=None)[source]¶
The results of a
generate_mga_filesrun inoutput_diras a near-optimal set in memory, and the result file of each point, in point order (files[p]is the solved network behind pointp), for reading detailed outputs. Arguments and errors as forexport_near_optimal_set().
Methods¶
The Method interface shared by all three worst-point
implementations (bilevel MILP, cdd, beneath-and-beyond), so a driving loop (see
mga_surveyor.explore) can be written once against this interface and
parameterized by which method to use.
Every method owns exactly the state needed to maintain an inner
approximation I (a set of points, implicitly their convex hull) and an
outer approximation O (a growing list of supporting halfspaces) of some
region – and nothing else. In particular, no method ever calls back into
whatever produced a point or a cut: Method.add_point() /
Method.add_cut() are pure state updates, so the whole package is
independent of any specific test example or system model. Finding new
points/cuts to feed in is the caller’s job (see the generic loop in
mga_surveyor.explore, or drive a method directly with your own).
- class mga_surveyor.methods.base.Method(k, norm)[source]¶
Bases:
ABCCommon interface for a worst-point / convergence-metric implementation.
- Parameters:
- abstractmethod bootstrap(initial_points, initial_halfspaces)[source]¶
Seed the inner and outer approximations.
Must be called exactly once, before any
add_point(),add_cut(), orfind_trial_point()call.- Parameters:
initial_points (list[ndarray]) – Feasible points (e.g. the cost-optimal design) to seed the inner approximation with.
initial_halfspaces (list[tuple[ndarray, ndarray]]) –
(direction, point)pairs, each defining a supporting hyperplane known to hold for the true region (e.g. from element-wise upper/lower bounds), to seed the outer approximation with.
- Return type:
None
- abstractmethod add_point(point)[source]¶
Grow the inner approximation with a newly found feasible point.
- abstractmethod add_cut(direction, point)[source]¶
Shrink the outer approximation by adding a new supporting halfspace
{x : direction @ (x - point) <= 0}.
- abstractmethod find_trial_point()[source]¶
Find the point in the outer approximation furthest (in
self.norm) from the inner approximation.- Returns:
(trial_point, gap), wheregapis the max-min distance itself (the convergence metric).(None, 0.0)if the outer approximation has no vertices (only possible beforebootstrap()).- Return type:
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'usescdd.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 (seedisdyakis_triacontahedron.py’s module docstring for a real instance of that failure). Every halfspace coefficient is converted tofractions.Fractionbefore being handed tocdd.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.CddMethod.add_cut()folds a new halfspace in incrementally – resuming cddlib’s own Double Description computation instead of recomputing the whole polytope – viapolyhedron_append_halfspaces(present on both thecddandcdd.gmpmodules), when the installedcdd/cdd.gmphas it. That function is a local patch on top of pycddlib/cddlib (vendored, with the patch, undervendor/cdd– seevendor/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. Whenpolyhedron_append_halfspaceseither isn’t present (a stockpycddlibinstall) or raises (its own restrictions on the append aren’t met for this polytope – see its docstring),_vertices_with_ids()transparently falls back to a full rebuild fromself.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 whichcddbuild 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_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. Whencopy_generators_with_idsisn’t available, every vertex is solved every refresh, exactly as before this caching existed.
- mga_surveyor.methods.cdd.CddBackend¶
Which cdd arithmetic backend to use –
'float'(cdd’s native C double arithmetic) or'gmp'(cdd.gmp’s exact rational arithmetic).alias of
Literal[‘float’, ‘gmp’]
- class mga_surveyor.methods.cdd.ProjectionFn(*args, **kwargs)[source]¶
Bases:
ProtocolContract for
projection_fn: projectpointontoconv(points)undernorm, returning(closest_point, normal)– exactly whatgurobi_projection.closest_point_on_hull/highs_projection. closest_point_on_hullimplement (see either’s docstring).
- mga_surveyor.methods.cdd.check_cdd_backend(backend)[source]¶
Validate an untrusted
backendvalue at a package boundary – thecdd-specific counterpart ofcheck_norm().- Parameters:
backend (str)
- Return type:
None
- mga_surveyor.methods.cdd.cdd_vertices_of(outer_halfspaces, backend='float')[source]¶
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
CddMethodinstance’s own incremental state – e.g. as a from-scratch ground-truth cross-check against a live instance’s incrementally-maintained vertex set (seetests/test_cdd_incremental.py), where reusing incremental state would defeat the point.- Parameters:
- Returns:
The polytope’s vertices, as an
(m, k)array.- Return type:
- class mga_surveyor.methods.cdd.CddMethod(k, norm, executor=None, backend='float', projection_fn=None, projection_backend='gurobi')[source]¶
Bases:
MethodSee module docstring.
- Parameters:
k (int) – Dimension of the exploratory variables.
norm (str) – Distance metric, one of
'l1','l2', or'linf'.executor (concurrent.futures.Executor, optional) – Used to run the independent per-vertex
closest_point_on_hullsolves concurrently after each refresh. A freshThreadPoolExecutoris created if none is given.backend (str) –
'float'(default) or'gmp'– see module docstring. Unrelated toprojection_backend/projection_fnbelow: this picks cdd’s own outer-polytope arithmetic, not the inner-hull projection’s solver.projection_fn (ProjectionFn | None) – Lower-level override of the inner-hull projection callable itself, signature
(point, points, norm) -> (closest_point, normal)– takes precedence overprojection_backendif given. Every call site goes throughself.projection_fn, so any callable matching that contract works, not just the two built-in backends.projection_backend (str) – 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 ownbackendparameter – named differently here sincebackendon this class already means cdd’s arithmetic.
- Raises:
ValueError – If
projection_backendis not'gurobi'or'highs'.
- reset_stats()[source]¶
Zero the instrumentation counters in
stats– purely additive bookkeeping, no effect on any other method’s behavior or return value._refresh()/_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. oneadd_point+ itsadd_cut`(s) + one `max_gap()), then readstatsafter that iteration’s calls are done.cdd_time/projection_time: seconds spent inside cdd’s own append/rebuild call, and insideself.projection_fnsolves, respectively (the latter summed across both_refresh_stale_closest_points()and_refresh()’s own solve step).n_total: the outer vertex count as of the last_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.Noneinstead of an int whenever id tracking itself isn’t available at all for this cdd install (see module docstring) – distinct from0, 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_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).
- Return type:
None
- bootstrap(initial_points, initial_halfspaces)[source]¶
Seed the inner and outer approximations.
Must be called exactly once, before any
add_point(),add_cut(), orfind_trial_point()call.- Parameters:
initial_points (list[ndarray]) – Feasible points (e.g. the cost-optimal design) to seed the inner approximation with.
initial_halfspaces (list[tuple[ndarray, ndarray]]) –
(direction, point)pairs, each defining a supporting hyperplane known to hold for the true region (e.g. from element-wise upper/lower bounds), to seed the outer approximation with.
- Return type:
None
- add_cut(direction, point)[source]¶
Shrink the outer approximation by adding a new supporting halfspace
{x : direction @ (x - point) <= 0}.
- find_trial_point()[source]¶
Find the point in the outer approximation furthest (in
self.norm) from the inner approximation.- Returns:
(trial_point, gap), wheregapis the max-min distance itself (the convergence metric).(None, 0.0)if the outer approximation has no vertices (only possible beforebootstrap()).- Return type:
- find_trial_points_above_tol(tol)[source]¶
Like
find_trial_point(), but returns every outer vertex whose gap is at leasttol(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 (seemga_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).toluses the same cutoffexplore.drive’s own main loop applies before ever dispatching a solve for the single worst point:gap < tolmeans converged there, sogap >= tol(not the strictergap > tol) is the matching “still worth solving” condition here – a candidate right attolexactly is still oneexplore.driveitself would have dispatched a solve for.Not part of the
Methodinterface:explore.drivereaches it throughfind_pool_trial_points(), found viahasattr.BilevelMethodhas 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), andBBMethod– which does keep a vertex set – doesn’t implement it (yet), so this lives onCddMethodalone rather than on the shared base class.- Parameters:
tol (float) – The same convergence tolerance
explore.driveitself is called with. No default – seeexplore.drive’s own docstring on why it takes no default either.- Returns:
(points, gaps), sorted by gap descending – index 0 is the same point/gapfind_trial_pointitself would return. Both empty if the outer polytope has no vertices yet, or none are at leasttol.- Return type:
- find_pool_trial_points(max_parallel, tol)[source]¶
Batched stand-in for
find_trial_point(): up tomax_parallelabove-tolcandidate trial points to solve in parallel instead of just the single worst one – themax_parallelworst ones, sincefind_trial_points_above_tol()already returns them sorted by gap descending.explore.drivecalls this (found viahasattr) whenever itsmax_parallel > 1, solving the returned points in one batchedclosest_pointcall; withmax_parallel == 1, or for a method without it,driveusesfind_trial_point()instead.- Parameters:
- Returns:
(points, gaps), capped atmax_parallel, both empty iffind_trial_points_above_tolitself returns nothing.- Return type:
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 toCddMethod’s cddlib Double Description method. Seemga_surveyor.methods.basefor the generalMethodcontract this mirrors; this class implements the samebootstrap/add_point/add_cut/find_trial_point/max_gapinterface, 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
_add_halfspace()). Every subsequent dual point – i.e. everyadd_cut()for the rest of this object’s life, which in production usage is the overwhelming majority of calls – goes throughConvexHull.add_pointson 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
x0strictly 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 atx0, maps to the dual pointdirection / bwhereb = direction@(point-x0), which is only well-defined (and the resulting dual facet/primal vertex correspondence only valid) whenb > 0, i.e.x0strictly satisfies the halfspace. By default,BBMethod.bootstrap()uses the centroid (mean) ofinitial_pointsasx0and keeps it fixed for the method’s lifetime; passoriginto__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: theMethodinterface doesn’t designate any one ofinitial_pointsas “the” interior reference point, and no fixed choice is guaranteed interior for every possible caller. If a lateradd_cut()(or the initial halfspaces themselves) violatesx0’s interiority,_dual_point()raisesValueErrorimmediately rather than silently returning a wrong vertex set – in practice this hasn’t triggered for the box-plus-optimal-point bootstrap patternmga_surveyor.exploreactually uses, since the centroid of a box’s extreme points plus one interior (near-optimal) point lands well inside the box.As with
_halfspace_row(), each halfspace’sdirectionis 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 incrementaladd_pointsdoesn’t expose any persistent per-vertex identity across an update (cddlib’s patchedcopy_generators_with_idshas 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:_vertex_hash()rounds a vertex’s coordinates to_VERTEX_HASH_DECIMALSplaces and uses the resulting tuple as a stand-in identity, on the empirical grounds (seeqhull_survival_check.pyin 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 oneadd_cutto the next – only the vertices a cut actually creates or destroys change at all._refresh()uses this hash exactly the wayCddMethod._refreshuses 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, solvingclosest_point_on_hullonly 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 –_VERTEX_HASH_DECIMALS(a1e-8grid) is chosen coarser than the~1e-9roundoff 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.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_refresh_stale_closest_points()can just re-use the existing arrays directly, no identity of any kind needed.
- class mga_surveyor.methods.bb.ProjectionFn(*args, **kwargs)[source]¶
Bases:
ProtocolContract for
projection_fn– seemga_surveyor.methods.cdd.ProjectionFn.
- class mga_surveyor.methods.bb.BBMethod(k, norm, executor=None, projection_fn=None, projection_backend='gurobi', origin=None)[source]¶
Bases:
MethodSee module docstring.
- Parameters:
k (int) – Dimension of the exploratory variables.
norm (str) – Distance metric, one of
'l1','l2', or'linf'.executor (concurrent.futures.Executor, optional) – Used to run the independent per-vertex
closest_point_on_hullsolves concurrently after each refresh. A freshThreadPoolExecutoris created if none is given.projection_fn (ProjectionFn | None) – Lower-level override of the inner-hull projection callable itself – takes precedence over
projection_backendif given. SeeCddMethod’s own docstring for the exact contract.projection_backend (str) – Which persistent solver to use for the inner-hull projection –
'gurobi'(default) or'highs'.origin (ndarray | None) – Fixed interior reference point for the polar-dual construction (see module docstring) – overrides the default centroid-of-
initial_pointsheuristicbootstrap()would otherwise use. Pick this explicitly whenever a specific point is known to be strictly interior to every halfspace for the whole run. Neithermga_surveyor.explorenorpypsa_extpasses 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, givingb = 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’sb = direction@ (point-origin)can shrink towards zero even while staying positive, degrading that halfspace’s dual pointdirection/b(and hence the vertices it participates in) numerically – a plausible explanation if this class’s vertex set/gap ever starts drifting fromCddMethod’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 ininitial_points) avoids that. No default –Nonekeeps the centroid heuristic.
- Raises:
ValueError – If
projection_backendis not'gurobi'or'highs'.
- bootstrap(initial_points, initial_halfspaces)[source]¶
Seed the inner and outer approximations.
Must be called exactly once, before any
add_point(),add_cut(), orfind_trial_point()call.- Parameters:
initial_points (list[ndarray]) – Feasible points (e.g. the cost-optimal design) to seed the inner approximation with.
initial_halfspaces (list[tuple[ndarray, ndarray]]) –
(direction, point)pairs, each defining a supporting hyperplane known to hold for the true region (e.g. from element-wise upper/lower bounds), to seed the outer approximation with.
- Return type:
None
- add_cut(direction, point)[source]¶
Shrink the outer approximation by adding a new supporting halfspace
{x : direction @ (x - point) <= 0}.
- find_trial_point()[source]¶
Find the point in the outer approximation furthest (in
self.norm) from the inner approximation.- Returns:
(trial_point, gap), wheregapis the max-min distance itself (the convergence metric).(None, 0.0)if the outer approximation has no vertices (only possible beforebootstrap()).- Return type:
BilevelMethod – “bilevel solution”.
Implements the method of Turan, Moret & Bardow, “ORACLE: A rigorous metric and method to explore all near-optimal designs for energy systems”, Computers & Chemical Engineering (2026).
Only
norm='linf'is supported; L1/L2 aren’t implemented (useCddMethodinstead).Requires
gurobipyand a Gurobi license; no open-source backend.Reformulates the max-min bilevel LP into a single-level MILP via KKT + Big-M (Fortuny-Amat/McCarl) linearization of the complementarity conditions.
- mga_surveyor.methods.bilevel.compute_safe_big_m(A_O, b_O, inner_points, margin=1.0)[source]¶
Derive provably-valid
(M_P, M_D)directly from this problem’s own data, instead of guessing fixed constants – seesolve_farthest_outer_point_milp()’s own docstring for what each bounds. Both constants follow from the KKT system’s own structure:M_Pboundsw[i]and the two slacksslack_plus[j] = t - zO[j] + (Iw)[j],slack_minus[j] = t + zO[j] - (Iw)[j].w[i] <= 1always (convex weights). For the slacks: letlo[j]/hi[j]be the min/ max ofzO[j]overO(found here via2*nztiny LPs onA_O/b_O), andL[j]/U[j]the min/max ofinner_points[:, j](a plain array reduction – any convex combination’sj-th coordinate is provably within[L[j], U[j]]). Thent* = max_zO min_w ||zO - Iw||_inf <= T_MAX := max_j max(hi[j]-L[j], U[j]-lo[j])(how farOcan possibly get fromconv(inner_points)on any single axis), and each slack is at mostt* + T_MAX <= 2*T_MAX.M_Dboundsa_plus[j],a_minus[j],b_dual[i]. The stationarity constraintsum(a_plus[j]+a_minus[j]) == 1(all terms >= 0) already forcesa_plus[j] <= 1anda_minus[j] <= 1on its own. At the complementary-slackness-activei(somew[i] > 0always exists, andb_dual[i] = 0there), the stationarity-in-wequation pinsetatosum_j inner_points[i,j]*(a_plus[j]-a_minus[j]), bounded byR_IN := max_{i,j} |inner_points[i,j]|since theaterms sum to 1 in absolute value. Propagating back through that same equation for everyigivesb_dual[i] <= 2*R_IN.
Both are LOWER bounds on what’s actually needed (exact at the true optimum) –
margin(default1.0, i.e. no slack) inflates them for extra numerical headroom at the cost of a proportionally weaker relaxation; pass e.g.1.05if solves ever come back infeasible due to floating-point roundoff at the boundary.- Parameters:
- Returns:
(M_P, M_D), ready to pass straight intosolve_farthest_outer_point_milp()/BilevelMethod.- Return type:
- Raises:
ImportError – If
gurobipyis not installed.
- mga_surveyor.methods.bilevel.solve_farthest_outer_point_milp(A_O, b_O, inner_points, time_limit, M_P=None, M_D=None, verbose=False, diagnostics=None, mip_gap=1e-07, mip_gap_abs=None)[source]¶
Solve
max_{zO in O} min_{zI in conv(inner_points)} ||zO - zI||_infvia the KKT-based single-level MILP reformulation.Ois given asA_O @ z <= b_O.- Parameters:
A_O (ndarray) – Outer polytope constraint matrix, with
Ogiven byA_O @ z <= b_O.b_O (ndarray) – Outer polytope right-hand side, with
Ogiven byA_O @ z <= b_O.inner_points (ndarray) – Points whose convex hull is the inner approximation.
time_limit (float | None) – Seconds, forwarded to Gurobi’s own
TimeLimitparam – no default, an explicit choice is required every call (Nonefor unbounded/exact-only, matching the original behavior before this parameter existed).NonerequiresGRB.OPTIMAL, raising on anything else. When set, a solve that hits the time limit with at least one feasible incumbent (GRB.TIME_LIMIT,model.SolCount > 0) is ALSO accepted – the returnedt_staris then a valid lower bound on the true max-min distance, not necessarily the exact value (the Big-M reformulation’s usual exactness caveat, now compounded by not having actually proven optimality either). Passdiagnosticsto tell which case happened. A time-limited solve with NO incumbent at all still raises, same as any other failure status.M_P (float | None) – Big-M constant bounding the primal solution (Fortuny-Amat/McCarl linearization of the complementarity conditions); must be a valid (large enough) bound for the specific problem, or the reformulation is not exact – there is no automatic way to check this from inside the MILP itself.
None(default) computes a provably-valid bound viacompute_safe_big_m()on this exact call’s ownA_O/b_O/inner_pointsinstead of guessing a fixed constant.M_D (float | None) – Big-M constant bounding the dual solution; same caveat – and same
Nonedefault – asM_P.verbose (bool) – If True, let Gurobi print its own solve log.
diagnostics (dict | None) – If given, populated in place with
solve_time,status(Gurobi’s own status code),is_optimal(Trueonly forGRB.OPTIMAL),mip_gap(model.MIPGap– meaningless/inf-ish if no incumbent, which can’t happen here since that case raises instead), andnode_count. Doesn’t change the return value; purely for a caller that wants to log solve quality without re-deriving it.mip_gap (float) – Forwarded to Gurobi’s own
MIPGap(relative optimality gap) convergence parameter.mip_gap_abs (float | None) – Forwarded to Gurobi’s own
MIPGapAbs(absolute optimality gap) convergence parameter.None(default) leaves Gurobi’s own default in place – unlikemip_gap, this isn’t set unconditionally, since0is itself a meaningful value (require an EXACT proof, not just within some absolute tolerance) that shouldn’t be silently equivalent to “unset”.
- Returns:
(z_O_star, t_star, w_star)– the worst point, the max-min L_inf distance (exact iffdiagnostics["is_optimal"], when given), and the convex-combination weights of its closest inner point (z_I_star = w_star @ inner_points).- Return type:
- Raises:
ImportError – If
gurobipyis not installed.RuntimeError – If the solve ends in any status other than
GRB.OPTIMAL, or (only whentime_limitis set)GRB.TIME_LIMITwith at least one feasible incumbent.
- class mga_surveyor.methods.bilevel.BilevelMethod(k, norm, time_limit, M_P=None, M_D=None, verbose=False, mip_gap=1e-07, mip_gap_abs=None)[source]¶
Bases:
MethodSee module docstring.
- Parameters:
k (int) – Dimension of the exploratory variables.
norm (str) – Must be
'linf'– see module docstring for why.time_limit (float | None) – Forwarded to
solve_farthest_outer_point_milp()on every call – see its own docstring. No default – an explicit choice is required (Nonefor unbounded/exact-only, matching the original behavior before this parameter existed); set a real limit to accept a possibly-non-exact (but time-bounded) gap instead of risking an unboundedly long single solve – seestats’is_optimalfor whether a given call’s result was actually exact.M_P (float | None) – Big-M primal bound, forwarded to
solve_farthest_outer_point_milp()on every call –None(default) computes a fresh, provably-valid bound viacompute_safe_big_m()on every solve instead of a fixed constant (cheap relative to the MILP solve itself – see that function’s own docstring).M_D (float | None) – Big-M dual bound, forwarded to
solve_farthest_outer_point_milp()on every call – sameNonedefault asM_P.verbose (bool) – If True, let Gurobi print its own solve log.
mip_gap (float) – Forwarded to
solve_farthest_outer_point_milp()on every call – see its own docstring.mip_gap_abs (float | None) – Forwarded to
solve_farthest_outer_point_milp()on every call – see its own docstring.
- Raises:
NotImplementedError – If
normis not'linf'.
- reset_stats()[source]¶
Zero
stats– mirrorsCddMethod.reset_stats()’s role for a caller that wants to scope solve diagnostics to one logical iteration, though here there’s at most one solve perfind_trial_point()/max_gap()call to begin with (no cross-call accumulation needed), so this just resets to defaults. Populated fromsolve_farthest_outer_point_milp()’s owndiagnosticsout-param after any call that actually solved (an unchanged/no-opfind_trial_pointcall, or one with no halfspaces yet, leaves the previous values in place instead of clearing them).- Return type:
None
- bootstrap(initial_points, initial_halfspaces)[source]¶
Seed the inner and outer approximations.
Must be called exactly once, before any
add_point(),add_cut(), orfind_trial_point()call.- Parameters:
initial_points (list[ndarray]) – Feasible points (e.g. the cost-optimal design) to seed the inner approximation with.
initial_halfspaces (list[tuple[ndarray, ndarray]]) –
(direction, point)pairs, each defining a supporting hyperplane known to hold for the true region (e.g. from element-wise upper/lower bounds), to seed the outer approximation with.
- Return type:
None
- add_cut(direction, point)[source]¶
Shrink the outer approximation by adding a new supporting halfspace
{x : direction @ (x - point) <= 0}.
- find_trial_point()[source]¶
Cached: recomputes only if
self._dirtyis set (bybootstrap(),add_point(), oradd_cut()since the last call); a repeat call in between – notably frommax_gap()– skips the MILP solve and reuses the cached result.
Normalization¶
Generic affine-map normalization: keeps a Method’s inner/outer
polytope confined to the unit cube [-1, 1]^k, regardless of how
differently-scaled the underlying dimensions are (e.g. MW vs MWh), by
wrapping explore.drive’s three oracle callbacks
(FurthestPointFn/ClosestPointFn/OptimalPointFn) with a per-dimension
affine map computed from the box points – explore.drive/Method need
no changes at all; they just see oracle functions that happen to speak
normalized coordinates instead of real ones.
Finding the actual closest point under this normalized geometry isn’t
just a coordinate relabeling, though: a plain L1/Linf objective over raw
real-unit residuals doesn’t correspond to the cube-normalized notion of
distance unless each dimension’s residual is weighted by the same
per-dimension scale this module computes (AffineMap.weights) –
normalize_oracle_fns only computes that scale, the actual weighting has
to happen inside whatever solves the closest-point problem itself (see
mga_surveyor.pypsa_ext.make_closest_point_fn’s own weights parameter).
Without it, the point found would be closest under real-unit distance,
not the cube-normalized distance Method is actually exploring under.
None of this is PyPSA-specific – same independence as explore.py
itself, so it’s usable against mga_surveyor.tests.lp_region or any
other oracle implementation too.
- class mga_surveyor.normalize.AffineMap(center, half_range)[source]¶
Bases:
objectPer-dimension affine map real <-> normalized:
normalized = weights * (real - center), whereweights = 1 / half_range– calibrated so[center - half_range, center + half_range]maps exactly onto[-1, 1]per dimension.- property weights: ndarray¶
1 / half_range– what a point’s own coordinates get scaled by (to_normalized/to_real), and what a closest-point solve’s objective needs to weight each dimension’s residual by for “closest” to mean the same thing in real units as it does in this normalized cube (see module docstring).
- normal_to_normalized(normal)[source]¶
A halfspace normal transforms by the inverse of what a point does (
half_range, notweights) – it’s a dual vector (a gradient), not a point, so it transforms by the map’s inverse-transpose, which for this diagonal map is just its inverse again. Substitutingx = to_real(x')into a real-space halfspace{x : normal . (x - p) <= 0}gives exactly{x' : normal_to_normalized(normal) . (x' - to_normalized(p)) <= 0}– the same halfspace, re-expressed in normalized coordinates.
- mga_surveyor.normalize.compute_affine_map(box_points, keys=None, atol=1e-09)[source]¶
From the
2kbox-direction pointsexplore.drive’s bootstrap already computes (rows0..k-1= the+e_imaximizers, rowsk..2k-1= the-e_iminimizers –explore.drive’s ownbox_directionsordering), read off each dimension’s true achievable[min, max]directly: rowi’s owni-th coordinate IS that dimension’s max (maximizinge_i . xmaximizesx_ialone, nothing else), rowk+i’s IS its min. Calibrated exactly, not approximately – each dimension’s achievable range maps onto exactly[-1, 1].keys(defaultNone): dimension names, used only to name the offending dimension(s) in the error below – purely cosmetic, optional so this stays usable without them.- Raises:
ValueError – If any dimension’s achievable range is (numerically) zero – fixed at a single value under the current slack budget. There’s nothing meaningful to rescale by for a fixed dimension (
weights = 1 / half_rangewould be a division by zero), and a dimension with no achievable range at all has no reason to be indimensionsin the first place – likely the underlying network component isn’t actually extendable. Raised (not silently worked around) so this fails loudly instead of quietly producinginf/nandownstream.- Parameters:
- Return type:
- mga_surveyor.normalize.presolve_box_points(furthest_point, k)[source]¶
Solve the
2kbox directions exactly once, right now, and return aFurthestPointFnthat just returns this same already-computed result instead of re-solving – for any caller that needs the box points (or needs whatever side effects that one solve has, e.g. anon_solvecallback baked intofurthest_pointitself, asmga_surveyor.pypsa_ext.make_furthest_point_fnsupports) beforeexplore.drive’s own bootstrap gets to them, withoutexplore.driveending up re-solving (and re-triggering those side effects) a second time for nothing.- Parameters:
furthest_point (FurthestPointFn)
k (int)
- Return type:
- mga_surveyor.normalize.normalize_from_box_points(box_points, box_normals, make_closest_point, optimal_fn, keys=None)[source]¶
The rest of
normalize_oracle_fns, split out for a caller that already hasbox_points/box_normalsin hand (e.g. from its ownpresolve_box_pointscall, made for some other reason too – like filtering candidate halfspaces against the box ones before they ever reachMethod.add_cut) and doesn’t want a second, redundant solve of the same2kdirections.make_closest_point(weights) -> ClosestPointFnis a factory, not a ready-madeClosestPointFn, because the right weights (thisAffineMap’s ownweights) are only known oncebox_pointsare in hand – seemga_surveyor.pypsa_ext.make_closest_point_fn’s ownweightsparameter for what those actually do to its objective.keys(defaultNone): dimension names, passed straight through tocompute_affine_map– purely cosmetic, only used to name the offending dimension if it raises.Returns
(furthest_point_n, closest_point_n, optimal_fn_n, affine_map)– the wrapped trio, plus theAffineMapitself for a caller that needs to convert points already in real units (e.g.extra_points/extra_halfspacesfrom an earlier, interrupted run) into this same normalized space before folding them intoexplore.drive’s bootstrap.- Raises:
ValueError – If any dimension has no achievable range (see
compute_affine_map).- Parameters:
box_points (ndarray)
box_normals (ndarray)
make_closest_point (Callable[[ndarray], ClosestPointFn])
optimal_fn (OptimalPointFn)
- Return type:
tuple[FurthestPointFn, ClosestPointFn, OptimalPointFn, AffineMap]
- mga_surveyor.normalize.normalize_oracle_fns(furthest_point, make_closest_point, optimal_fn, k, keys=None)[source]¶
Wrap the three
explore.driveoracle callbacks so they speak normalized[-1, 1]^kcoordinates instead of real units –explore.drive/Methodneed no changes at all, they just see functions matching the same three protocols.Solves the
2kbox directions exactly once, here (presolve_box_points) –explore.drive’s own bootstrap never needs to. A thin convenience wrapper overpresolve_box_points+normalize_from_box_points, for a caller that doesn’t needbox_points/box_normalsfor anything else; seenormalize_from_box_pointsfor one that does.- Raises:
ValueError – If any dimension has no achievable range (see
compute_affine_map).- Parameters:
furthest_point (FurthestPointFn)
make_closest_point (Callable[[ndarray], ClosestPointFn])
optimal_fn (OptimalPointFn)
k (int)
- Return type:
tuple[FurthestPointFn, ClosestPointFn, OptimalPointFn, AffineMap]
Common helpers¶
Norm-generic geometric primitives usable by any worst-point method – not tied to one method’s specific algorithm.
Everything here operates only on point clouds and halfspace lists handed to
it – nothing in this module knows anything about where those points or
cuts came from (a real system model, a synthetic test polytope, or
anything else), and nothing here is tied to a particular solver backend
either. A halfspace/cut is always represented as a (direction, point)
pair meaning {x : direction @ (x - point) <= 0}; this is the one
convention used consistently across the whole package.
The one operation this package needs that genuinely requires a solver –
projecting a point onto conv(points) under a given norm – deliberately
does NOT live here. It lives in gurobi_projection.py and highs_projection.py
instead, one module per backend, both implementing the same
(point, points, norm) -> (c, normal) contract, so this module can stay
backend-agnostic in fact, not just in name.
- mga_surveyor.common.Norm¶
One of the three supported distance metrics.
alias of
Literal[‘l1’, ‘l2’, ‘linf’]
- mga_surveyor.common.Halfspace¶
A
(direction, point)pair meaning{x : direction @ (x - point) <= 0}.
- mga_surveyor.common.check_norm(norm)[source]¶
Validate an untrusted
normvalue at a package boundary.Deliberately typed as plain
str, notNorm– the whole point of this function is to check a value that isn’t yet known to be one of the three valid options; every other function in the package that already expects a valid norm usesNorminstead.- Parameters:
norm (str)
- Return type:
None
- mga_surveyor.common.gaps(outer_vertices, closest_points, norm)[source]¶
Distance from each outer vertex to its closest point on the inner hull, under the SAME norm used for the projection – so the argmax selection and the stopping tolerance measure the thing that was actually optimized.
- mga_surveyor.common.SEP_TOL_FACTOR = 0.001¶
Default
sep_tolas a fraction of the convergencetol(seeseparates), used whenever a caller passessep_tol=None.
- mga_surveyor.common.separates(point, target, sep_tol, norm)[source]¶
Whether a closest-point solve for
targetreturned apointgenuinely away from it (distance undernormabovesep_tol) – i.e.targetwas infeasible and the solve’s halfspaces (geometric and objective cut) should be added. At or belowsep_tolthe target was already (numerically) feasible, i.e. withinsep_tolof the region, and the reported normal can be a degenerate dual split, so nothing is added.sep_tolis deliberately separate from (and far below) the convergencetol: a target withintolof the feasible set but outside it still yields valid, tightening cuts.
- mga_surveyor.common.linearized_objective_cut(x0, obj_value, duals, obj_optimal, slack, atol=1e-09)[source]¶
A supporting halfspace of the true near-optimal region, linearized from a single solved point’s own duals – valid, not a heuristic: the minimum-cost-achievable-at-x value function is convex in x (a standard parametric-LP fact), so its tangent at any solved point x0 is a GLOBAL underestimator,
obj(x) >= obj_value + duals @ (x - x0)for every x, not just near x0. Near-optimality (obj(x) <= (1 + slack) * obj_optimal) therefore forcesduals @ (x - x0) <= KwhereK = (1 + slack) * obj_optimal - obj_value(>= 0, since x0 – the point the duals came from – is itself near-optimal).Returned as this package’s usual
(direction, point)halfspace convention:direction = duals, andpointisx0shifted along a single axis – whichever one hasduals’ own largest-magnitude component,j = argmax(|duals|)– by just enough to makeduals @ (point - x0) == Kexactly:point = x0 + (K / duals[j]) * e_j. Collapses tox0itself whenK == 0(x0 has no slack left), same as any other cut that passes through its own generating point.Deliberately NOT the Euclidean projection (
x0 + (K / (duals @ duals)) * duals) despite that also being a valid choice of point on the same halfspace (add_cut’s own halfspace only depends on the scalardirection @ point, identical for every point actually on the plane – so this is still just a choice among equally-correct options, not a different halfspace).dualsmixes real-world units that can differ by orders of magnitude (e.g. $/MW vs $/MWh), soduals @ dualscan be dominated by whichever dimension happens to have large values there, sending the Euclidean-projection point to a numerically extreme value in every OTHER dimension – which then makesdirection @ point(computed downstream by whichever method processes this halfspace) suffer catastrophic floating-point cancellation, corrupting that cut’s own vertex classification (confirmed in practice, against this project’s incremental edge-walking construction beforeCddMethodbecame the production method: exactly this construction once produced ~187,000 spurious crossing vertices for a 4-dimensional polytope, an OOM crash, not just an inefficiency). Dividing byduals[j]itself (the largest-magnitude component, so the least numerically sensitive denominator available) and moving along a single axis avoids ever amplifying small numerical noise into a huge coordinate swing.Returns
Nonewhendualsis (numerically) the zero vector: thenK >= 0is the whole constraint, true for every x – a vacuous cut, not worth adding.
Convex-hull projection¶
Gurobi (via gurobipy) implementation of the closest-point-on-hull
projection query – (point, points, norm) -> (c, normal) – the one
solver-backed operation common.py deliberately does not contain. Peer
module to highs_projection.py: same contract, different backend. Use this
one for all three norms, including L2 (a quadratic objective, which HiGHS
cannot solve); use highs_projection.closest_point_on_hull for an
open-source, license-free alternative when your norm is ‘l1’ or ‘linf’.
gurobipy is imported at module import time but optionally (gp = None
if it isn’t installed, raising only on first use), and the licensed Gurobi
environment is opened lazily, on the first call to closest_point_on_hull
– so import mga_surveyor (and picking projection_backend='highs'
throughout) never requires gurobipy, nor pays for a Gurobi environment it’s
never going to use.
- mga_surveyor.gurobi_projection.closest_point_on_hull(point, points, norm)[source]¶
Project
pointonto conv(points) undernorm(‘l1’, ‘l2’, or ‘linf’), formulated as a convex combination ofpoints– no ConvexHull/facet enumeration needed, so this scales to the point counts that accumulate over an exploration run.Solved with a persistent, per-(thread, norm) Gurobi model built once and only ever updated: the query point enters only via the RHS of k residual constraints (O(k) per query), and new inner points are folded in with O(k) work each via
gp.Columnrather than a full rebuild. That reuse assumes every call from one thread passes the same growingpointsarray (new rows only appended), as one Method’s own executor does; a different point set in the same thread would silently reuse the old columns.Threads=1since many of these are typically solved concurrently from a thread pool – letting each individual model also spawn worker threads would oversubscribe the machine.- Returns
(c, normal): c: the closest point itself.normal: a valid separating-hyperplane normal atc, i.e. every pointxin the hull satisfiesnormal @ (x - c) <= 0, taken from the (sign-corrected) dual values of the residual constraints. For L2 this is2 * (point - c)– the residual’s direction, scaled by the squared objective’s gradient (L2 is self-dual); for L1/Linf the residual is not generally a valid normal, so the dual is required in general – using the dual uniformly is what makes this function correct for all three norms with one code path.
- Returns
HiGHS (via raw highspy, no AML abstraction layer) reimplementation of
gurobi_projection.closest_point_on_hull – same name, same contract
(point, points, norm) -> (c, normal), just this module’s backend instead of
that one’s; the two are never imported side by side under the same bare
name (pick one backend per solve), so there’s no reason for one of them to
carry a _highs suffix the other doesn’t. Mirrors the raw-gurobipy design
as closely as HiGHS’s native
Python API allows: one persistent Highs() instance per (thread, norm),
extended with a new w column per new inner point via addCol, and the
query point folded into the bounds of two per-dimension rows (one per side
of the abs-value linearization) updated in place via changeRowBounds – no
file export, no AML abstraction layer, matching the persistent-model
pattern that makes the Gurobi version fast (see project notes: an earlier
attempt through Pyomo’s AML layer over the same persistent Gurobi backend
cost ~15-50x versus this, and linopy – which has no persistent-solve path
at all – cost 3,000-7,000x).
L1 and Linf only: HiGHS is an LP/MIP solver, no quadratic objective support (confirmed separately: Pyomo’s appsi_highs interface raises DegreeError on a quadratic objective) – no L2 branch here. Use gurobi_projection.closest_point_on_hull for L2.
Tolerances are tightened to 1e-9 (HiGHS’s default is 1e-7 for both primal and dual feasibility), matching the Gurobi version’s OptimalityTol/ FeasibilityTol=1e-9 – important for iteration-by-iteration agreement with the Gurobi backend over long runs, where looser tolerances would let small per-call differences accumulate.
highspy is imported at module import time but optionally (highspy =
None if it isn’t installed, raising only on first use) – so import
mga_surveyor (and picking projection_backend='gurobi' throughout) never
requires highspy to be installed.
As in gurobi_projection, the persistent per-(thread, norm) model assumes
every call from one thread passes the same growing points array (new rows
only appended), as one Method’s own executor does.