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 |
|---|---|---|
G-ORACLE, beneath-and-beyond on the dual polytope (Qhull, floating point) |
G-BB |
|
|
G-ORACLE, double description (patched cddlib, floating point) |
G-DD-float |
|
G-ORACLE, double description in exact rational arithmetic |
G-DD-rational |
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.