Andrea Lodi

In recent years, the integration of Machine Learning (ML) models with Operation Research (OR) tools has gained popularity across diverse app… (voir plus)lications, including cancer treatment, algorithmic configuration, and chemical process optimization. In this domain, the combination of ML and OR often relies on representing the ML model output using Mixed Integer Programming (MIP) formulations. Numerous studies in the literature have developed such formulations for many ML predictors, with a particular emphasis on Artificial Neural Networks (ANNs) due to their significant interest in many applications. However, ANNs frequently contain a large number of parameters, resulting in MIP formulations that are impractical to solve, thereby impeding scalability. In fact, the ML community has already introduced several techniques to reduce the parameter count of ANNs without compromising their performance, since the substantial size of modern ANNs presents challenges for ML applications as it significantly impacts computational efforts during training and necessitates significant memory resources for storage. In this paper, we showcase the effectiveness of pruning, one of these techniques, when applied to ANNs prior to their integration into MIPs. By pruning the ANN, we achieve significant improvements in the speed of the solution process. We discuss why pruning is more suitable in this context compared to other ML compression techniques, and we identify the most appropriate pruning strategies. To highlight the potential of this approach, we conduct experiments using feed-forward neural networks with multiple layers to construct adversarial examples. Our results demonstrate that pruning offers remarkable reductions in solution times without hindering the quality of the final decision, enabling the resolution of previously unsolvable instances.

2023-07-14

ArXiv (preprint)

Capacity Planning in Stable Matching: An Application to School Choice

Federico Bobbio

Margarida Carvalho

Ignacio Rios

Alfredo Torrico

Centralized mechanisms are becoming the standard approach to solve several assignment problems. Examples include the allocation of students … (voir plus)to schools (school choice), high-school graduates to colleges, residents to hospitals and refugees to cities. In most of these markets, a desirable property of the assignment is stability, which guarantees that no pair of agents has incentive to circumvent the matching. Using school choice as our matching market application, we introduce the problem of jointly allocating a school capacity expansion and finding the best stable matching for the students in the expanded market. We analyze theoretically the problem, focusing on the trade-off behind the multiplicity of student-optimal assignments, and the problem complexity. Since the theoretical intractability of the problem precludes the adaptation of classical approaches to solve it efficiently, we generalize existent mathematical programming formulations of stability constraints to our setting. These generalizations result in integer quadratically-constrained programs, which are computationally hard to solve. In addition, we propose a novel mixed-integer linear programming formulation that is exponentially-large on the problem size. We show that the stability constraints can be separated in linear time, leading to an effective cutting-plane method. We evaluate the performance of our approaches in a detailed computational study, and we find that our cutting-plane method outperforms mixed-integer programming solvers applied to existent formulations extended to our problem setting. We also propose two heuristics that are effective for large instances of the problem. Finally, we use the Chilean school choice system data to demonstrate the impact of capacity planning under stability conditions. Our results show that each additional school seat can benefit multiple students. On the one hand, we can focus on access by prioritizing extra seats that benefit previously unassigned students; on the other hand, we can focus on merit by allocating extra seats that benefit several students via chains of improvement. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.

2023-07-07

Proceedings of the 24th ACM Conference on Economics and Computation (publié)

Continuous cutting plane algorithms in integer programming

Didier Chételat

2023-07-01

Operations Research Letters (publié)

A solution algorithm for chance-constrained problems with integer second-stage recourse decisions

Enrico Malaguti

Michele Monaci

Giacomo Nannicini

Paolo

Paronuzzi

2023-06-15

Mathematical programming (publié)

Integer Programming Games: A Gentle Computational Overview

Margarida Carvalho

Gabriele Dragotto

Sriram Sankaranarayan

2023-06-05

ArXiv (prépublication)

Predicting Time to and Average Quality of Future Offers for Kidney Transplant Candidates Declining a Current Deceased Donor Kidney Offer: A Retrospective Cohort Study

Jonathan Jalbert

Jean-Noel Weller

Pierre-Luc Boivin

Sylvain Lavigne

Mehdi Taobane

Mike Pieper

Heloise Cardinal

2023-06-02

Canadian Journal of Kidney Health and Disease (publié)

Machine-learning-based arc selection for constrained shortest path problems in column generation

Mouad Morabit

Guy Desaulniers

Column generation is an iterative method used to solve a variety of optimization problems. It decomposes the problem into two parts: a maste… (voir plus)r problem and one or more pricing problems (PP). The total computing time taken by the method is divided between these two parts. In routing or scheduling applications, the problems are mostly defined on a network, and the PP is usually an NP-hard shortest path problem with resource constraints. In this work, we propose a new heuristic pricing algorithm based on machine learning. By taking advantage of the data collected during previous executions, the objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution. The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows. Reductions in computational time of up to 40% can be obtained.

2023-04-01

INFORMS Journal on Optimization (publié)

The Critical Node Game

Gabriele Dragotto

Amine Boukhtouta

Mehdi Taobane

Cloud networks are the backbone of the modern distributed internet infrastructure as they provision most of the on-demand resources organiza… (voir plus)tions and individuals use daily. However, any abrupt cyber-attack could disrupt the provisioning of some of the cloud resources fulfilling the needs of customers, industries, and governments. In this work, we introduce a game-theoretic model that assesses the cyber-security risk of cloud networks and informs security experts on the optimal security strategies. Our approach combines game theory, combinatorial optimization, and cyber-security and aims at minimizing the unexpected network disruptions caused by malicious cyber-attacks under uncertainty. Methodologically, our approach consists of a simultaneous and non-cooperative attacker-defender game where each player solves a combinatorial optimization problem parametrized in the variables of the other player. Practically, our approach enables security experts to (i.) assess the security posture of the cloud network, and (ii.) dynamically adapt the level of cyber-protection deployed on the network. We provide a detailed analysis of a real-world cloud network and demonstrate the efficacy of our approach through extensive computational tests.

2023-03-10

ArXiv (prépublication)

A Convex Reformulation and an Outer Approximation for a Large Class of Binary Quadratic Programs

Borzou Rostami

Fausto Errico

2023-03-01

Operations Research (publié)