Andrea Lodi

Guillaume Rabusseau

Airlines have been making use of highly complex Revenue Management Systems to maximize revenue for decades. Estimating the impact of changin… (see more)g one component of those systems on an important outcome such as revenue is crucial, yet very challenging. It is indeed the difference between the generated value and the value that would have been generated keeping business as usual, which is not observable. We provide a comprehensive overview of counterfactual prediction models and use them in an extensive computational study based on data from Air Canada to estimate such impact. We focus on predicting the counterfactual revenue and compare it to the observed revenue subject to the impact. Our microeconomic application and small expected treatment impact stand out from the usual synthetic control applications. We present accurate linear and deep-learning counterfactual prediction models which achieve respectively 1.1% and 1% of error and allow to estimate a simulated effect quite accurately.

2021-01-01

arXiv.org (preprint)

dblp.uni-trier.de

Multilevel Approaches for the Critical Node Problem

Andrea Baggio

Andrea Tramontani

2021-01-01

Operational Research (published)

The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights

Maxime Gasse

Simon Bowly

Quentin Cappart

Jonas Charfreitag

Laurent Charlin

Didier Chételat

Antonia Chmiela

Justin Dumouchelle

Ambros Gleixner

Aleksandr Kazachkov

Elias Boutros Khalil

Paweł Lichocki

Miles Lubin

Chris J. Maddison

Christopher Morris

D. Papageorgiou

Augustin Parjadis

Sebastian Pokutta

Antoine Prouvost … (see 22 more)

Lara Scavuzzo

Giulia Zarpellon

Linxin Yangm

Sha Lai

Akang Wang

Xiaodong Luo

Xiang Zhou

Haohan Huang

Sheng Cheng Shao

Yuanming Zhu

Dong Dong Zhang

Tao Manh Quan

Zixuan Cao

Yang Xu

Zhewei Huang

Shuchang Zhou

C. Binbin

He Minggui

Haoren Ren Hao

Zhang Zhiyu

An Zhiwu

Mao Kun

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused … (see more)on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning as a new approach for solving combinatorial problems, either directly as solvers or by enhancing exact solvers. Based on this context, the ML4CO aims at improving state-of-the-art combinatorial optimization solvers by replacing key heuristic components. The competition featured three challenging tasks: finding the best feasible solution, producing the tightest optimality certificate, and giving an appropriate solver configuration. Three realistic datasets were considered: balanced item placement, workload apportionment, and maritime inventory routing. This last dataset was kept anonymous for the contestants.

2021-01-01

NeurIPS (Competition and Demos) (published)

BDD-based optimization for the quadratic stable set problem

Jaime E. González

Andr'e Augusto Cire

Louis-Martin Rousseau

2020-08-01

Discrete Optimization (published)

BDD-based optimization for the quadratic stable set problem

Jaime E. González

Andr'e Augusto Cire

Louis-Martin Rousseau

2020-08-01

Discrete Optimization (published)

Multi-agent Assortment Optimization in Sequential Matching Markets

Alfredo Torrico

2020-06-08

ArXiv (preprint)

Provable Guarantees for General Two-sided Sequential Matching Markets

Alfredo Torrico

Two-sided markets have become increasingly more important during the last years, mostly because of their numerous applications in housing, l… (see more)abor and dating. Consumer-supplier matching platforms pose several technical challenges, specially due to the trade-off between recommending suitable suppliers to consumers and avoiding collisions among consumers' preferences. In this work, we study a general version of the two-sided sequential matching model introduced by Ashlagi et al. (2019). The setting is the following: we (the platform) offer a menu of suppliers to each consumer. Then, every consumer selects, simultaneously and independently, to match with a supplier or to remain unmatched. Suppliers observe the subset of consumers that selected them, and choose either to match a consumer or leave the system. Finally, a match takes place if both the consumer and the supplier sequentially select each other. Each agent's behavior is probabilistic and determined by a regular discrete choice model. Our objective is to choose an assortment family that maximizes the expected cardinality of the matching. Given the computational complexity of the problem, we show several provable guarantees for the general model, which in particular, significantly improve the approximation factors previously obtained.

2020-06-08

arXiv.org (preprint)

dblp.uni-trier.de

On generalized surrogate duality in mixed-integer nonlinear programming

Benjamin Muller

Gonzalo Munoz

Maxime Gasse

Ambros Gleixner

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)