Research map / Learning theory and algorithms / Combinatorial and search optimization
A Divide and Conquer Algorithm for Predict+Optimize with Non-convex 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 |
|---|---|---|---|
| Use exact transition-point reasoning with DNL-Greedy instead of ridge regression | Scheduling PPO · Scheduling, 2 machines, 1 job | normalized mean regret: 0.73±0.33 (5) | Helped |
| Use exact transition-point reasoning with DNL-Greedy instead of ridge regression | Scheduling PPO · Scheduling, 2 machines, 2 jobs | regret | Hurt |
| Use exact transition-point reasoning with DNL-Greedy instead of SPO-Relax | Scheduling PPO · Scheduling with 3 machines | normalized mean regret | Helped |
| Use exact transition-point reasoning with DNL-Greedy instead of surrogate methods | Weighted knapsack · Weighted knapsack, capacities 12–220 | normalized mean regret | Helped |
| Use DNL transition-point extraction instead of DP-based extraction | Knapsack PPO · 0-1 knapsack benchmarks | normalized mean regret | No clear effect |
| Use DNL-Greedy rather than full DNL transition-point mapping (ablation) | DNL · Knapsack and scheduling benchmarks | normalized mean regret | No clear effect |
| Stop transition-point extraction at the first point that improves TOV (ablation) | DNL-Greedy · Knapsack and scheduling benchmarks | training time: N 2 | Helped |
| Use coordinate descent to optimize model parameters (ablation) | DNL · Multivariate predict+optimize problems | optimality | Hurt |
| Use a numerical divide-and-conquer search for transition points rather than DP extraction | DNL · Knapsack benchmarks | training time | Helped |
| Use a differentiable surrogate rather than exact combinatorial reasoning | SPO-Relax, QPTL, and IntOpt · Hard weighted-knapsack and scheduling benchmarks | normalized mean regret | Hurt |
Closest papers by meaning
- UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems (NeurIPS 2024 · similarity 0.87)
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 2024 · similarity 0.86)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.85)
- Solver-Free Decision-Focused Learning for Linear Optimization Problems (NeurIPS 2025 · similarity 0.85)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.85)
- Adaptive Partitioning Schemes for Optimistic Optimization (ICML 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.