Solving complex combinatorial problems through Maximum Satisfiability: Planning and facility location

Abstract

This thesis explores the application of Maximum Satisfiability (Max-SAT) to two key optimization problems: the p-center problem and scheduling problems, particularly focusing on the challenge of minimizing conflicts in conference session scheduling. The p-center problem, relevant in areas like facility location, aims to minimize the maximum distance between clients and their assigned facilities, which has practical applications in fields such as logistics, network design, and urban planning. Additionally, the scheduling problem addressed in this work involves organizing conference sessions to reduce conflicts and optimize the number of parallel sessions. This study uses data from the ROADEF conference, one of the most prominent French-speaking events dedicated to combinatorial optimization and operational research. ROADEF collect researchers and professionals to tackle complex problems in these fields, making it an ideal real-world case study for scheduling optimization.For both problems, this research presents Max- SAT formulations that incorporate additional variables to better capture the complexity of the issues. These models are solved using advanced techniques in Max-SAT optimization, leading to improved results. For the scheduling problem, the proposed approach significantly reduces session conflicts and the need for parallel sessions, outperforming manual solutions. In the p-center problem, the Max-SAT-based approach demonstrates effectiveness in optimizing facility locations, reducing the maximum distance between clients and facilities. The findings highlight the versatility and efficiency of Max-SAT in solving diverse optimization problems, offering systematic and effective solutions for both scheduling and facility location challenges. ***

Ce mémoire explore l’application de la Satisfiabilité Maximale (Max-SAT) à deux problèmes d’optimisation majeurs : le problème des p-centres et les problèmes de planification, avec un accent particulier sur la réduction des conflits dans l’organisation des sessions de conférences. Le problème des p-centres, pertinent dans des domaines tels que la localisation d’installations, vise à minimiser la distance maximale entre les clients et les installations qui leur sont attribuées, avec des applications pratiques dans la logistique, la conception de réseaux et l’aménagement urbain. En parallèle, le problème de planification porte sur l’optimisation des sessions d’une conférence, en vue de réduire les conflits entre sessions et le nombre de sessions parallèles. Cette étude utilise des données issues de la conférence ROADEF, l’un des événements francophones les plus prestigieux dédiés à l’optimisation combinatoire et à la recherche opérationnelle. ROADEF rassemble chercheurs et professionnels pour résoudre des problèmes complexes dans ces domaines, en faisant un cas d’étude idéal pour l’optimisation de la planification. Pour les deux problèmes, on propose des modélisations Max-SAT enrichies par l’introduction de variables supplémentaires afin de mieux représenter la complexité des situations. Ces modèles sont résolus à l’aide de techniques avancées d’optimisation Max-SAT, offrant des résultats améliorés. Dans le problème de planification, l’approche proposée permet de réduire significativement les conflits entre les sessions et le besoin de sessions parallèles, surpassant ainsi les solutions manuelles. Dans le problème des p-centres, l’approche basée sur Max-SAT s’avère efficace pour optimiser la localisation des installations et réduire la distance maximale entre les clients et les installations. Ces résultats mettent en lumière la polyvalence et l’efficacité de Max-SAT pour résoudre des problèmes d’optimisation variés, offrant des solutions systématiques et efficaces pour les défis de planification et de localisation d’installations.