Research map / Learning theory and algorithms / Combinatorial and search optimization
Deep Neural Network Approximated Dynamic Programming for Combinatorial Optimization
Shenghe Xu, Shivendra S. Panwar, Murali Kodialam, T.V. Lakshman
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 NDP instead of Hungarian solver | LSAP 20 jobs · LSAP 20 jobs | time: 1.47s -> 0.01s | Improved |
| use NDP instead of greedy heuristic | LSAP 20 jobs · LSAP 20 jobs | optimality gap: 11.55% -> 3.07% | Improved |
| use NDP instead of attention model on TSP 20 | TSP 20 cities · TSP 20 cities | optimality gap: 0.08% -> 2.54%; 0.31s -> 0.06s | Mixed |
| use NDP instead of attention model on TSP 50 | TSP 50 cities · TSP 50 cities | optimality gap: 1.76% -> 12.02%; 1.38s -> 0.14s | Mixed |
| use NDP-Policy instead of heuristic LWC | Talent scheduling 20 scenes · Talent scheduling 20 scenes | optimality gap: 20.2% -> 4.18% | Improved |
| use NDP-Policy instead of exact EBB solver | Talent scheduling 30 scenes · Talent scheduling 30 scenes | time: 1030.80s -> 0.15s | Improved |
| policy-based NDP instead of value-based NDP | Talent scheduling 20 scenes · Talent scheduling 20 scenes | optimality gap: 15.80% -> 4.18% | Improved |
| policy-based NDP instead of value-based NDP | TSP 20 cities · TSP 20 cities | optimality gap: 3.84% -> 2.54% | Improved |
| policy-based NDP instead of value-based NDP | LSAP 20 jobs · LSAP 20 jobs | optimality gap: 3.47% -> 3.07% | No clear effect |
| fine-tune all DNNs jointly after pre-training (ablation) | NDP · validation gap on LSAP, TSP, talent scheduling | performance gap | Improved |
| use larger hidden layer 16n instead of 8n (ablation) | NDP LSAP · LSAP | performance gap: less than 0.5 percent reduction | No clear effect |
Closest papers by meaning
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.87)
- Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization (ICML 2025 · similarity 0.87)
- UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems (NeurIPS 2024 · similarity 0.87)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.86)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · 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.
