Résumé : Research on metaheuristics has focused on (novel) algorithmic development and on competitive testing, both of which have been frequently argued to yield little generalizable knowledge. This talk discusses meta-analysis — a systematic statistical examination that combines the results of several independent studies — as a more suitable way to obtain problem- and implementation-independent insights on metaheuristics. Meta-analysis is widely used in several scientific domains, most notably the medical sciences (e.g., to establish the efficacy of a certain treatment). To the best of our knowledge, this is the first meta-analysis in the field of metaheuristics. To illustrate the approach, we carry out a meta-analysis to gain insights into the importance of the adaptive layer in adaptive large neighborhood search (ALNS). Although ALNS has been widely used to solve a broad range of problems, it has not yet been established whether or not adaptiveness actually contributes to the performance of an ALNS algorithm.

Résumé : We present a travel through different domains, including discrete geometry, air traffic management and network science, to explore the capability and impact of MINLP. We propose mixed-integer nonlinear models and show how very different problems can be successfully handled in a MINLP framework. This leads to different outcomes for the addressed problems, going from a numerical proof of the optimal solution for a problem of covering in discrete geometry, to math-heuristic algorithms for network clustering, passing through efficient global solutions for a complex real-life application in air traffic management.

Résumé : Parallelization is a powerful tool for speeding up the completion of activities in diverse areas such as computation, construction, or production. Malleable scheduling captures this possibility by allowing each job to be processed simultaneously on a set of multiple machines. The classic malleable scheduling model operates under the assumptions that the processing time of a job only depends on the number k of machines asssigned to it ("identical machines") and does not decrease faster than 1/k ("non-decreasing work"). In this talk, we discuss malleable scheduling beyond identical machines: We allow the processing time of each job to be a (job-dependent) function f of the set of machines assigned to it, and translate the nondecreasing work assumption to conditions on the "speed functions" 1/f. For fractionally subadditive speeds, we show that, with only a small increase of makespan, any assignment of the jobs to machine sets can be turned into a schedule with a simple structure that is easy to execute in practice and robust to delays in the execution of individual jobs. For the case of submodular speed functions this transformation can be carried out efficiently and can be further exploited to derive a simple logarithmic approximation algorithm. Finally, when speeds fulfill the gross-substitutes property, we obtain a constant factor approximation by carefully utilizing the underlying discrete convexity structure. This is joint work with Dimitris Fotakis and Orestis Papadigenopoulos.

Résumé : We give the first 2-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a 'good' cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem. This is joint work with Manuel Aprile (Padova U), Matthew Drescher (ULB, Brussels), Tony Huynh (Monash U)

Résumé : We will take the example of linear program modelling to show original ideas to teach OR even in a distant mode. Learning how to model, as a linear program, a problem described in natural language requires the students to train on various and numerous exercises. Moreover, a fast feedback on the validity of their solutions helps a better and faster understanding. We present an idea on how a student or a teacher can evaluate automatically a linear program modelling. We also describe how this idea has been implemented as a tool on the learning platform caseine.org and used by hundreds of students from various universities. This is ongoing work with Hadrien Cambazard and Nicolas Catusse.

Résumé : In this talk, we describe the strong relationship between mixed-integer programming (MIP) and dynamic programming (DP). We show two case studies. In the first one (a variant of knapsack problem) valid inequalities are used to improve a method based on DP. In the second one (a variant of vehicle routing problem) a DP is used to produce a stronger MIP formulation, which is solved using an iterative method inspired from techniques used for DP.

Résumé : The Balanced Minimum Evolution Problem (BMEP) is proving of fundamental assistance to track evolution of SARS-Cov2 during COVID19 pandemic. In this talk we introduce the audience to the problem and we present new results on some fundamental characteristics of the BMEP polytope, facet-defining inequalities, a polynomial time oracle to recognize its vertices, as well as a massively parallel branch-and-bound algorithm to solve its instances.