AI Paper Atlas

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

AAAI 2020 · Learning theory and algorithms › Combinatorial and search optimization · approach: Unsupervised neural combinatorial optimization · 28 citations (OpenAlex)

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 changedWhereMeasuredEffect
use NDP instead of Hungarian solverLSAP 20 jobs · LSAP 20 jobstime: 1.47s -> 0.01sImproved
use NDP instead of greedy heuristicLSAP 20 jobs · LSAP 20 jobsoptimality gap: 11.55% -> 3.07%Improved
use NDP instead of attention model on TSP 20TSP 20 cities · TSP 20 citiesoptimality gap: 0.08% -> 2.54%; 0.31s -> 0.06sMixed
use NDP instead of attention model on TSP 50TSP 50 cities · TSP 50 citiesoptimality gap: 1.76% -> 12.02%; 1.38s -> 0.14sMixed
use NDP-Policy instead of heuristic LWCTalent scheduling 20 scenes · Talent scheduling 20 scenesoptimality gap: 20.2% -> 4.18%Improved
use NDP-Policy instead of exact EBB solverTalent scheduling 30 scenes · Talent scheduling 30 scenestime: 1030.80s -> 0.15sImproved
policy-based NDP instead of value-based NDPTalent scheduling 20 scenes · Talent scheduling 20 scenesoptimality gap: 15.80% -> 4.18%Improved
policy-based NDP instead of value-based NDPTSP 20 cities · TSP 20 citiesoptimality gap: 3.84% -> 2.54%Improved
policy-based NDP instead of value-based NDPLSAP 20 jobs · LSAP 20 jobsoptimality gap: 3.47% -> 3.07%No clear effect
fine-tune all DNNs jointly after pre-training (ablation)NDP · validation gap on LSAP, TSP, talent schedulingperformance gapImproved
use larger hidden layer 16n instead of 8n (ablation)NDP LSAP · LSAPperformance gap: less than 0.5 percent reductionNo clear effect

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy