Choosing a method

All trial-point methods share the Method interface, so drive() runs any of them unchanged. They differ only in how they find the vertex of the outer approximation furthest from the inner one, which is Step 2 of the algorithm.

Class

Approach

Paper name

BBMethod

G-ORACLE, beneath-and-beyond on the dual polytope (Qhull, floating point)

G-BB

CddMethod, backend="float"

G-ORACLE, double description (patched cddlib, floating point)

G-DD-float

CddMethod, backend="gmp"

G-ORACLE, double description in exact rational arithmetic

G-DD-rational

BilevelMethod

ORACLE’s bilevel problem as a MILP (Gurobi, \(\ell_\infty\) only)

O-MILP

What the experiments showed

The paper compared all four on the same inner and outer approximations of a PyPSA-Eur model with eight PoIs:

  • G-BB matched the exact reference (G-DD-rational) to within \(3 \times 10^{-7}\) percentage points at every iteration, and took at most 7 s per iteration.

  • G-DD-rational is exact, but took up to 2.9 h per iteration (41.5 h in total).

  • G-DD-float was about as fast as G-BB, but lost vertices as the run went on (only 12% of the exact vertex count by the end). From iteration 89 on it underestimated the distance in 66 iterations, which can stop a run before it has really converged.

  • O-MILP grew by about 12% per iteration and exceeded 8 hours at iteration 94.

Recommendation: use BBMethod. It is as fast as the floating-point double description and as accurate as the exact one. Use CddMethod with backend="gmp" when you need an exact reference, and BilevelMethod only to compare against ORACLE.

generate_mga_files() follows this recommendation: its vertex_method defaults to "bb". Pass vertex_method="cdd" to use the floating-point double description instead.

Norm

The norm fixes what “furthest” and “nearest” mean, and so what the tolerance guarantees. \(\ell_\infty\) is usually the right choice: with normalization it bounds the error of every PoI individually, rather than a sum or an average over all of them. The \(\ell_2\) norm needs a quadratic objective, which only Gurobi supports, and the nearest-point solve against a PyPSA network currently supports only \(\ell_1\) and \(\ell_\infty\).

Projection backend

The per-vertex projection \(f(v)\) is a small convex problem, solved with Gurobi (gurobi_projection) or HiGHS (highs_projection). HiGHS is open source and handles \(\ell_1\) and \(\ell_\infty\); Gurobi needs a licence but also handles \(\ell_2\).

Several trial points per iteration

Since G-ORACLE knows the distance of every vertex, it can solve the nearest-point problem for several far vertices at once instead of only the furthest. With max_parallel > 1, drive does this for methods that provide find_pool_trial_points, which is currently CddMethod only. The paper notes the caveat: nearby vertices give largely redundant cuts, so convergence does not speed up in proportion to the extra solves.