Research map / Learning theory and algorithms / Combinatorial and search optimization
Improving Optimization Bounds Using Machine Learning: Decision Diagrams Meet Deep Reinforcement Learning
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 a DRL-learned variable ordering instead of RAND, MIN, MPD, or DEG | Relaxed DD bounds for MISP · MISP, BA graph distributions tested (ν=2, 4, 8, 16), w=100 | optimality gap | Helped |
| Use a DRL-learned variable ordering instead of the tested ordering heuristics | Restricted DD bounds for MISP · MISP, BA graph distributions tested (ν=2, 4, 8, 16), w=2 | optimality gap | Helped |
| Train the ordering model at one DD width and evaluate it at other widths (ablation) | DRL ordering for relaxed DDs · MISP, BA graphs (ν=4) | optimality gap | No clear effect |
| Increase relaxed-DD width beyond 1000 (ablation) | RL-UB-4 · MISP, BA graphs (ν=4) | optimality gap | Helped |
| Increase relaxed-DD width to 10000 (ablation) | RL-UB-4 · MISP, BA graphs (ν=4) | optimality gap | Helped |
| Evaluate on graphs much larger than those used for training (ablation) | DRL ordering for relaxed DDs · MISP, larger BA graphs (ν=4), w=100 | optimality gap | Hurt |
| Evaluate on a graph distribution increasingly different from the training distribution (ablation) | DRL ordering for MISP · MISP, BA graphs with different ν | relative gap to the model trained on the tested distribution | Hurt |
| Use a model trained for restricted DDs to order relaxed DDs, or vice versa (ablation) | DRL ordering for MISP · MISP, BA graphs (ν=4) | optimality gap | Hurt |
| Use a DRL-learned variable ordering instead of RAND or MAX-WEIGHT | Relaxed and restricted DD bounds for MCP · MCP, BA graphs (ν=4), relaxed w=100 and restricted w=2 | optimality gap | Helped |
| Use the LP relaxation rather than the DRL-ordered relaxed DD | MISP · Relatively sparse BA graphs | upper-bound optimality gap | Hurt |
Closest papers by meaning
- Using Clustering to Strengthen Decision Diagram Bounds for Discrete Optimization (AAAI 2024 · similarity 0.89)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.86)
- Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization (ICML 2025 · similarity 0.86)
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates (AAAI 2024 · similarity 0.85)
- Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation (NeurIPS 2025 · similarity 0.85)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · 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.