Portrait de Behrouz Babaki n'est pas disponible

Behrouz Babaki

Alumni

Publications

COIL: A Deep Architecture for Column Generation
Behrouz Babaki
Laurent Charlin
Sanjay Dominik Jena
. Column generation is a popular method to solve large-scale linear programs with an exponential number of variables. Several important appl… (voir plus)ications, such as the vehicle routing problem, rely on this technique in order to be solved. However, in practice, column generation methods suffer from slow convergence (i.e. they require too many iterations). Stabilization techniques, which carefully select the column to add at each iteration, are commonly used to improve convergence. In this work, we frame the problem of selecting which columns to add as one of sequential decision-making. We propose a neural column generation architecture that iteratively selects columns to be added to the problem. Our architecture is inspired by stabilization techniques and predicts the optimal duals, which are then used to select the columns to add. We proposed architecture, trained using imitation learning. Exemplified on the Vehicle Routing Problem, we show that several machine learning models yield good performance in predicting the optimal duals and that our architecture outperforms them as well as a popular state-of-the-art stabilization technique. Further, the architecture approach can generalize to instances larger than those observed during training.
Neural Column Generation for Capacitated Vehicle Routing
Behrouz Babaki
Sanjay Dominik Jena
Laurent Charlin
The column generation technique is essential for solving linear programs with an exponential number of variables. Many important application… (voir plus)s such as the vehicle routing problem (VRP) now require it. However, in practice, getting column generation to converge is challenging. It often ends up adding too many columns. In this work, we frame the problem of selecting which columns to add as one of sequential decision-making. We propose a neural column generation architecture that iteratively selects columns to be added to the problem. The architecture, inspired by stabilization techniques, first predicts the optimal duals. These predictions are then used to obtain the columns to add. We show using VRP instances that in this setting several machine learning models yield good performance on the task and that our proposed architecture learned using imitation learning outperforms a modern stabilization technique.
2021-12-16
AAAI.org/2022/Workshop/ML4OR-22 (poster)
openreview.net
openreview.net
Individual Fairness in Kidney Exchange Programs
Golnoosh Farnadi
William St-Arnaud
Behrouz Babaki
Margarida Carvalho
2021-05-18
AAAI Conference on Artificial Intelligence (publié)
doi.org
A Unifying Framework for Fairness-Aware Influence Maximization
Golnoosh Farnadi
Behrouz Babaki
Michel Gendreau
The problem of selecting a subset of nodes with greatest influence in a graph, commonly known as influence maximization, has been well studi… (voir plus)ed over the past decade. This problem has real world applications which can potentially affect lives of individuals. Algorithmic decision making in such domains raises concerns about their societal implications. One of these concerns, which surprisingly has only received limited attention so far, is algorithmic bias and fairness. We propose a flexible framework that extends and unifies the existing works in fairness-aware influence maximization. This framework is based on an integer programming formulation of the influence maximization problem. The fairness requirements are enforced by adding linear constraints or modifying the objective function. Contrary to the previous work which designs specific algorithms for each variant, we develop a formalism which is general enough for specifying different notions of fairness. A problem defined in this formalism can be then solved using efficient mixed integer programming solvers. The experimental evaluation indicates that our framework not only is general but also is competitive with existing algorithms.
2020-04-20
Companion Proceedings of the Web Conference 2020 (publié)
doi.org
Fairness in Kidney Exchange Programs through Optimal Solutions Enumeration
Golnoosh Farnadi
Behrouz Babaki
Margarida Carvalho
Not all patients who need kidney transplant can find a donor with compatible characteristics. Kidney exchange programs (KEPs) seek to match … (voir plus)such incompatible patient-donor pairs together, usually with the objective of maximizing the total number of transplants. We propose a randomized policy for selecting an optimal solution in which patients’ equity of opportunity to receive a transplant is promoted. Our approach gives rise to the problem of enumerating all optimal solutions, which we tackle using a hybrid of constraint programming and linear programming. We empirically demonstrate the advantages of our proposed method over the common practice of using the first optimal solution obtained by a solver.