1.1k citations · 1.4k across the 20 of their papers we have counts for
21 papers
Fast Matrix Multiplication Without Tears: A Constraint Programming Approach
Arnaud Deza, Chang Liu, Pashootan Vaezipoor +1
It is known that the multiplication of an matrix with an matrix can be performed using fewer multiplications than what the naive approach suggests.…
LEO: Learning Efficient Orderings for Multiobjective Binary Decision Diagrams
Rahul Patel, Elias B. Khalil
Approaches based on Binary decision diagrams (BDDs) have recently achieved state-of-the-art results for multiobjective integer programming problems. The variable ordering used in c…
LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations
Yudong Xu, Wenhao Li, Pashootan Vaezipoor +2
Can a Large Language Model (LLM) solve simple abstract reasoning problems? We explore this broad question through a systematic analysis of GPT on the Abstraction and Reasoning Corp…
Machine Learning for Cutting Planes in Integer Programming: A Survey
Arnaud Deza, Elias B. Khalil
We survey recent work on machine learning (ML) techniques for selecting cutting planes (or cuts) in mixed-integer linear programming (MILP). Despite the availability of various cla…
Walkability Optimization: Formulations, Algorithms, and a Case Study of Toronto
Weimin Huang, Elias B. Khalil
The concept of walkable urban development has gained increased attention due to its public health, economic, and environmental sustainability benefits. Unfortunately, land zoning a…
Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus
Yudong Xu, Elias B. Khalil, Scott Sanner
The Abstraction and Reasoning Corpus (ARC) aims at benchmarking the performance of general artificial intelligence algorithms. The ARC's focus on broad generalization and few-shot…
Multi-Task Predict-then-Optimize
Bo Tang, Elias B. Khalil
The predict-then-optimize framework arises in a wide variety of applications where the unknown cost coefficients of an optimization problem are first predicted based on contextual…
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…
PyEPO: A PyTorch-based End-to-End Predict-then-Optimize Library for Linear and Integer Programming
Bo Tang, Elias B. Khalil
In deterministic optimization, it is typically assumed that all problem parameters are fixed and known. In practice, however, some parameters may be a priori unknown but can be est…
A Deep Reinforcement Learning Framework For Column Generation
Cheng Chi, Amine Mohamed Aboussalah, Elias B. Khalil +2
Column Generation (CG) is an iterative algorithm for solving linear programs (LPs) with an extremely large number of variables (columns). CG is the workhorse for tackling large-sca…
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…
Neur2SP: Neural Two-Stage Stochastic Programming
Justin Dumouchelle, Rahul Patel, Elias B. Khalil +1
Stochastic Programming is a powerful modeling framework for decision-making under uncertainty. In this work, we tackle two-stage stochastic programs (2SPs), the most widely used cl…
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…
Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework
Elias B. Khalil, Pashootan Vaezipoor, Bistra Dilkina
In Mixed Integer Linear Programming (MIP), a (strong) backdoor is a "small" subset of an instance's integer variables with the following property: in a branch-and-bound procedure,…
Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
Mohammad Ali Alomrani, Reza Moravej, Elias B. Khalil
The challenge in the widely applicable online matching problem lies in making irrevocable assignments while there is uncertainty about future inputs. Most theoretically-grounded po…
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…
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…
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…
Combinatorial Attacks on Binarized Neural Networks
Elias B. Khalil, Amrita Gupta, Bistra Dilkina
Binarized Neural Networks (BNNs) have recently attracted significant interest due to their computational efficiency. Concurrently, it has been shown that neural networks may be ove…
Learning Combinatorial Optimization Algorithms over Graphs
Hanjun Dai, Elias B. Khalil, Yuyu Zhang +2
The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can…
Fake News Mitigation via Point Process Based Intervention
Mehrdad Farajtabar, Jiachen Yang, Xiaojing Ye +6
We propose the first multistage intervention framework that tackles fake news in social networks by combining reinforcement learning with a point process network activity model. Th…