Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization

2018/09/14 by Bryan Wilder, Bistra Dilkina, Wilder, Bryan +3 · 23 citations
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #Mobile Crowdsensing and Crowdsourcing

paper · pdf · doi:10.48550/arxiv.1809.05504

openalex publication_date 2018/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Creating impact in real-world settings requires artificial intelligence techniques to span the full pipeline from data, to predictive models, to decisions. These components are typically approached separately: a machine learning model is first trained via a measure of predictive accuracy, and then its predictions are used as input into an optimization algorithm which produces a decision. However, the loss function used to train the model may easily be misaligned with the end goal, which is to make the best decisions possible. Hand-tuning the loss function to align with optimization is a difficult and error-prone process (which is often skipped entirely). We focus on combinatorial optimization problems and introduce a general framework for decision-focused learning, where the machine learning model is directly trained in conjunction with the optimization algorithm to produce high-quality decisions. Technically, our contribution is a means of integrating common classes of discrete optimization problems into deep learning or other predictive models, which are typically trained via gradient descent. The main idea is to use a continuous relaxation of the discrete problem to propagate gradients through the optimization procedure. We instantiate this framework for two broad classes of combinatorial problems: linear programs and submodular maximization. Experimental results across a variety of domains show that decision-focused learning often leads to improved optimization performance compared to traditional methods. We find that standard measures of accuracy are not a reliable proxy for a predictive model's utility in optimization, and our method's ability to specify the true goal as the model's training objective yields substantial dividends across a range of decision problems.

Citations

• From Data to Knowledge to Action: A Global Enabler for the 21st Century
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization
• OptNet: Differentiable Optimization as a Layer in Neural Networks
• SparseMAP: Differentiable Sparse Structured Inference

Cited by

• Smooth Learning with Hard Constraints via Legendre-Regularized Policies
• ORPR: An OR-Guided Pretrain-then-Reinforce Learning Model for Inventory Management
• Policy-Aligned Estimation of Conditional Average Treatment Effects
• CORL: Reinforcement Learning of MILP Policies Solved via Branch and Bound
• Scalable Decision Focused Learning via Online Trainable Surrogates
• Learning-Based Hierarchical Approach for Fast Mixed-Integer Optimization
• A Fully First-Order Layer for Differentiable Optimization
• Neuro-Symbolic Constrained Optimization for Cloud Application Deployment via Graph Neural Networks and Satisfiability Modulo Theory
• A Dual Perspective on Decision-Focused Learning: Scalable Training via Dual-Guided Surrogates
• Neural Index Policies for Restless Multi-Action Bandits with Heterogeneous Budgets
• Privacy-preserving Decision-focused Learning for Multi-energy Systems
• Diffusion-DFL: Decision-focused Diffusion Models for Stochastic Optimization
• Feasibility-Aware Decision-Focused Learning for Predicting Parameters in the Constraints
• Multi-channel Uplift Policy Learning
• Inverse Optimization Latent Variable Models for Learning Costs Applied to Route Problems
• Loss-aware distributionally robust optimization via trainable optimal transport ambiguity sets
• Prediction Loss Guided Decision-Focused Learning
• Decision-Focused Learning Enhanced by Automated Feature Engineering for Energy Storage Optimisation
• Simulating classification models to evaluate Predict-Then-Optimize methods
• Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives
• Aligning the Evaluation of Probabilistic Predictions with Downstream Value
• Minimizing Surrogate Losses for Decision-Focused Learning using Differentiable Optimization
• Who Pays the RENT? Implications of Spatial Inequality for Prediction-Based Allocation Policies

Related

• Decision-Focused Learning: Through the Lens of Learning to Rank
• Machine learning for combinatorial optimization: A methodological tour d’horizon
• Machine Learning for Combinatorial Optimization: a Methodological Tour\n d'Horizon
• A Dual Perspective on Decision-Focused Learning: Scalable Training via Dual-Guided Surrogates
• Decision-Focused Learning without Differentiable Optimization: Learning Locally Optimized Decision Losses