We address the contextual bandit problem for high-dimensional combinatorial action spaces involving a class of structured discrete constrained optimization problems. In this setting, key quantities within the optimization formulation, such as performance indicators contributing to the objective or constraints, must be estimated from data during the trial sequence of optimized actions. These problems frequently arise in the many operations management domains including IT resource allocation and retail assortment price optimization. We propose a novel, practical, and transparent approach based on general-purpose regression oracles, leveraging Inverse Gap Weighting (IGW) for seamless integration within an optimization framework. IGW sampling is efficiently managed by: (a) a column generation reformulation of the underlying Mixed Integer Programming (MIP) model which allows for flexible lower-level predictors, causal coherence, and efficient representation of large action spaces;(b) a diverse solution pool generation to balance the exploration-exploitation trade-off in large action spaces. To address non-smoothness in the reward function due to optimization constraints, we incorporate a risk-averse phased learning strategy. We validate our approach on a real-world auto-scaling problem in IT automation, achieving a significant reduction in cumulative regret through skillful exploration, with additional gains from risk-averse methods that effectively manage constraint violations.

There has been a surge of interest in learning optimal decision trees using mixed-integer programs (MIP) in recent years, as heuristic-based methods do not guarantee optimality and find it challenging to incorporate constraints that are critical for many practical applications. However, existing MIP methods that build on an arc-based formulation do not scale well as the number of binary variables is in the order of 2 to the power of the depth of the tree and the size of the dataset. Moreover, they can only handle sample-level constraints and linear metrics. In this paper, we propose a novel path-based MIP formulation where the number of decision variables is independent of dataset size. We present a scalable column generation framework to solve the MIP. Our framework produces a multiway-split tree which is more interpretable than the typical binary-split trees due to its shorter rules. Our framework is more general as it can handle nonlinear metrics such as F1 score, and incorporate a broader class of constraints. We demonstrate its efficacy with extensive experiments. We present results on datasets containing up to 1,008,372 samples while existing MIP-based decision tree models do not scale well on data beyond a few thousand points. We report superior or competitive results compared to the state-of-art MIP-based methods with up to a 24X reduction in runtime.

With the abundance of available data, many enterprises seek to implement data-driven prescriptive analytics to help them make informed decisions. These prescriptive policies need to satisfy operational constraints, and proactively eliminate rule conflicts, both of which are ubiquitous in practice. It is also desirable for them to be simple and interpretable, so they can be easily verified and implemented. Existing approaches from the literature center around constructing variants of prescriptive decision trees to generate interpretable policies. However, none of the existing methods is able to handle constraints. In this paper, we propose a scalable method that solves the constrained prescriptive policy generation problem. We introduce a novel path-based mixed-integer program (MIP) formulation which identifies a (near) optimal policy efficiently via column generation. The policy generated can be represented as a multiway-split tree which is more interpretable and informative than binary-split trees due to its shorter rules. We demonstrate the efficacy of our method with extensive computational experiments on both synthetic and real datasets.

We present a new deflected subgradient scheme for generating good quality dual solutions for linear programming (LP) problems and utilize this within the context of large-scale airline crew planning problems that arise in practice. The motivation for the development of this method came from the failure of a black-box-type approach implemented at United Airlines for solving such problems using column generation in concert with a commercial LP solver, where the software was observed to stall while yet remote from optimality. We identify a phenomenon called dual noise to explain this stalling behavior and present an analysis of the desirable properties of dual solutions in this context. The proposed deflected subgradient approach has been embedded within the crew pairing solver at United Airlines and tested using historical data sets. Our computational experience suggests a strong correlation between the dual noise phenomenon and the quality of the final solution produced, as well as with the accompanying algorithmic performance. Although we observed that our deflected subgradient scheme yielded an average speed-up factor of 10 for the column generation scheme over the commercial solver, the average reduction in the optimality gap over the same number of iterations was better by a factor of 26, along with an average reduction in the dual noise by a factor of 30. The results from the column generation implementation suggest that significant benefits can be obtained by using the deflected subgradient-based scheme instead of a black-box-type or standard solver approach to solve the intermediate linear programs that arise within the column generation scheme.

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issue of network vulnerability by prescribing alternate routes for traffic flows. Applications include the dispatching of duplicate packets of data to improve the reliability in communication networks and the diverting of traffic during congestion to reduce the chances of bottlenecks in transportation networks, in the presence of time-dependent variations in travel delays in the network. We prove that this problem, and many variations of it, are NP-hard and we develop a 0–1 linear programming model that can be used to solve this problem. This model can accommodate various degrees of disjointedness of the pair of paths, from complete to partial with respect to specific arcs. We also present some computational results obtained by solving the above models using CPLEX-MIP. © 1998 John Wiley & Sons, Inc. Networks 31: 259–272, 1998