Source-linked AI summary
MIPaaL: Mixed Integer Program as a Layer
Aaron Ferber, Bryan Wilder, Bistra Dilkina, Milind Tambe
TL;DR
The paper addresses the gap between prediction accuracy and decision quality for decision-making problems represented as MIPs. It introduces MIPaaL, which differentiates through an exact cutting-plane-based continuous surrogate, and reports higher decision quality than separate prediction-and-prescription baselines and LP-relaxation learning.
Problem
Decision-focused learning had mainly addressed limited optimization classes, while many practical decision problems require mixed-integer models with discrete and continuous variables.
Method
MIPaaL integrates a MIP as a differentiable neural-network layer by generating an equivalent continuous optimization problem through cutting planes.
Results
MIPaaL achieves uniformly higher decision quality than baselines, including more than 2x the average portfolio return of TwoStage or RootLP and 40.3% more successful bipartite matches.
Takeaways & Limitations
Integrating the full combinatorial problem into training improves decision quality across portfolio optimization and bipartite matching settings.
Abstract
from arXiv · showhide
Machine learning components commonly appear in larger decision-making pipelines; however, the model training process typically focuses only on a loss that measures accuracy between predicted values and ground truth values. Decision-focused learning explicitly integrates the downstream decision problem when training the predictive model, in order to optimize the quality of decisions induced by the predictions. It has been successfully applied to several limited combinatorial problem classes, such as those that can be expressed as linear programs (LP), and submodular optimization. However, these previous applications have uniformly focused on problems from specific classes with simple constraints. Here, we enable decision-focused learning for the broad class of problems that can be encoded as a Mixed Integer Linear Program (MIP), hence supporting arbitrary linear constraints over discrete and continuous variables. We show how to differentiate through a MIP by employing a cutting planes solution approach, which is an exact algorithm that iteratively adds constraints to a continuous relaxation of the problem until an integral solution is found. We evaluate our new end-to-end approach on several real world domains and show that it outperforms the standard two phase approaches that treat prediction and prescription separately, as well as a baseline approach of simply applying decision-focused learning to the LP relaxation of the MIP.
1 Introduction
Decision-focused learning trains predictive models to improve downstream decision quality rather than prediction accuracy alone. MIPaaL targets Mixed Integer Programs, motivated by their flexibility and use across real-world applications.
- Standard training losses can prioritize outliers or feature-space regions that downstream decisions never use.Practitioners may also require predictions to satisfy semantically meaningful objectives such as fairness.
- MIPs support flexible, interpretable formulations across applications including electrical-grid load control, RNA prediction, and industrial optimization.Their flexibility also allows them to capture computationally hard problems.
- Decision-focused learning incorporates the downstream optimization problem into model training to improve the quality of induced decisions.A central challenge is passing gradients back through the optimal decision so the predictive model can adjust its weights.
- MIPaaL improves solution quality over a baseline in portfolio optimization and bipartite matching with diversity constraints.The evaluation covers two real-world MIP problem domains.
2 Problem description
The paper studies learning settings where a predictive model estimates unknown MIP objective coefficients from features, and training directly targets the quality of the resulting MIP solution.
- Each instance consists of features φ, objective coefficients c, and known downstream data D containing MIP constraint information.The predictive model estimates c from φ while D supplies additional optimization data.
- The model fθ predicts objective coefficients, and the paper seeks parameters that maximize expected MIP-solution quality rather than minimize coefficient-prediction error alone.The standard two-stage approach instead trains against a loss comparing predicted and ground-truth coefficients.
3 MIPaaL: Encoding MIP in a Neural Network
MIPaaL embeds a MIP solver as a neural-network layer whose inputs include predicted objective coefficients and feasibility parameters. It enables differentiation by replacing the MIP with an equivalent continuous problem generated through cutting planes.
- The neural-network layer takes predicted objective coefficients and outputs the optimal MIP solution under linear constraints and integrality requirements.A forward pass can use any solver with objective coefficients and MIP feasibility parameters.
- The MIP’s discrete, highly nonconvex structure makes straightforward backward-pass gradient computation difficult.Forward propagation is straightforward, but the discrete structure hinders direct differentiation.
- MIPaaL uses a pure cutting-plane approach that generates an equivalent continuous optimization problem while preserving the optimal integral solution.The method is exact but may generate exponentially many cuts.
- The cutting-plane algorithm repeatedly solves LP relaxations, adding cuts for fractional solutions until an integral optimum is found.Each cut removes the discovered fractional solution without removing feasible integral solutions.
- Gradients are obtained by differentiating KKT conditions of the resulting continuous problem, using quadratic smoothing to support backpropagation.The smoothing approach supplies strong convexity for the surrogate optimization problem.
4 Decision-Focused Learning with MIPaaL
Decision-focused training uses the MIPaaL layer to optimize decisions made from neural-network predictions rather than relying only on prediction error. Backpropagation updates the predictor through the continuous surrogate produced by the cutting-plane solver.
- Prediction error can produce poor practical decisions when metrics such as mean squared error or cross-entropy are misaligned with solution quality.The training objective therefore incorporates the downstream task.
- MIPaaL computes a forward pass with the neural predictor and cutting-plane solver to generate the LP corresponding to the original MIP.The predictor estimates objective coefficients from embeddings of decision-variable components.
- Neural-network parameters are trained by backpropagating through the surrogate LP using KKT conditions and a small quadratic regularization term.The regularization enforces strong convexity and enables differentiation through the surrogate layer.
5 Empirical Evaluation
MIPaaL is evaluated on portfolio optimization and diverse bipartite matching against TwoStage and RootLP baselines. Across these settings, exact MIPaaL improves deployment decision quality, including when conventional prediction metrics are worse.
- Experimental settings: Experiments cover combinatorial portfolio optimization with cardinality and rebalancing constraints and bipartite matching with diversity constraints.The portfolio tasks use SP500 and DAX data, while matching uses citation-network instances with added diversity bounds.
- Decision quality: MIPaaL tends to outperform the other methods across individual problem settings, while early cut stopping can underperform RootLP.The comparison is reported for both portfolio optimization settings and diverse matching.
- Ablation and constraints: In diverse matching, early-cut decision-focused methods perform comparably to TwoStage, whereas exact MIPaaL retains gains after diversity constraints break LP-relaxation integrality.This contrasts the exact layer with methods that stop cut generation early.
- Prediction versus decisions: MIPaaL can achieve better deployment quality despite worse MSE, because it focuses predictions on highly profitable assets rather than approximating all coefficients equally.The reported prediction behavior explains why standard predictive metrics can diverge from decision quality.
- Prediction versus decisions: For matching, TwoStage can have better test Cross-Entropy while MIPaaL has better AUC, indicating that training losses and decision-relevant prediction behavior can differ.The result is reported alongside the observation that MIPaaL predictions may sometimes also be accurate in a traditional sense.
- Transfer learning: MIPaaL improves portfolio transfer performance across time periods, asset sets, countries, and problem sizes, although gains are smaller than when trained directly for the target task.On SP-30b, it gives more than double the improvement over TwoStage and a 59% improvement over RootLP; it also improves over both baselines on DAX.
6 Related Work
Prior work embeds optimization in neural networks for restricted problem classes, while MIPaaL extends differentiable optimization to flexible Mixed Integer Programs with exact decision-quality feedback.
- Earlier work also reframed heuristic components inside exact MIP solvers as machine-learning tasks, including learning in branch and bound.
- Optimization layers have been developed for quadratic programs, linear programs, zero-sum games, submodular optimization, and semidefinite relaxations.
- MIPaaL is presented as the first neural-network approach for flexible Mixed Integer Programs that provides exact feedback on decision quality.
7 Conclusion
MIPaaL incorporates Mixed Integer Programs as differentiable neural-network layers using cutting planes and improves decision quality over separated prediction-and-decision training and continuous-relaxation baselines.
- MIPaaL differentiates through flexible, discrete, potentially inapproximable MIPs by generating equivalent continuous optimization problems with cutting planes.
- The method trains predictive models with losses directly corresponding to downstream decision quality.
- Across portfolio optimization and diverse bipartite matching, MIPaaL outperforms decoupled prediction-and-decision training and continuous-relaxation approaches.
A.1 Data specification
The portfolio experiments use historical market data, temporal train-validation-test splits, 11 trading indicators, and evaluations on both the SP500 and DAX.
- Portfolio data come from historical price and volume records in the Quandl WIKI dataset.
- The temporal split uses 72 training periods, 35 validation periods, and 36 testing periods from January 2005 through November 2016.
- The model uses 11 features consisting of historical price averages and return rates over multiple time horizons.
- Experiments evaluate generality on the SP500 and DAX market indices.
- The SP-30a, SP-30b, SP-50, SP-100, and SP-200 settings specify concrete asset-index groups for portfolio experiments.
A.2 Optimization model
The portfolio optimization model selects final asset weights while balancing target similarity and transaction costs under sector, cardinality, and trading constraints.
- The experiments set sector deviation to 0.1 and ticket and name budgets to half the securities considered, preserving a non-empty feasible region.
- Inputs include assets, sectors, ticket and name limits, expected returns, trading volumes, sector membership, and initial and target weights.
- The model seeks final portfolio weights close to a target while controlling execution cost, sector exposure, cardinality, trading limits, and total weight.
- Decision variables include final weights, auxiliary absolute-deviation variables, sector-change variables, and binary indicators for used or reweighted assets.
- The objective maximizes the final portfolio-weight expression subject to budget, deviation, and transaction constraints.
- The formulation has |S| + 6n continuous variables, |2n| binary variables, and 10n + |2S| + 4 constraints.
B.1 Data specification
The experiments use bipartite matching instances derived from the CORA citation network, with diversity constraints based on papers’ fields of study.
- The matching data comes from the CORA citation network, whose nodes and edges represent publications and citations.
- The full network has 2708 nodes partitioned into 27 matching instances, each containing 50 nodes on each side of a complete bipartite graph.
- Each instance requires at least 25% of suggested pairings to involve distinct fields and at least 25% of suggested citations to involve the same field.
- Edge weights indicate whether one paper cites another, while node features are binary indicators for words from a 1433-word lexicon.
B.2 Optimization model
The optimization model matches nodes under one-to-one and field-composition constraints, using predicted edge weights as objective coefficients.
- The model matches nodes from two sets while limiting each node to at most one match.
- It imposes minimum proportions for selected edges connecting nodes within the same field and across different fields.
- The formulation contains |N1| × |N2| decision variables and |N1| + |N2| + 2 constraints.
- The experiments set both field-composition parameters to p = q = 0.25 to avoid overly easy problems while retaining feasible regions.