Programme > Plénières

 Les ordinateurs quantiques promettent depuis quelques années de résoudre efficacement les problèmes NP difficiles en offrant un nouveau paradigme de résolution. Cette présentation va présenter l'informatique quantique sous la forme d'une introduction accessible à tous ceux qui souhaitent comprendre de quoi se compose une machine quantique et comment écrire des algorithmes tirant partie de ses machines quantiques. Suffit-il simplement de passer d'une vision séquentielle à une vision quantique ? Quelles sont les briques qui composent un programme quantique ? Existe t'il plusieurs voies possibles ? Avec quelles performances théoriques et pratiques ? Autant de questions simples auxquelles cet exposé va tenter de répondre.

In this plenary, we formally introduce a variant of the inventory-routing problem (IRP) which we call the Fixed-Partition Policy IRP (FPP-IRP). In contrast to the classical IRP where delivery routes are arbitrary, the FPP-IRP partitions customers into mutually exclusive clusters that are fixed throughout the optimization horizon, and distribution is performed separately for each cluster. By restricting the flexibility inherent in the classical IRP, the FPP-IRP attains many potential advantages. First, partitioning reduces the operational complexity of the system and allows a simpler organization of the distribution service. Second, it improves the robustness of the system by isolating disruptions to affected clusters. Third, it can fit the needs and requirements of specific applications where consistency in the distribution policy, like familiarity between customers and drivers and route invariance, is required. We present two fixed-partition policies for the IRP together with mathematical formulations and valid inequalities. We also present a worst-case analysis on the performance of these policies. Extensive computational results are presented to show the behavior of these policies and glean insights into their potential benefits.

Plénière 3 : Learning to Optimise: Online and Offline Hyperheuristics for Operational Research
Intervention du Pr. Edward Keedwell, Exeter University, UK
Jeudi 29 avril 2021 à 9h

Optimisation problems exist in many areas of business including logistics, scheduling, design, vehicle routing etc. Metaheuristics have frequently been applied to these problems but hyperheuristics offer an alternative approach that adapt themselves using learning techniques to create a bespoke optimiser for the search problem at hand. In this talk, I will describe the learning optimisation approach that is central to hyperheuristics and will cover my group’s research on the development of online and offline learning of sequences of heuristics to solve problems in the operational research and water distribution network design spaces. The talk will conclude by demonstrating that sequence-based hyperheuristics are capable of generating high-quality solutions to these problems and also can reveal important information about the mapping between the problem domain, the maturity of the optimisation process and the search strategy employed.

Plénière 4 :  Scheduling tasks with precedence constraint, release times and due dates on parallel processors:
Bounds and approximations
Intervention du Pr. Claire Hanen, Sorbonne University, FR
vendredi 30 avril 2021 à 9h

In 1976, Garey and Johnson proposed a polynomial algorithm for scheduling unit execution time tasks with precedence relations and due-dates, minimizing the maximum latency on two processors. The- defined an iterative procedure to adjust deadlines of the underlying decision problem until a fixed point is reached,before using a list scheduling algorithms. The adjustment algorithm considered both precedence and resource constraints. They extended the idea in a new algorithm to solve the same problem with release dates. The question of the interleaving of precedence and resource constraints for the computation of bounds and approximated solutions of scheduling problems with parallel processors have been investigated since by different authors providing polynomial algorithms for special cases, or approximation algorithms. In the meanwhile many work has been done to derive efficiently bounds for problems without prececence constraints on parallel processors, using mainly energetic reasoning and preemptive relaxation. Can these ideas be used in a context with precedence constraints and how? This talk will present some of the results of the field and list the open questions raised by them.