PaperlayerView exact revision on arXiv

Source-linked AI summary

Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities

Jayanta Mandi, James Kotary, Senne Berden, Maxime Mulamba, Victor Bucarey, Tias Guns, Ferdinando Fioretto

arXiv:2307.13565v4cs.LGcs.AImath.OC

TL;DR

Decision-focused learning addresses the mismatch between prediction objectives and downstream optimization decisions under uncertainty. This survey organizes DFL methods, reviews their trade-offs, and evaluates them across multiple problems, finding that no single technique performs best everywhere.

  • Problem

    Predict-Then-Optimize methods evaluate predictions through downstream decisions, whereas standard machine-learning losses train prediction accuracy rather than decision quality directly.

  • Method

    The survey categorizes DFL into gradient-based and gradient-free methods, further dividing gradient-based techniques into four classes and reviewing their trade-offs.

  • Results

    No single DFL technique performs best across all experiments; performance varies by test problem, with QPTL substantially outperforming other techniques in bipartite matching but performing poorly in scheduling.

  • Takeaways & Limitations

    DFL methods should be assessed in relation to the decision problem because their comparative performance differs across problems and modeling settings.

  • Takeaways & Limitations

    ILPs create discontinuous, nondifferentiable mappings and are NP-hard, potentially preventing exact solution computation during every machine-learning training step.

Abstract

from arXiv · show

Decision-focused learning (DFL) is an emerging paradigm that integrates machine learning (ML) and constrained optimization to enhance decision quality by training ML models in an end-to-end system. This approach shows significant potential to revolutionize combinatorial decision-making in real-world applications that operate under uncertainty, where estimating unknown parameters within decision models is a major challenge. This paper presents a comprehensive review of DFL, providing an in-depth analysis of both gradient-based and gradient-free techniques used to combine ML and constrained optimization. It evaluates the strengths and limitations of these techniques and includes an extensive empirical evaluation of eleven methods across seven problems. The survey also offers insights into recent advancements and future research directions in DFL. Code and benchmark: https://github.com/PredOpt/predopt-benchmarks

1. Introduction

Decision-focused learning integrates prediction and constrained optimization end to end so models are trained for decision quality under uncertainty. The survey organizes DFL methods and benchmarks their performance across multiple problems.

  • Motivation: Real-world decision-making often requires estimating unknown optimization parameters from contextual data before prescribing decisions.ML estimates uncertain quantities, while constrained optimization selects decisions using those estimates.
  • Motivation: The conventional two-stage approach trains prediction and optimization independently, assuming more accurate predictions produce better decisions.DFL targets the mismatch between prediction quality and downstream decision quality.
  • Decision-Focused Learning: DFL trains the ML model end to end using a loss based on the resulting decisions rather than prediction accuracy alone.This requires integrating the optimization solver into the ML model and differentiating through it.
  • Survey Contributions: The survey distinguishes gradient-based from gradient-free methods and categorizes gradient-based techniques into four methodological classes.The classes cover analytical differentiation, analytical smoothing, random-perturbation smoothing, and surrogate-loss differentiation.
  • Survey Contributions: The paper provides publicly available problem-specific models, benchmarks methods on seven problems, and discusses open challenges and future directions.The benchmark code and data are available through the PredOpt benchmarks repository.

2. Preliminaries

Predict-Then-Optimize problems map features to uncertain parameters and then solve constrained optimization, exposing a gap between prediction loss and decision loss. DFL addresses this gap but faces nondifferentiability and substantial computational cost.

  • Problem Setting: Predict-Then-Optimize problems infer uncertain optimization parameters from features and use the predictions to compute prescriptive decisions.The decision is obtained by solving a constrained optimization problem with predicted parameters.
  • Problem Setting: The survey assumes constraints are known and parameter uncertainty appears only in the objective function.This assumption ensures model outputs remain feasible, whereas uncertain constraints can make the learning problem ill-defined without recourse.
  • Learning Paradigms: Predict-focused learning minimizes standard prediction losses, whereas DFL optimizes criteria measuring the quality of resulting optimization decisions.DFL integrates prediction and optimization into a composite framework.
  • Learning Paradigms: Prediction error and task loss can diverge: errors that preserve the selected solution may not increase regret, while smaller errors can change the decision.The two-item knapsack example illustrates that identical prediction errors can yield different regret.
  • Implementation Challenges: DFL training can be computationally expensive because it solves and differentiates the optimization problem for every sample in every epoch.This cost becomes a potential impediment for large and NP-hard problems.

2.4 Optimization Problem Forms

Optimization problem forms differ in solvability, differentiability, and the challenges they create for decision-focused learning. The survey covers convex, linear, integer linear, and integer nonlinear formulations, with examples spanning routing, ranking, selection, matching, and portfolio decisions.

  • 2.4.1 Convex Optimization: Convex optimization guarantees that every local optimum is global, but its solution mapping may still be nondifferentiable.Some convex problems yield everywhere-differentiable mappings, whereas linear programs provide a notable nondifferentiable example.
  • 2.4.2 Linear Programming: Linear programs use affine objectives and constraints and model resource allocation, sorting, top-k selection, shortest paths, matching, and related decisions.Their broad use in operations research reflects the prevalence of linear resource relationships.
  • 2.4.2 Linear Programming: LP solution mappings are piecewise constant, so their derivatives are zero almost everywhere and undefined elsewhere for gradient-based training.DFL methods therefore typically differentiate smooth approximations to the LP.
  • 2.4.2 Linear Programming: Top-k selection chooses k items with the largest total predicted value, while maximum computation is the special case k = 1.Entropy regularization makes the maximum mapping equivalent to a softmax function.
  • 2.4.2 Linear Programming: Max-flow places predicted capacities in constraint right-hand sides, whereas the equivalent min-cut formulation places them in the objective and fits the DFL setting.This dual reformulation allows DFL techniques to predict flow capacities.
  • 2.4.3 Integer Linear Programming: ILPs restrict variables to integer values, making their mappings discontinuous and nondifferentiable while their NP-hardness can prevent exact solution computation at every training step.Their discontinuous feasible regions also prevent many LP smoothing techniques.
  • 2.4.3 Integer Linear Programming: ILP examples include knapsack selection under capacity, travelling salesperson routing with predicted distances, and combinatorial portfolio optimization.The travelling salesperson formulation seeks a minimum-length path visiting every city exactly once.
  • 2.4.4 Integer Nonlinear Programming: Integer nonlinear programs combine integer variables with nonlinear objectives or constraints and inherit zero-valued gradients almost everywhere.The survey states that no DFL technique had specifically been developed for or tested on these problems, with approximate ILP surrogates as the closest related approach.

3. Review of Decision-Focused Learning Methodologies

DFL methodologies are divided into gradient-based and gradient-free categories. Gradient-based methods support neural-network models, while gradient-free methods avoid the zero-gradient issue and accommodate models that do not require gradients.

  • Gradient-based and Gradient-free DFL: Gradient-based DFL is extensively studied and supports deep neural networks as the underlying machine-learning model.Neural networks are commonly trained through gradient-based optimization.
  • Gradient-based and Gradient-free DFL: Gradient-free DFL uses model frameworks such as tree-based or search-based methods that do not require gradients.These methods can bypass the issue of zero-valued gradients altogether.
  • Gradient-based and Gradient-free DFL: The survey presents gradient-based DFL first and gradient-free DFL second as its two broad methodology categories.This classification separates methods by whether learning relies on computing gradients.

3.1 Review of Gradient-Based DFL Methodologies

Gradient-based DFL methods address the challenge of differentiating optimization mappings by using analytical derivatives, smoothing, random perturbations, or surrogate losses. These approaches enable end-to-end training, while differing in problem scope, approximation, solver dependence, and theoretical support.

  • Four classes organize gradient-based DFL techniques: analytical differentiation, analytical smoothing, smoothing by random perturbations, and differentiation of surrogate loss functions.The categorization supports systematic discussion and comparison of existing methods.
  • Analytical differentiation computes exact derivatives by differentiating optimality conditions for optimization forms where derivatives exist and are non-zero.
  • Analytical smoothing makes combinatorial optimization mappings differentiable by adding regularization and solving approximate problems.Combinatorial mappings otherwise have analytical derivatives that are zero almost everywhere.
  • Random perturbation methods construct smooth optimization mappings through implicit regularization induced by perturbations.
  • Surrogate-loss methods provide differentiable decision-quality objectives, including losses with Fisher consistency and risk bounds relating surrogate risk to regret risk.These losses can be computed and differentiated without solving the CO problem, thereby avoiding the zero-gradient problem.
  • The SPO framework applies to CO problems with cost parameters entering linearly, including LPs, QPs, ILPs, and MILPs.In ILP experiments, LP relaxations expedited training without significantly changing final regret, but the result may depend on the integrality gap.

Discussion

The survey summarizes gradient-based DFL techniques by their applicable CO problem form and gradient-computation method, while noting that most evaluations use linear-objective problems.

  • Table 1 organizes key gradient-based DFL techniques by applicable CO problem form and gradient-computation technique.Although some methods are broadly applicable, most have been evaluated on CO problems with linear objective functions.

3.2 Review of Gradient-Free DFL Methodologies

Gradient-free DFL methods avoid gradient-based training and use model classes or optimization formulations suited to direct regret minimization. Their benefits include convex or globally optimal training in restricted settings, alongside important scope limits.

  • Gradient-free DFL methods typically use tree-based or explicitly specified models, such as linear models, because they do not rely on gradient-based training.
  • For linear predictive models, the convex LSPO+ loss can be minimized with a convex solver without gradient-based training.
  • Decision trees and tree ensembles can be learned by recursive partitioning against regret or by posing tree learning as a MILP.
  • A MILP formulation for linear predictive models can produce globally optimal parameters, unlike gradient-based methods that may reach a local optimum.The method is limited to linear ML models and binary MILPs.
  • Coordinate-descent methods update cost-vector components using transition points, while divide-and-conquer extends coverage to bilinear objectives and substantially improves speed.

3.3 Other Aspects of Decision-Focused Learning

The survey discusses extensions and practical issues involving non-unique solutions, comparative performance, multiple tasks, uncertain constraints, robustness, stochastic optimization, and active learning.

  • DFL must account for multiple non-unique optimal solutions, which can arise when an LP cost vector is parallel to a feasible-polyhedron face.
  • Although DFL is expected to reduce regret, prediction-focused learning can asymptotically outperform integrated DFL when the underlying prediction model is well-specified.
  • Multi-task Decision-Focused Learning: Multi-task DFL uses either a shared output vector or shared layers with task-specific heads to train predictions across multiple tasks.Reported results show that both architectures can train models making effective predictions for multiple tasks.
  • Other directions include stochastic optimization, fair multiobjective optimization, robustness to label noise, and active learning for scarce labels.
  • Constraint Learning: Predicting parameters in constraints can produce decisions infeasible under the true parameters, making constraint uncertainty a major DFL challenge.Most DFL work instead predicts objective parameters while assuming the feasible space is known.
  • Constraint Learning: Gradient computation for constraint parameters is particularly difficult in combinatorial problems because feasible spaces are discrete and optimal solutions may have no active constraints.
  • Robustness: Poisoning attacks can affect DFL models, although repeatedly evaluating the optimization problem makes such attacks computationally expensive.

4. Applications of Decision-Focused Learning

DFL has been applied across diverse Predict-Then-Optimize applications, including computer vision, ranking, routing, maritime inspection, energy systems, and communications.

  • Fair Learning to Rank: DFL differentiates relevance prediction from fair-ranking optimization in learning-to-rank systems.The approach trains relevance prediction and fair ranking end to end, though solving the ranking optimization throughout training can be computationally demanding.
  • Route optimization: DFL supports shortest-path and vehicle-routing applications by predicting edge probabilities or travel times before optimization.Reported applications include wildlife-trafficking route prediction, last-mile delivery routing, and total-travel-time minimization.
  • Maritime transportation: In maritime transportation, Predict-Then-Optimize models select ships for inspection under limited personnel and multiple non-compliance categories.
  • Power and energy systems: DFL trains predictive models against downstream operating costs in renewable power scheduling and addresses port selection in wireless communication systems.The renewable-power application forecasts wind power for energy scheduling, while the communication application frames fluid-antenna port selection as a Predict-Then-Optimize problem.
  • Other applications: Other reviewed applications include differentiable surrogate optimization for nonlinear problems and computer-vision tasks involving ranking metrics and graph matching.

5. Experimental Evaluation on Benchmark Problemsets

The survey proposes benchmark test problems because the absence of a common benchmark has made comparisons among DFL techniques inconsistent.

  • The benchmark effort assembles publicly available datasets and test problems previously used in DFL research.

5.1 Problem Descriptions

The benchmark problemset covers Predict-Then-Optimize tasks with linear objective functions, including shortest paths, portfolios, and image-based decisions, using deliberately simple predictive models in several experiments.

  • All benchmark problems are Predict-Then-Optimize settings that combine prediction with constrained optimization, and their objective functions are linear.
  • Shortest path: The grid shortest-path benchmark moves across a 5 × 5 grid from southwest to northeast using 25 nodes and 40 edges.Its optimization formulation uses binary edge-selection variables and flow constraints to enforce a source-to-sink path.
  • Shortest path: The synthetic shortest-path experiment predicts 40-dimensional edge costs from five-dimensional features using controlled nonlinear misspecification and multiplicative noise.Five Deg settings are evaluated with noise-halfwidth ϑ = 0.5, training sets of 1000, and test sets of 10,000.
  • Portfolio optimization: The Markowitz benchmark predicts asset returns before maximizing portfolio value subject to a risk constraint and allocation constraints.Synthetic instances vary the nonlinearity parameter Deg across 1, 4, 8, and 16, with a linear predictive model.
  • Image and selection problems: The image-based benchmark predicts pixel costs to find minimum-cost paths through Warcraft II terrain maps, while another setup trains directly on optimal selections.The latter uses a linear predictive model and a negated inner-product task loss between prescribed and true selections, without assuming access to ground-truth parameters.

5.2 Experimental Results and Analysis

Across seven problems, the experiments show that no single DFL technique is uniformly best. Performance depends on problem structure, model specification, relaxation quality, and the trade-off between decision quality and training cost.

  • PF performs best when the predictive model is correctly specified, but misspecification can make DFL methods comparatively better.
  • Training-time results expose a scalability–quality trade-off: Listwise, Pairwise, Pairwise(diff), and MAP reduce training time by solving the optimization problem only occasionally.These methods use psolve = 5% and generally lie between PF and full DFL approaches in training time and quality.
  • No single DFL technique performs best across all experiments, with different methods excelling on different test problems.
  • SPO is consistently robust across test problems, although it does not outperform every competing technique.
  • I-MLE, FY, DBB, and QPTL underperform PF on portfolio optimization with quadratic constraints, where several methods were designed for linear constraints.SPO slightly outperforms PF in most portfolio cases, while LTR and MAP perform better than SPO for Deg 16.
  • QPTL performs strongly when the relaxed LP approximates the ILP well, but poorly when integrality relaxation changes the combinatorial solution substantially.This pattern favors QPTL in bipartite matching and knapsack, but not scheduling.

6. Future Research Directions

Future DFL research centers on extending the paradigm to broader optimization settings while improving theoretical reliability, risk sensitivity, scalability, and empirical validation. Key directions include multistage, multimodal, cross-task, nonlinear, and constraint-uncertainty settings.

  • Robust risk-sensitive DFL: Risk-sensitive DFL remains underdeveloped because most methods minimize expected regret rather than distributionally worst-case regret.Suggested alternatives include value-at-risk and min-max regret, drawing on robust optimization.
  • Scalable DFL: Scalable DFL requires clarifying the trade-off between solution-cache size, computational efficiency, surrogate accuracy, and solution quality.It remains unclear whether proxy solvers can reach regret levels comparable to traditional constrained-optimization solvers.
  • Theoretical guarantees: DFL methods need stronger theoretical guarantees, especially for combinatorial problems with nonlinear constraints.The survey reports that not all methods guarantee regret minimization and that some perform suboptimally with nonlinear constraints.
  • Uncertainty in the constraints: Future work should extend DFL to uncertainty in constraints, including risk-sensitive methods that preserve feasibility under extreme parameter variation.Constraint-parameter prediction is less explored than objective-parameter prediction, and forming solution caches for such methods is challenging.
  • Extending DFL to multistage settings: DFL should be evaluated in multistage decision processes and intermediate optimization layers embedded between neural networks.Examples include production and inventory decisions over multiple periods and Top-k patch selection for downstream image recognition.
  • Broader problem settings: Broader applicability also requires methods for multimodal datasets and nonlinear objective functions, whose parameters and structures are common in real-world problems.The survey identifies multimodal facility-location uncertainty and nonlinear combinatorial objectives as important extensions.

7. Conclusion

The survey positions Predict-Then-Optimize as a significant real-world problem setting and presents DFL as a comprehensive research overview. It synthesizes methods, applications, benchmarks, and open challenges, supported by evaluations of 11 techniques across diverse problem sets.

  • 7. Conclusion: Predict-Then-Optimize problems address real-world decisions by predicting unknown constrained-optimization parameters before making decisions.The survey highlights applications across artificial intelligence, operations research, and business analytics.
  • 7. Conclusion: The survey organizes DFL methods and explains two central challenges: differentiating through combinatorial solutions and the computational cost of optimization during training.These challenges motivate the survey’s methodological overview and discussion of practical limitations.
  • 7. Conclusion: The empirical study compares 11 DFL techniques across different problem sets and complements the review with four application examples.The evaluated settings cover multiple DFL problem domains.
  • 7. Conclusion: The survey provides datasets, code, and future research directions intended to support broader application and methodological development of DFL.The authors frame these resources as a catalyst for research across diverse domains and contexts.

Appendix A. Results on All Problem Instances

Appendix A supplies boxplots for all problem instances, extending the selected-instance visualizations in the main text across seven benchmark problem families.

  • Appendix A. Results on All Problem Instances: Appendix A reports boxplots for all instances rather than only the selected instances shown in the main text.The appendix expands the main-text visualization coverage.
  • Appendix A. Results on All Problem Instances: The appendix includes results for grid shortest path, portfolio optimization, Warcraft shortest path, and energy-cost aware scheduling.These are among the problem families listed for the complete-instance boxplots.
  • Appendix A. Results on All Problem Instances: Additional complete-instance boxplots cover knapsack and diverse bipartite problems.The passage lists these problem families as part of the appendix’s expanded results.

Appendix B. Learning Curves

Appendix B examines learning curves for learning-to-rank losses on three scheduling instances. Pairwise (diff) ranking loss is stable, whereas Listwise and Pairwise ranking losses do not stabilize.

  • Appendix B. Learning Curves: The appendix presents learning curves for learning-to-rank loss functions on three scheduling instances.The curves are used to compare training behavior across the ranking-loss variants.
  • Appendix B. Learning Curves: Pairwise (diff) ranking loss produces stable learning curves across the scheduling instances.The passage specifically identifies this loss as stable during learning.
  • Appendix B. Learning Curves: Listwise and Pairwise ranking losses do not stabilize in the reported scheduling experiments.Their learning behavior contrasts with that of Pairwise (diff).

Appendix C. Details about Hyperparameter Configuration

The appendix reports comparative benchmark figures and learning curves, while documenting that experiment hyperparameters were selected by grid search and released for reproducibility.

  • Hyperparameter configuration: Grid search selected the hyperparameters for each methodology in every experiment.The optimal combinations are provided in the repository for reproducibility.
  • Comparative evaluations: The synthetic shortest path evaluation reports distributions of relative regrets at noise-halfwidth ϑ = 0.5.
  • Comparative evaluations: The synthetic portfolio evaluation reports distributions of absolute regrets at noise magnitude ϑ = 1.
  • Comparative evaluations: Comparative evaluations on Warcraft shortest path, energy scheduling, knapsack, and diverse bipartite matching report distributions of relative regrets.
  • Comparative evaluations: Subset selection evaluations report distributions of mismatch rates.
  • Learning curves: Additional learning curves are reported for energy scheduling LTR losses and the diverse bipartite matching problem.
Loading 2307.13565v4…