Prescriptive Learning of Linear Policies with Feasibility Guarantees for Binary Decision-Making
Authors: Farzaneh Pourahmadi, Trine Krogh Boomsma, Pierre Pinson
Organizations: Department of Wind and Energy Systems, Technical University of Denmark. · Department of Mathematical Sciences, University of Copenhagen. · Dyson School of Design Engineering, Imperial College London.
Binary decision-making under uncertainty arises across a wide range of applications, including energy systems scheduling, transportation, and workforce planning. While machine learning has been increasingly applied to accelerate or replace mixed-integer solvers in such settings, existing approaches rely on predictive learning, training models to reproduce optimal decisions from labeled data, which lacks knowledge of counterfactual outcomes and provides no guarantees that the resulting decisions will be feasible. This limitation is further compounded under distributional shift, where policies trained on historical data may produce systematically infeasible decisions. We propose a prescriptive learning framework for binary decision-making that addresses both limitations. Rather than predicting optimal labels, the framework jointly optimizes over linear decision policies and feasible assignments across all training scenarios, allowing feasible alternatives and their operational performance to be considered directly during training. We further extend the framework to a distributionally robust chance-constrained formulation using a Wasserstein ambiguity set, which enforces feasibility with a prescribed probability under the worst-case distribution in the ambiguity set and enables a tunable trade-off between robustness and solution quality. We demonstrate the framework on two case studies, namely a unit commitment problem and a staff allocation problem. Out-of-sample experiments under test distributions that either match or differ from the training distribution show that the robust model is more conservative when the two distributions coincide, while under distributional shift it substantially reduces unmet demand and lowers total cost by up to 76.5% relative to classical predictive learning.
Figures & tables
Figure 1: Comparison of the classical and prescriptive linear policies for the illustrative example. The square markers represent the optimal binary decisions for the training samples, and the dashed horizontal line denotes the decision threshold at 0.5 . The classical policy is fitted solely to the optimal labels and may therefore prescribe infeasible decisions, whereas the prescriptive policy incorporates the original optimization constraints during training and preserves feasibility at the expense of some loss in optimality.
Figure 2: Learned linear policies under distribution shift. The classical predictive and prescriptive models both learn the constant policy π(θ)=1 because all training samples satisfy θ≤1 and therefore have optimal decision x∗=1 . Under the shifted test samples, these policies remain above the threshold and become infeasible when θ>1 . The distributionally robust policy shifts downward and prescribes x=0 for larger values of θ , improving feasibility under distribution shift.
Dataset
High
Medium
Low
Training, validation, close test
0.83
0.62
0.45
Far test
0.93
0.85
0.78
Noise ηt
U[−0.03,0.03]
U[−0.05,0.05]
U[−0.03,0.03]
Table 1: Scaling factors κ of the demand distributions ( 10 trajectories per level).
Figure 3: Demand forecast distributions for hour 18 across the three datasets. Wasserstein distances from the training set: W1(training,close test)=0.017 and W1(training,far test)=0.185 .
Figure 4: Out-of-sample results, totals over the 30 trajectories of each test set: production cost (comprising variable production, online, and start-up costs; top row), unmet demand (middle row), and total cost (bottom row). Left column: close test (same distribution as training). Right column: far test (distribution shift from training). The green dashed line is the hindsight benchmark.
Figure 5: Out-of-sample cost comparison for the staff allocation use case with S=100 training scenarios (means per test scenario). Costs are decomposed into staffing cost (top), unmet demand in employee-shifts per scenario (middle), and total cost (bottom) for the close test set, drawn from the same distribution as the training data, and the far test set, which reflects a high-demand distribution shift. The green dashed line indicates the hindsight benchmark.
Figure 6: Mean out-of-sample total cost of the staff allocation use case as a function of the number of training scenarios S , for the close test (left) and the far test (right). The green dashed line indicates the hindsight benchmark; the dotted line marks the far-test cost of the distributionally robust model trained on S=50 scenarios.
Mixed-Integer Linear Programming (MILP) decision engines routinely output nominally optimal plans for high-stakes industrial systems. Yet deployment rarely matches solve-time assumptions: small perturbations in costs, demands, or resource availability can invalidate feasibility or trigger discontinuous shifts to qualitatively different solutions. We argue that this post-solve robustness gap is a missing layer in today's optimization pipelines and a missing evaluation dimension for learning-enabled decision systems. Rather than replacing robust optimization or stochastic programming, the proposed layer audits a solved incumbent and returns solver-backed evidence about how far that solution can be trusted. We formalize two central objects: (i) an ε-near-optimal feasible neighborhood in parameter space, capturing when an incumbent remains feasible and near-optimal under perturbations, and (ii) solution smoothness in decision space, capturing whether nearby alternatives with small combinatorial edits remain competitive. We then synthesize the most relevant partial answers from sensitivity and stability analysis, robust optimization, neighborhood search, adversarial testing, and learning-based enhancements, and articulate an agenda for a unified post-solve robustness layer. Concretely, we call for certified inner approximations around the incumbent, probabilistic robustness estimation with calibrated uncertainty, adversarial robustness margins, and learning-based prediction and explanation aligned with solver-backed verification. We conclude with a compact reporting template and evaluation protocol that would make robustness a first-class output of decision engines.
Yi-Xiang Hu
University of Science and Technology of China, Hefei, China
Plugging predictions of unknown parameters into downstream optimization problems, often referred to as the ``predict-then-optimize'' paradigm, has long been a standard approach in decision-making under uncertainty. However, improved predictive accuracy does not, in general, translate into improved decision quality. This disconnect has motivated growing interest in decision-focused learning (DFL) within the operations research community. This tutorial reviews recent developments in DFL and highlights key methodological insights, with a particular focus on stochastic linear programming as the downstream decision-making problem. We discuss why several widely used tools in traditional statistical learning are not directly suited to decision-focused settings and must be rethought, including (i) data collection strategies driven purely by predictive uncertainty and (ii) distributional distance measures such as the Wasserstein distance. We summarize properties of DFL that distinguish it from conventional predictive modeling and provide insights into the development of new decision-focused tools.
Mo Liu
Department of Statistics and Operations Research, University of North Carolina at Chapel Hill
Decision-focused learning (DFL) trains predictors for downstream decision quality, but often relies on optimal reference decisions that are expensive to obtain. We present PolyStepOR, which trains directly from realized decision costs without pre-computed optima and extends to in-constraint predictions through repair or infeasibility penalties. To handle piecewise-constant losses, PolyStepOR perturbs predictor parameters, evaluates the resulting decisions, and uses optimal transport to favor lower-cost directions, requiring no derivatives. Without task-specific tuning, PolyStepOR performs strongly on classical optimization benchmarks and competitively on predicted-constraint and real-world problems. Theoretically, we characterize decision-preserving perturbations and boundary detection, bound sensitivity to cost errors, and establish stationarity guarantees for a smoothed objective. PolyStepOR thus replaces optimal reference decisions and derivatives with forward evaluations.
Viet The Nguyen, Gunther Gust, An Thai Le
University of Würzburg, Germany · Center for Artificial Intelligence and Data Science (CAIDAS), Germany · Center for AI Research, VinUniversity, Vietnam +1