Solution Pool

End-to-end predict-then-optimize training repeatedly solves 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 best cached solution under the predicted cost (lowest objective for minimization, highest for maximization) instead of solving the original linear or integer program.

Algorithm

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\), \(S\) is the solution pool, and Eq. (1) is the underlying problem \(\min_{v} \tilde{c}^\top v\) over \(\{v : A v \le b\}\). The probability \(p_{\text{solve}}\) corresponds to solve_ratio.

Usage

Every pyepo.func module supports the solution pool except CaVE. CaVE has no pool and uses solve_ratio for its projection branch instead (see CaVE).

solve_ratio sets the probability of solving exactly. PyEPO draws the coin once per batch rather than per instance, so this is the expected fraction of batches solved. The default is 1.0, which disables caching. When solve_ratio is less than 1, pass dataset to seed the pool with initial solutions. The contrastive (NCE / CMAP) and learning-to-rank losses require dataset even at the default.

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

import pyepo

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