| 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. |
