Solver-Free Decision-Focused Learning via Neural Optimization Layers for Edge Selection
Organizations: Department of Data Science and AI, Faculty of Information Technology, Monash University, Clayton, 3800, Victoria, Australia · ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA), Melbourne, 3000, Victoria, Australia
Abstract
Decision-focused learning trains prediction models to improve downstream decisions, but many methods require costly solver calls or optimal-solution labels. We propose a solver-free decision-focused learning framework for NP-hard edge-selection problems with uncertain parameters in the objective, the constraints, or both. A neural optimization layer is first trained without solution labels, using problem objectives and constraint penalties. Graph-informed edge scoring and iterative refinement encourage concentrated and structurally consistent continuous decisions. The layer is then frozen, and a prediction model is trained through its continuous output using a problem-specific loss evaluated under observed parameters. At deployment, the predictor, optimization layer, and a lightweight decoder produce decisions without solving the original NP-hard problem. Experiments on the asymmetric traveling salesperson and endpoint-free orienteering problems show consistently better decision quality than prediction-focused learning and improvements over most evaluated decision-focused baselines. Our framework requires less training time than the evaluated decision-focused baselines, even when optimization-layer pretraining is included. Neural deployment also produces decisions faster than solver-based deployment, offering a better quality-efficiency trade-off. The layer also reduces training cost in existing decision-focused methods when used as an approximate optimization oracle.
Figures & tables
| Nodes | Degree | Method | Regret (%) | Training time (h:m:s) | Inference time (ms/instance) | |||||
| Mean | Median | P95 | Worst | |||||||
| 50 | 4 | MSE | 33.19 | 31.33 | 55.48 | 123.20 | 0 0.14 | 86.69 | ||
| SPO+ | 9.76 | 9.45 | 17.00 | 37.34 | 6: | 50.91 | 99.81 | |||
| SPO+ (NOL oracle) | 12.88 | 11.67 | 23.93 | 48.74 | 22.52 | 108.07 | ||||
| CaVE | 10.25 | 9.80 | 17.59 | 38.10 | 1: | 23.70 | 91.32 | |||
| PGC | 12.56 | 11.68 | 22.44 | 37.12 | 12: | 52.79 | 97.36 | |||
| Nodes | Degree | Uncertain components | Method | Regret (%) | Training time (h:m:s) | Inference time (ms/instance) | |||||
| Mean | Median | P95 | Worst | ||||||||
| 50 | 4 | Constraints | MSE | 33.19 | 32.06 | 51.03 | 70.66 | 0 0.08 | 251.55 | ||
| Odece | 21.68 | 20.36 | 39.74 | 58.51 | 28: | 18.94 | 428.33 | ||||
| Odece (NOL oracle) | 23.14 | 22.34 | 38.18 | 51.91 | 6: | 19.22 | 468.97 | ||||
| DFLNOL | 12.61 | 12.14 | 21.85 | 45.70 | 21.77 | 9.74 | |||||
| DFLNOL Gurobi | 18.56 | 17.62 | 31.14 | 46.99 | 21.77 | 247.47 | |||||
Decision-Focused Learning
Decision-focused learning trains predictive models to improve the quality and cost of the decisions they inform.
See all 55 papers