249 citations · 790 across the 59 of their papers we have counts for
30 papers · 1 filter
Predictive Dual Smoothing for Column Generation
Senne Berden, Noah Schutte, Andrea Lodi +1
Solving large-scale linear programs efficiently is an important challenge in many optimization settings. A key technique is column generation, which alternates between solving the…
An improved column-generation-based matheuristic for learning classification trees
Krunal Kishor Patel, Guy Desaulniers, Andrea Lodi
Decision trees are highly interpretable models for solving classification problems in machine learning (ML). The standard ML algorithms for training decision trees are fast but gen…
Learning to Compare Nodes in Branch and Bound with Graph Neural Networks
Abdel Ghani Labassi, Didier Chételat, Andrea Lodi
Branch-and-bound approaches in integer programming require ordering portions of the space to explore next, a problem known as node comparison. We propose a new siamese graph neural…
Explainable prediction of Qcodes for NOTAMs using column generation
Krunal Kishor Patel, Guy Desaulniers, Andrea Lodi +1
A NOtice To AirMen (NOTAM) contains important flight route related information. To search and filter them, NOTAMs are grouped into categories called QCodes. In this paper, we devel…
Deep Neural Networks pruning via the Structured Perspective Regularization
Matteo Cacciola, Antonio Frangioni, Xinlin Li +1
In Machine Learning, Artificial Neural Networks (ANNs) are a very powerful tool, broadly used in many applications. Often, the selected (deep) architectures include many layers, an…
Lookback for Learning to Branch
Prateek Gupta, Elias B. Khalil, Didier Chetélat +4
The expressive and computationally inexpensive bipartite Graph Neural Networks (GNN) have been shown to be an important component of deep learning based Mixed-Integer Linear Progra…
MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers
Elias B. Khalil, Christopher Morris, Andrea Lodi
Mixed-integer programming (MIP) technology offers a generic way of formulating and solving combinatorial optimization problems. While generally reliable, state-of-the-art MIP solve…
Learning to branch with Tree MDPs
Lara Scavuzzo, Feng Yang Chen, Didier Chételat +4
State-of-the-art Mixed Integer Linear Program (MILP) solvers combine systematic tree search with a plethora of hard-coded heuristics, such as the branching rule. The idea of learni…
The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights
Maxime Gasse, Quentin Cappart, Jonas Charfreitag +38
Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolatio…
Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning
Sanae Lotfi, Tiphaine Bonniot de Ruisselet, Dominique Orban +1
In this paper, we consider both first- and second-order techniques to address continuous optimization problems arising in machine learning. In the first-order case, we propose a fr…
Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problems
Luca Accorsi, Andrea Lodi, Daniele Vigo
Despite the extensive research efforts and the remarkable results obtained on Vehicle Routing Problems (VRP) by using algorithms proposed by the Machine Learning community that are…
Ecole: A Library for Learning Inside MILP Solvers
Antoine Prouvost, Justin Dumouchelle, Maxime Gasse +2
In this paper we describe Ecole (Extensible Combinatorial Optimization Learning Environments), a library to facilitate integration of machine learning in combinatorial optimization…
Learning to Schedule Heuristics in Branch-and-Bound
Antonia Chmiela, Elias B. Khalil, Ambros Gleixner +2
Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world…
Predicting the probability distribution of bus travel time to move towards reliable planning of public transport services
Léa Ricard, Guy Desaulniers, Andrea Lodi +1
An important aspect of the quality of a public transport service is its reliability, which is defined as the invariability of the service attributes. Preventive measures taken duri…
Combinatorial optimization and reasoning with graph neural networks
Quentin Cappart, Didier Chételat, Elias Khalil +3
Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolatio…
Assessing the Impact: Does an Improvement to a Revenue Management System Lead to an Improved Revenue?
Greta Laage, Emma Frejinger, Andrea Lodi +1
Airlines and other industries have been making use of sophisticated Revenue Management Systems to maximize revenue for decades. While improving the different components of these sy…
Stochastic Damped L-BFGS with Controlled Norm of the Hessian Approximation
Sanae Lotfi, Tiphaine Bonniot de Ruisselet, Dominique Orban +1
We propose a new stochastic variance-reduced damped L-BFGS algorithm, where we leverage estimates of bounds on the largest and smallest eigenvalues of the Hessian approximation to…
Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers
Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo +3
We present Ecole, a new library to simplify machine learning research for combinatorial optimization. Ecole exposes several key decision tasks arising in general-purpose combinator…
Change Point Detection by Cross-Entropy Maximization
Aurélien Serre, Didier Chételat, Andrea Lodi
Many offline unsupervised change point detection algorithms rely on minimizing a penalized sum of segment-wise costs. We extend this framework by proposing to minimize a sum of dis…
Hybrid Models for Learning to Branch
Prateek Gupta, Maxime Gasse, Elias B. Khalil +3
A recent Graph Neural Network (GNN) approach for learning to branch has been shown to successfully reduce the running time of branch-and-bound algorithms for Mixed Integer Linear P…
Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
Giulia Zarpellon, Jason Jo, Andrea Lodi +1
Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs). Learning branching policies for MILP has become an…
JANOS: An Integrated Predictive and Prescriptive Modeling Framework
David Bergman, Teng Huang, Philip Brooks +2
Business research practice is witnessing a surge in the integration of predictive modeling and prescriptive analysis. We describe a modeling framework JANOS that seamlessly integra…
Learning chordal extensions
Defeng Liu, Andrea Lodi, Mathieu Tanneau
A highly influential ingredient of many techniques designed to exploit sparsity in numerical optimization is the so-called chordal extension of a graph representation of the optimi…
Exact Combinatorial Optimization with Graph Convolutional Neural Networks
Maxime Gasse, Didier Chételat, Nicola Ferroni +2
Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose a new graph convolutional neural network model for learning branch-and-bound…