Research map / Learning theory and algorithms / Combinatorial and search optimization
Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train with SPO-relax instead of MSE-r | linear prediction models for hard ICON scheduling · ICON hard scheduling instances 1–5 | relaxed regret: 72,662; 120,800; 108,748; 109,694; 118,946 | Helped |
| Use the continuous relaxation as the training oracle instead of the exact discrete problem (ablation) | SPO · knapsack and energy scheduling instances | test regret | No clear effect |
| Pretrain with MSE for 6 epochs before continuing with SPO-relax (ablation) | SPO-relax · three scheduling instances | per-epoch runtime: 6.5 (1.5) sec -> 8 (0.5) sec; 7 (1.5) sec -> 6 (1.0) sec; 10 (0.5) sec -> 12 (1.0) sec | No clear effect |
| Warmstart solver calls from an earlier basis (ablation) | SPO-relax · three scheduling instances | per-epoch runtime: 6.5 (1.5) sec -> 1.5 (0.2) sec; 7 (1.5) sec -> 1 (0.2) sec; 10 (0.5) sec -> 2.5 (0.1) sec | Helped |
| Add objective cuts when warmstarting the relaxation (ablation) | SPO-relax · relaxation solving | runtime | Hurt |
| Use SPO-relax instead of QPTL | linear prediction models · unweighted knapsack and two energy-scheduling instances | regret | Helped |
| Use SPO-relax instead of QPTL | linear prediction models · weighted knapsack | regret | Mixed |
| Use SPO-relax instead of QPTL | linear prediction models · weighted knapsack, capacity 60 | regret | Hurt |
Closest papers by meaning
- Dynamic Programming for Predict+Optimise (AAAI 2020 · similarity 0.88)
- Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime (NeurIPS 2024 · similarity 0.87)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.86)
- BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.86)
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 2024 · similarity 0.85)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.85)
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.