Preparation phase¶
The preparation phase turns the full model into a compact description that the exploration phase can work with in real time. It is computationally heavy, but runs only once per model.
Sample points¶
Start from the near-optimal set \(\mathcal{Z}\): the property-of-interest (PoI) values \(z = Dx\) of all designs within a cost slack \(\epsilon\) of the optimum. The preparation phase collects \(n\) sample points \(z^{(1)}, \dots, z^{(n)} \in \mathcal{Z}\):
vertices of \(\mathcal{Z}\), found by an MGA method, and
optionally interior points, for example the vertices found for a smaller slack, which improve the approximations used later.
The sample points are collected as the columns of a matrix \(S = [z^{(1)}, \dots, z^{(n)}] \in \mathbb{R}^{n_z \times n}\). In this repository the samples come from MGA Surveyor, whose inner approximation consists of exactly such near-optimal points.
The cheapest design behind each sample¶
Many designs map to the same PoI values, so each sample point has many designs behind it. Of these, the cheapest is the interesting one. It is found by fixing the PoIs and minimizing cost:
For each sample \(z^{(i)}\) this gives
its cost \(\nu^{(i)} = \nu(z^{(i)})\), collected in the vector \(v = [\nu^{(1)}, \dots, \nu^{(n)}]\),
the full design \(x^{(i)}\), used later to show detailed results such as dispatch, and
the duals \(\mu^{(i)}\) of the fixing constraint, used later for a cost lower bound.
Approximating the cost anywhere¶
With the samples and their costs, the cost of any point \(z\) in their convex hull can be approximated, without the full model, by the convex combination problem
The weights \(\alpha\) describe \(z\) as a mixture of samples. Because \(\nu\) is convex, mixing samples never underestimates the cost: \(\nu(z) \le v^\top \alpha\) for any feasible \(\alpha\). CCP finds the mixture with the tightest such upper bound.
This is the key to real-time exploration: everything the exploration phase does is a small linear program over the \(n\) weights \(\alpha\), whatever the size of the original model.
In the code¶
A near-optimal set holds what the preparation phase produces: the sample points with their costs and duals, and optionally detailed outputs per sample; see Near-optimal set format. MGA Surveyor exports one with
export_near_optimal_set().navigable_points()gives its points as aPointstable (one row per sample, one column per PoI, plus the cost column).point_2_alpha()solves CCP: it fixes every PoI column and minimizes the cost column.mix_output()mixes a detailed output with weights \(\alpha\), giving \(x = \sum_i \alpha_i x^{(i)}\). It reads only the samples with a weight.The scripts in
mga-compass/scriptsbuild a set for the web platform from a PyPSA network using MGA Surveyor; see Build a dataset for the platform.