A Solver-Free Training Method for Predict-then-Optimize

We propose a scalable method for training prediction (machine learning) models in the predict-then-optimize paradigm, where model outputs serve as coefficients for a subsequent linear optimization task. Directly minimizing the empirical decision regret is intractable for linear programming and combinatorial optimization since the decision mapping is piecewise constant, and the gradients are zero almost everywhere. While existing methods address this by smoothing the differentiation process, they suffer from scalability issues, since a computationally expensive solver call is required for every gradient evaluation. To address this, we propose a decision-focused learning pipeline based on a measure transformation principle, which yields a new surrogate loss that is completely optimization-solver-free during training. We establish theoretical guarantees, including Fisher consistency and excess risk bounds. Empirically, our method achieves decision quality competitive with state-of-the-art methods while reducing training time by orders of magnitude.

We study predict-then-optimize problems, where a machine-learning model first predicts uncertain quantities, and those predictions are then used to make an optimization-based decision, such as choosing a route, portfolio, or knapsack solution. Standard prediction losses can be misaligned with the final decision goal, while existing decision-focused methods often require repeatedly calling an optimization solver during training, which can be very slow and not scalable. To address this, we propose a solver-free training loss called WISE. Its key idea is to use two geometric facts about our decision-making problem: decisions depend mainly on the direction of the prediction, and mistakes on more important or higher-impact examples should receive more attention during training. WISE reweights and normalizes the training target to reflect these facts, while remaining easy to optimize with standard machine-learning tools. We showed that our method has theoretical guarantees and worked well in simulated experiments.