Source-linked AI summary
Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems
Jaynta Mandi, Emir Demirović, Peter. J Stuckey, Tias Guns
TL;DR
Prediction errors do not affect combinatorial optimization outcomes uniformly, motivating learning methods that account for optimization regret rather than prediction error alone. The paper extends SPO to hard discrete problems using relaxations and warmstarting to reduce repeated-solving costs. Across the studied problems, relaxation-based SPO often matches exact SPO, outperforms Melding in most instances, and reaches large-scale combinatorial applications.
Problem
Standard machine-learning training can ignore optimization regret, while SPO's repeated problem solving is computationally expensive for hard discrete combinatorial problems.
Method
The paper applies SPO to discrete combinatorial problems and investigates continuous relaxations, transfer learning, and warmstarting to reduce training and solving costs.
Results
Relaxation-based SPO achieves very similar performance to exact SPO across the studied instances and outperforms Melding in most cases.
Takeaways & Limitations
Training with relaxation solutions can guide learning effectively and open predict-and-optimize to larger and more complex combinatorial problems.
Takeaways & Limitations
The evaluated SPO-relax instances before the large-scale study were toy-level problems with relatively few decision variables and short solution times.
Abstract
from arXiv · showhide
Combinatorial optimization assumes that all parameters of the optimization problem, e.g. the weights in the objective function is fixed. Often, these weights are mere estimates and increasingly machine learning techniques are used to for their estimation. Recently, Smart Predict and Optimize (SPO) has been proposed for problems with a linear objective function over the predictions, more specifically linear programming problems. It takes the regret of the predictions on the linear problem into account, by repeatedly solving it during learning. We investigate the use of SPO to solve more realistic discrete optimization problems. The main challenge is the repeated solving of the optimization problem. To this end, we investigate ways to relax the problem as well as warmstarting the learning and the solving. Our results show that even for discrete problems it often suffices to train by solving the relaxation in the SPO loss. Furthermore, this approach outperforms, for most instances, the state-of-the-art approach of Wilder, Dilkina, and Tambe. We experiment with weighted knapsack problems as well as complex scheduling problems and show for the first time that a predict-and-optimize approach can successfully be used on large-scale combinatorial optimization problems.
Introduction
The paper extends predict-and-optimize learning from linear programs to hard discrete combinatorial problems, where prediction errors can affect optimization outcomes unevenly. Its central scaling challenge is the computational cost of repeatedly solving these problems during training.
- Motivation: Prediction accuracy alone may not improve optimization outcomes because errors affect feasible decisions unevenly.For example, overestimating the highest-valued prediction may leave a maximization solution unchanged, whereas underestimating it can alter the outcome.
- Smart Predict and Optimize: SPO trains predictive models using a loss that accounts for the downstream optimization outcome.The approach was originally proposed for linear programming problems with predictions appearing as weights in a linear objective.
- Contribution: This work applies SPO to discrete combinatorial optimization problems with linear objectives and permits black-box optimization methods.Only the optimization outcome is needed to compute the loss subgradient.
- Scaling challenge: Repeatedly solving the optimization problem during training is the main computational challenge, particularly for NP-hard problems.The loss requires solving the problem once for every evaluation on a training instance.
- Scaling challenge: Continuous relaxations are highly informative for learning, enabling the approach to scale toward large problem instances.The paper investigates relaxation-based learning alongside transfer learning and warmstarting techniques.
- Results: The approach outperforms the state-of-the-art Melding approach in most cases and is demonstrated on large-scale combinatorial instances.The experiments include weighted knapsack and complex scheduling problems, including instances from the ICON energy-cost aware scheduling challenge.
Related Work
Related work develops decision-focused learning beyond conventional prediction training, including methods that differentiate through optimization or incorporate optimization losses. This paper positions its approach as a direct method for scaling such learning to hard combinatorial problems.
- Decision-focused learning: Predict-and-optimize applications commonly use two-stage training in which machine learning models are trained independently of the optimization task.Decision-focused learning instead aims to couple machine learning and decision making.
- Differentiating through optimization: Prior work differentiates through quadratic-program KKT conditions to obtain gradients of optimal solutions with respect to predictions.Wilder, Dilkina, and Tambe use this approach for their predict-and-optimize method.
- SPO for combinatorial optimization: The paper builds on SPO for discrete combinatorial problems with linear objectives, which are often computationally expensive or NP-hard to solve.Its setting differs from the original framework's linear optimization problems with convex feasible regions.
- Learning-approach taxonomy: Prior knapsack work classified learning approaches as indirect, semi-direct, or direct according to how they use optimization knowledge.The categories range from ignoring the optimization problem to encoding or using it directly during learning.
- Learning-approach taxonomy: This paper uses a direct approach and examines how to combine related techniques to scale to large and hard combinatorial problems.The stated goal is to combine the strengths of optimization-aware learning methods for scalability.
Problem Formulation and Approach
The paper formulates predict-and-optimize learning for parameterized discrete problems, then replaces prediction-error training with optimization-aware SPO losses. It addresses the computational cost of repeated combinatorial solves by using weaker oracles, including relaxations and approximation methods.
- Optimizing a parameterized problem: A parameterized combinatorial problem uses observed and unobserved coefficients, with an oracle returning an optimal solution under supplied parameters.The model predicts unobserved parameters from correlated attributes before optimization evaluates the resulting solution.
- Optimizing a parameterized problem: The training objective is ideally regret on unseen data: the difference between using predicted parameters and the actual optimal solution.Regret measures the optimization impact of prediction error rather than prediction error alone.
- Two Stage Learning: In two-stage learning, the predictive model minimizes a chosen loss such as MSE using stochastic gradient descent without solving the optimization problem during training.This decouples prediction training from downstream optimization and makes gradient-based training straightforward.
- Two Stage Learning: Two-stage training can select epochs and hyperparameters using regret on a validation set, but this only avoids worsening results rather than improving learning toward regret.The approach still optimizes prediction error directly during training.
- Smart Predict then Optimize (SPO): SPO integrates optimization into learning through a convex surrogate regret loss whose subgradient is the difference between solutions under actual and transformed predicted parameters.For knapsack, nonzero subgradient entries identify items where the two solutions disagree.
- Smart Predict then Optimize (SPO): Repeatedly solving NP-hard problems for every training instance makes SPO computationally expensive and can become infeasible at large scale.Each epoch may require hundreds of knapsack solves, while optimal solutions under actual parameters can be cached.
- Combinatorial problems and scaling up: SPO-full uses a combinatorial optimization oracle during training because the framework permits any black-box oracle whose outcome supplies the loss subgradient.The natural oracle directly solves the target combinatorial problem.
- Combinatorial problems and scaling up: Weaker training oracles reduce solving time by substituting approximation algorithms, continuous or tighter relaxations, time- or node-limited solutions, or gap-tolerant MIP solves.For knapsack, the greedy algorithm is one example; the resulting approach is called SPO-gap for gap-tolerant MIP training.
Experimental Evaluation
Experiments evaluate SPO-relax and SPO-full against prediction-focused and decision-focused baselines on knapsack and scheduling problems. SPO-relax closely matches SPO-full, converges faster, and remains effective on larger hard scheduling instances despite limited solving budgets.
- Experimental setup: Experiments cover unweighted and weighted knapsack plus easy and hard energy-cost aware scheduling problems.Hard scheduling instances use 10 machines and 200 tasks, while easy instances use 3 machines with 10, 15, or 20 tasks.
- Exact versus relaxed solving: SPO-relax achieves very similar performance to SPO-full across all tested problem instances.The results indicate that continuous relaxation solutions can guide learning comparably to exact discrete solutions.
- Exact versus relaxed solving: SPO-relax converges much faster than SPO-full when learning curves are measured by model runtime.Continuous relaxations are polynomial-time solvable, whereas the discrete problem can be worst-case exponential; SPO-relax remains slower than MSE-r but delivers better quality.
- SPO versus QPTL: SPO-relax almost always outperforms other methods on unweighted knapsack and is best for weighted knapsack except at lower capacities.QPTL performs worse than MSE-r on unweighted knapsack and improves relative to SPO-relax only at lower weighted-knapsack capacities.
- SPO versus QPTL: SPO-relax produces better solutions than QPTL in all Figure 5 cases except weighted knapsack with capacity 60, where QPTL converges better.QPTL generally converges more slowly, and SPO-relax performs better on two energy-scheduling instances while regrets are similar on another.
- Large hard instances: On hard scheduling instances, six hours of SPO-relax training covers only 50–80% of training instances yet outperforms MSE-learned models.Training processes 300 to 450 instances, and the authors report this result without MSE warmstarting.
Conclusions and future work
The paper argues that SPO can extend to hard combinatorial problems by using weaker optimization oracles and scaling techniques, while identifying directions for improving relaxations and repeated solving.
- SPO outperforms QPTL and supports black-box oracles because its loss computation uses only optimization outcomes.The authors report that weaker oracles can support SPO loss computation without requiring gradients through the optimizer.
- For the studied problems, training with SPO loss on continuous relaxations achieves equal performance to solving the discrete combinatorial problem.This finding supports using relaxations during learning instead of repeatedly solving the exact discrete problem.
- These relaxation-based methods open the way to larger and more complex combinatorial problems where exact solutions may be impossible to obtain repeatedly.The paper frames repeated exact solving as a barrier to scaling predict-and-optimize methods.
- For weaker relaxations, the authors suggest adding cutting planes before solving to improve the relaxation.This is presented as a possible future improvement rather than an evaluated result.
- The authors propose exploiting previously computed solutions beyond solver warmstarts, alongside local search, iterative refinement, and relaxed BDDs as future directions.These methods could improve repeated solving or refine solutions during loss computation.