Solution Pool¶

End-to-end predict-then-optimize training involves repeated solving of optimization problems. A solution pool [1] stores previously computed solutions and uses them as an inner approximation of the feasible region.

When the pool is used, PyEPO selects the lowest-objective cached solution instead of solving the original linear/integer program.

The algorithm is shown below.

Algorithm: Gradient descent with inner approximation (numbering follows [1])

Input: \(A, b\); training data \(\mathcal{D} \equiv \{(x_i, c_i)\}_{i=1}^n\)

Hyperparams: \(\alpha\) (learning rate), epochs, \(p_{\text{solve}}\)

\[\begin{split}\begin{array}{rl} 1: & \text{Initialize}\ \omega \\ 2: & \text{Initialize}\ S = \{v^*(c_i) \mid (x_i, c_i) \in \mathcal{D}\} \\ 3: & \textbf{for}\ \text{each epoch}\ \textbf{do} \\ 4: & \quad \textbf{for}\ \text{each instance}\ \textbf{do} \\ 5: & \quad\quad \tilde{c} \leftarrow t(\hat{c})\ \text{with}\ \hat{c} = m(\omega, x) \\ 6: & \quad\quad \textbf{if}\ \mathrm{random}() < p_{\text{solve}}\ \textbf{then} \\ 7: & \quad\quad\quad \text{Obtain}\ v\ \text{by calling a solver for Eq.}\ (1)\ \text{with}\ \tilde{c} \\ 8: & \quad\quad\quad S \leftarrow S \cup \{v\} \\ 9: & \quad\quad \textbf{else} \\ 10: & \quad\quad\quad v = \arg\min\limits_{v' \in S} f(v', \tilde{c}) \\ 11: & \quad\quad \textbf{end if} \\ 12: & \quad\quad \omega \leftarrow \omega - \alpha\, \dfrac{\partial \mathcal{L}^v}{\partial \tilde{c}}\, \dfrac{\partial \tilde{c}}{\partial \omega} \\ 13: & \quad \textbf{end for} \\ 14: & \textbf{end for} \\ \end{array}\end{split}\]

In the algorithm, \(\omega\) are the predictor weights, \(m(\omega, x) = \hat{c}\) is the predicted cost, \(t(\cdot)\) is an optional cost transform, \(v^*(c)\) is the optimum for cost \(c\), and \(S\) is the solution pool. The probability \(p_{\text{solve}}\) corresponds to solve_ratio.

The solution pool is integrated into all pyepo.func modules.

solve_ratio controls the fraction of instances solved exactly during training. The default is 1.0 (no caching). When solve_ratio is less than 1, pass dataset to seed the pool with initial solutions.

Example with SPO+ (other functions work the same way):

import pyepo

spo = pyepo.func.SPOPlus(optmodel, processes=2, solve_ratio=0.7, dataset=dataset)