Research map / Probabilistic and scientific modeling / Molecules and proteins
Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime
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.
Benchmarks 11 predict-then-optimize (PtO) and predict-and-optimize (PnO) methods across 8 predictive combinatorial optimization problems in a modular framework, and releases a new industrial combinatorial advertising dataset.
Problem
Predictive combinatorial optimization, where objective coefficients are unknown at decision time, lacks a systematic benchmark comparing two-stage PtO and end-to-end PnO methods and a real-world evaluation dataset.
Approach
Categorizes PnO methods by how the discrete/continuous solution gradient is handled (discrete, continuous, statistical, surrogate) and implements them in one modular framework with unified predictors, solvers, losses and evaluations, plus a new industrial combinatorial advertising dataset.
Key results
- PnO methods beat the two-stage PtO baseline on 7 of 8 benchmarks, per the paper's summary.
- On Knapsack (Gen), listwise-LTR achieves 6.031% regret vs 6.595% for two-stage; SPO reaches 1.505% on energy scheduling vs 1.793% for two-stage.
- On combinatorial advertising, Identity reaches uplift 0.135 vs 0.069 for two-stage.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use listwise-LTR instead of Two-stage | Knapsack (Gen) · Knapsack (Gen) | regret (%): 6.595 -> 6.031 | Helped |
| use listwise-LTR instead of Two-stage | Knapsack (Energy) · Knapsack (Energy) | regret (%): 8.745 -> 8.083 | Helped |
| use SPO instead of Two-stage | Energy scheduling · Scheduling (Energy) | regret (%): 1.793 -> 1.505 | Helped |
| use SPO instead of Two-stage | Budget Allocation · Budget Allocation | regret (%): 20.332 -> 5.559 | Helped |
| use LODL instead of Two-stage | TopK (Cubic) · TopK (Cubic) | regret (%): 0.110 -> 0.172 | Hurt |
| use pointwise-LTR instead of Two-stage | Bipartite Matching · Bipartite Matching | regret (%): 92.963 -> 91.035 | Helped |
| use LODL instead of Two-stage | Portfolio optimization · Portfolio | regret: 0.243 -> 0.160 | Helped |
| train with Identity instead of Two-stage | Combinatorial Advertising · Combinatorial Advertising | uplift: 0.069 -> 0.135 | Helped |
| warm up with PtO MSE training, then fine-tune with Blackbox PnO (ablation) | Blackbox · 7 benchmark datasets | regret | Mixed |
| warm up with PtO MSE training, then fine-tune with Identity PnO (ablation) | Identity · 7 benchmark datasets | regret | Mixed |
| increase knapsack capacity from 30 to 60 and 90 (ablation) | Knapsack (Gen) methods · Knapsack (Gen), capacity sensitivity | regret | Mixed |
| increase the number of decision variables (ablation) | Knapsack (Gen) methods · Knapsack (Gen), variable-size sensitivity | regret | Mixed |
Surprising findings
- Discrete-category methods (DFL, Blackbox, Identity) often underperform the two-stage baseline on non-linear tasks such as budget allocation and top-k.
- PnO methods can achieve lower regret despite higher prediction MSE, suggesting better error trade-offs.
Limitations
- Covers only a subset of CO problems and methods; not exhaustive.
- No single PnO method dominates across all problems and settings.
- Current PnO methods degrade under tighter constraints, larger variable sizes, and distribution shift.
Experimental setup
Datasets: SEMO Yahoo! Webscope Cora Quandl Generated knapsack and cubic top-k
Benchmarks: Knapsack (Gen) Knapsack (Energy) Energy scheduling Budget allocation Cubic Top-K Bipartite matching Portfolio optimization Combinatorial advertising
Metrics: relative regret (%) uplift train time test time
Baselines: Two-stage DFL Blackbox Identity CPLayer SPO NCE LTR LODL
Builds on: SPO Blackbox OptNet LODL NCE
Closest papers by meaning
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.85)
- BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.85)
- Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization (NeurIPS 2025 · similarity 0.84)
- PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization (NeurIPS 2025 · similarity 0.83)
- Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks (NeurIPS 2026 · similarity 0.83)
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 2024 · similarity 0.83)
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.