Andrea Lodi

Daniele Vigo

2022-03-01

Operations Research Letters (publié)

JANOS: An Integrated Predictive and Prescriptive Modeling Framework

David Bergman

Teng Huang

Philip Brooks

Arvind U. Raghunathan

Business research practice is witnessing a surge in the integration of predictive modeling and prescriptive analysis. We describe a modeling… (voir plus) framework JANOS that seamlessly integrates the two streams of analytics, allowing researchers and practitioners to embed machine learning models in an end-to-end optimization framework. JANOS allows for specifying a prescriptive model using standard optimization modeling elements such as constraints and variables. The key novelty lies in providing modeling constructs that enable the specification of commonly used predictive models within an optimization model, have the features of the predictive model as variables in the optimization model, and incorporate the output of the predictive models as part of the objective. The framework considers two sets of decision variables: regular and predicted. The relationship between the regular and the predicted variables is specified by the user as pretrained predictive models. JANOS currently supports linear regression, logistic regression, and neural network with rectified linear activation functions. In this paper, we demonstrate the flexibility of the framework through an example on scholarship allocation in a student enrollment problem and provide a numeric performance evaluation. Summary of Contribution. This paper describes a new software tool, JANOS, that integrates predictive modeling and discrete optimization to assist decision making. Specifically, the proposed solver takes as input user-specified pretrained predictive models and formulates optimization models directly over those predictive models by embedding them within an optimization model through linear transformations.

2022-03-01

INFORMS Journal on Computing (publié)

Single Allocation Hub Location with Heterogeneous Economies of Scale

Borzou Rostami

Masoud Chitsaz

Okan Arslan

Gilbert Laporte

2022-03-01

Operations Research (publié)

Computing Nash equilibria for integer programming games

João Pedro Pedroso

2022-01-01

European Journal of Operational Research (publié)

A Learning Metaheuristic Algorithm for a Scheduling Application

Nazgol Niroumandrad

Nadia Lahrichi

2022-01-01

Modeling, Identification and Control (publié)

Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information

Eric Larsen

Sébastien Lachapelle

This paper offers a methodological contribution at the intersection of machine learning and operations research. Namely, we propose a method… (voir plus)ology to quickly predict expected tactical descriptions of operational solutions (TDOSs). The problem we address occurs in the context of two-stage stochastic programming, where the second stage is demanding computationally. We aim to predict at a high speed the expected TDOS associated with the second-stage problem, conditionally on the first-stage variables. This may be used in support of the solution to the overall two-stage problem by avoiding the online generation of multiple second-stage scenarios and solutions. We formulate the tactical prediction problem as a stochastic optimal prediction program, whose solution we approximate with supervised machine learning. The training data set consists of a large number of deterministic operational problems generated by controlled probabilistic sampling. The labels are computed based on solutions to these problems (solved independently and offline), employing appropriate aggregation and subselection methods to address uncertainty. Results on our motivating application on load planning for rail transportation show that deep learning models produce accurate predictions in very short computing time (milliseconds or less). The predictive accuracy is close to the lower bounds calculated based on sample average approximation of the stochastic prediction programs.

2022-01-01

INFORMS Journal on Computing (publié)

Single Allocation Hub Location with Heterogeneous Economies of Scale

Borzou Rostami

Masoud Chitsaz

Okan Arslan

Gilbert Laporte

The economies of scale in hub location is usually modeled by a constant parameter, which captures the benefits companies obtain through cons… (voir plus)olidation. In their article “Single allocation hub location with heterogeneous economies of scale,” Rostami et al. relax this assumption and consider hub-hub connection costs as piecewise linear functions of the flow amounts. This spoils the triangular inequality property of the distance matrix, making the classical flow-based model invalid and further complicates the problem. The authors tackle the challenge by building a mixed-integer quadratically constrained program and by developing a methodology based on constructing Lagrangian function, linear dual functions, and specialized polynomial-time algorithms to generate enhanced cuts. The developed method offers a new strategy in Benders-type decomposition through relaxing a set of complicating constraints in subproblems when such relaxation is tight. The results confirm the efficacy of the solution methods in solving large-scale problem instances.

2021-12-28

Operational Research (published)

ZERO: Playing Mathematical Programming Games

Gabriele Dragotto

S. Sankaranarayanan

2021-11-15

ArXiv (prépublication)

The Cut and Play Algorithm: Computing Nash Equilibria via Outer Approximations

Gabriele Dragotto

Sriram Sankaranarayanan

We introduce the Cut-and-Play, an efficient algorithm for computing equilibria in simultaneous non-cooperative games where players solve non… (voir plus)convex and possibly unbounded optimization problems. Our algorithm exploits an intrinsic relationship between the equilibria of the original nonconvex game and the ones of a convexified counterpart. In practice, Cut-and-Play formulates a series of convex approximations of the original game and refines them with techniques from integer programming, for instance, cutting planes and branching operations. We test our algorithm on two families of challenging nonconvex games involving discrete decisions and bilevel programs, and we empirically demonstrate that it efficiently computes equilibria and outperforms existing game-specific algorithms.

2021-11-10

ArXiv (prépublication)

Capacity Planning in Stable Matching

Federico Bobbio

Ignacio Rios

Alfredo Torrico

We introduce the problem of jointly increasing school capacities and finding a student-optimal assignment in the expanded market. Due to the… (voir plus) impossibility of efficiently solving the problem with classical methods, we generalize existent mathematical programming formulations of stability constraints to our setting, most of which result in integer quadratically-constrained programs. In addition, we propose a novel mixed-integer linear programming formulation that is exponentially large on the problem size. We show that its stability constraints can be separated by exploiting the objective function, leading to an effective cutting-plane algorithm. We conclude the theoretical analysis of the problem by discussing some mechanism properties. On the computational side, we evaluate the performance of our approaches in a detailed study, and we find that our cutting-plane method outperforms our generalization of existing mixed-integer approaches. We also propose two heuristics that are effective for large instances of the problem. Finally, we use the Chilean school choice system data to demonstrate the impact of capacity planning under stability conditions. Our results show that each additional seat can benefit multiple students and that we can effectively target the assignment of previously unassigned students or improve the assignment of several students through improvement chains. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.

2021-10-02

ArXiv (prépublication)

Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problems

Luca Accorsi

Daniele Vigo

2021-09-28

ArXiv (preprint)

On the estimation of discrete choice models to capture irrational customer behaviors

Sanjay Dominik Jena

Claudio Sole

The random utility maximization model is by far the most adopted framework to estimate consumer choice behavior. However, behavioral economi… (voir plus)cs has provided strong empirical evidence of irrational choice behaviors, such as halo effects, that are incompatible with this framework. Models belonging to the random utility maximization family may therefore not accurately capture such irrational behavior. Hence, more general choice models, overcoming such limitations, have been proposed. However, the flexibility of such models comes at the price of increased risk of overfitting. As such, estimating such models remains a challenge. In this work, we propose an estimation method for the recently proposed generalized stochastic preference choice model, which subsumes the family of random utility maximization models and is capable of capturing halo effects. In particular, we propose a column-generation method to gradually refine the discrete choice model based on partially ranked preference sequences. Extensive computational experiments indicate that our model, explicitly accounting for irrational preferences, can significantly boost the predictive accuracy on both synthetic and real-world data instances. Summary of Contribution: In this work, we propose an estimation method for the recently proposed generalized stochastic preference choice model, which subsumes the family of random utility maximization models and is capable of capturing halo effects. Specifically, we show how to use partially ranked preferences to efficiently model rational and irrational customer types from transaction data. Our estimation procedure is based on column generation, where relevant customer types are efficiently extracted by expanding a treelike data structure containing the customer behaviors. Furthermore, we propose a new dominance rule among customer types whose effect is to prioritize low orders of interactions among products. An extensive set of experiments assesses the predictive accuracy of the proposed approach by comparing it against rank-based methods with only rational preferences and with more general benchmarks from the literature. Our results show that accounting for irrational preferences can boost predictive accuracy by 12.5% on average when tested on a real-world data set from a large chain of grocery and drug stores.

2021-09-08

ArXiv (preprint)