Andrea Lodi

Felipe Serrano

2019-12-01

ArXiv (preprint)

JANOS: An Integrated Predictive and Prescriptive Modeling Framework

David Bergman

Teng Huang

Philip A. Brooks

A. Raghunathan

Business research practice is witnessing a surge in the integration of predictive modeling and prescriptive analysis. We describe a modeling… (see more) 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.

2019-11-21

ArXiv (preprint)

Nonlinear chance-constrained problems with applications to hydro scheduling

Enrico Malaguti

Giacomo Nannicini

Dimitri Thomopulos

2019-11-14

Mathematical Programming (published)

Nash Games Among Stackelberg Leaders

Gabriele Dragotto

Felipe Feijoo

Sriram Sankaranarayanan

We analyze Nash games played among leaders of Stackelberg games (NASP). We show it is Σ p 2 - hard to decide if the game has a mixed-strate… (see more)gy Nash equilibrium (MNE), even when there are only two leaders and each leader has one follower. We provide a ﬁnite time algorithm with a running time bounded by O (2 2 n ) which computes MNEs for NASP when it exists and returns infeasibility if no MNE exists. We also provide two ways to improve the algorithm which involves constructing a series of inner approximations (alternatively, outer approximations) to the leaders’ feasible region that will provably obtain the required MNE. Finally, we test our algorithms on a range of NASPs arising out of a game in the energy market, where countries act as Stackelberg leaders who play a Nash game, and the domestic producers act as the followers.

2019-10-14

arXiv.org (preprint)

dblp.uni-trier.de

Exact Combinatorial Optimization with Graph Convolutional Neural Networks

Maxime Gasse

Didier Chételat

Nicola Ferroni

Laurent Charlin

Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose a new graph convolutional neural netw… (see more)ork model for learning branch-and-bound variable selection policies, which leverages the natural variable-constraint bipartite graph representation of mixed-integer linear programs. We train our model via imitation learning from the strong branching expert rule, and demonstrate on a series of hard problems that our approach produces policies that improve upon state-of-the-art machine-learning methods for branching and generalize to instances significantly larger than seen during training. Moreover, we improve for the first time over expert-designed branching rules implemented in a state-of-the-art solver on large problems. Code for reproducing all the experiments can be found at this https URL.

2019-01-01

NeurIPS (published)

Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information

Eric P. Larsen

Sébastien Lachapelle

This paper offers a methodological contribution at the intersection of machine learning and operations research. Namely, we propose a method… (see more)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.

2018-07-31

ArXiv (preprint)

A polynomial algorithm for a continuous bilevel knapsack problem

Patrice Marcotte

2018-03-01

Operations Research Letters (published)

Existence of Nash Equilibria on Integer Programming Games

João Pedro Pedroso

2018-02-15

Springer Proceedings in Mathematics & Statistics (published)

Nash equilibria for integer programming games

João Pedro Pedroso

In this paper, we develop algorithmic approaches for a recently defined class of games, the integer programming games. Two general methods t… (see more)o approximate an equilibrium are presented and enhanced in order to improve their practical efficiency. Their performance is analysed through computational experiments in a knapsack game and a competitive lot-sizing game. To the best of our knowledge, this is the first time that equilibria computation methods for general integer programming games are build and computationally tested.

2018-01-01

(published)

www.semanticscholar.org

Nash equilibria in the two-player kidney exchange game

João Pedro Pedroso

Ana Luiza D'ávila Viana

2016-04-21

Mathematical Programming (published)

Experimental Algorithms

Samuel Rosat

Issmail ElHallaoui

François Soumis

2013-11-01

Lecture Notes in Computer Science (published)