Research map / Learning theory and algorithms / Combinatorial and search optimization
Solver-Free Decision-Focused Learning for Linear Optimization Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LAVA, a solver-free decision-focused learning loss for linear optimization that contrasts the ground-truth optimal vertex with its precomputed adjacent vertices, cutting training time while keeping regret close to SPO+ and PFYL.
Problem
Decision-focused learning for predict-then-optimize with linear programs is computationally expensive because each loss evaluation requires solving the optimization problem with predicted costs.
Approach
A solution is optimal iff it is at least as good as its adjacent vertices on the polytope; the LAVA loss hinges the difference between the predicted objective of the ground-truth optimal vertex and each precomputed adjacent vertex, requiring no solver calls during training. Adjacent vertices are precomputed via simplex pivots, using a geometric-degeneracy-aware procedure (TNP rule) for degenerate
Key results
- LAVA test regret 0.016 on random LPs vs 0.015 for SPO+, with training time 5.8s vs 180.2s for SPO+ and 469.1s for CaVE.
- On multi-dimensional knapsack LAVA reaches 0.086 regret (SPO+ 0.082) with training time 9.8s vs 303.3s for SPO+ and 581.1s for PFYL.
- On the highly degenerate shortest path benchmark LAVA is slower (13.0s) than SPO+ (18.6s) and NCE (0.6s) and has worse regret (0.060 vs 0.052 for SPO+), the main cost being adjacent vertex precomputation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LAVA instead of SPO+ | Linear regressor · Random LP | normalized regret: 0.015 ± 0.001 -> 0.016 ± 0.001 | Mixed |
| Use LAVA instead of SPO+ | Linear regressor · Multi-dimensional knapsack | normalized regret: 0.082 ± 0.001 -> 0.086 ± 0.002 | Hurt |
| Use LAVA instead of SPO+ | Linear regressor · Shortest Path | normalized regret: 0.052 ± 0.007 -> 0.060 ± 0.012 | Hurt |
| Use LAVA instead of SPO+ | Linear regressor · Random LP | training time (seconds): 180.2± 21.8 -> 5.8 ± 0.1 | Helped |
| Use LAVA instead of SPO+ | Linear regressor · Multi-dimensional knapsack | training time (seconds): 303.3 ± 74.6 -> 9.8 ± 1.4 | Helped |
| Use LAVA instead of SPO+ | Linear regressor · Shortest Path | training time (seconds): 18.6 ± 1.3 -> 13.0 ± 1.0 | Helped |
| Set ε to 0.1 rather than 0 (ablation) | LAVA · Random LP | normalized regret: 0.023 ± 0.001 -> 0.016 ± 0.001 | Helped |
| Set ε to 0.1 rather than 0 (ablation) | LAVA · Multi-dimensional knapsack | normalized regret: 0.127 ± 0.007 -> 0.086 ± 0.002 | Helped |
| Set ε to 0.1 rather than 0 (ablation) | LAVA · Shortest Path | normalized regret: 0.061 ± 0.008 -> 0.060 ± 0.012 | No clear effect |
| Remove the loss threshold by setting ε to ∞ instead of 0.1 (ablation) | LAVA · Random LP | normalized regret: 0.016 ± 0.001 -> 0.166 ± 0.009 | Hurt |
| Remove the loss threshold by setting ε to ∞ instead of 0.1 (ablation) | LAVA · Multi-dimensional knapsack | normalized regret: 0.086 ± 0.002 -> 0.156 ± 0.003 | Hurt |
| Remove the loss threshold by setting ε to ∞ instead of 0.1 (ablation) | LAVA · Shortest Path | normalized regret: 0.060 ± 0.012 -> 0.243 ± 0.022 | Hurt |
Surprising findings
- On shortest path, LAVA takes longer to train than most baselines because adjacent-vertex precomputation is expensive under high degeneracy.
- Removing the hinge threshold (epsilon = infinity) drastically worsens regret, e.g. 0.166 vs 0.016 on random LPs.
Limitations
- Performance degrades on highly degenerate problems such as shortest path, where adjacent-vertex precomputation is costly.
- Applies to LPs; ILPs/MILPs handled only via LP relaxation with containment or integrality-gap caveats.
- Evaluated only with linear regression models and small problem sizes.
Experimental setup
Datasets: Random LP (synthetic) Multi-dimensional knapsack (synthetic with California housing features) Shortest path 5x5 grid (synthetic polynomial mapping) California house prices
Benchmarks: Random LPs Multi-dimensional knapsack Shortest path
Metrics: normalized regret training time
Baselines: MSE SPO+ PFYL NCE CaVE
Builds on: SPO+ Perturbed Fenchel-Young loss CaVE NCE loss PyEPO
Closest papers by meaning
- Feasibility-Aware Decision-Focused Learning for Predicting Parameters in the Constraints (NeurIPS 2025 · similarity 0.90)
- DFF: Decision-Focused Fine-Tuning for Smarter Predict-Then-Optimize with Limited Data (AAAI 2025 · similarity 0.88)
- Locally Convex Global Loss Network for Decision-Focused Learning (AAAI 2025 · similarity 0.87)
- What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization (NeurIPS 2025 · similarity 0.87)
- A Generalization Result for Convergence in Learning-to-Optimize (ICML 2025 · similarity 0.86)
- Leaving the Nest: Going beyond Local Loss Functions for Predict-Then-Optimize (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.