Solving disjunctive temporal problems: a constraint programming approach

Details

Supervisors

Saint-Guillain, Michael ; Schaus, Pierre ; Deville, Yves

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] en sciences informatiques, à finalité spécialisée

Abstract

In our increasingly connected world, the management and coordination of time-dependent tasks is crucial. Disjunctive Temporal Networks (DTNs) play a central role in managing such complex, time-sensitive tasks. Their applications range from planning space exploration missions, where precise sequencing of events is vital, to organizing intricate operations within supply chains. However, the resolution of DTNs, due to their combinatorial nature, remains a long-standing challenge. This thesis provides a fresh perspective to this issue by transforming the quest for a perfect DTN solution into the pursuit of a practical approximation. It proposes a novel approach using Constraint Programming (CP) and the Boolean Switch relaxation, to turn the DTN problem into a Constrained Optimization Problem (COP). This method aims to find feasible solutions faster and provides flexible way of handling DTNs. To ease this process and further enhance the practicality of our approach, we developed a user-friendly tool. This tool allows for real-time visualization and tracking of constraint violations during the relaxation process. It integrates various solvers along with the strategies we’ve developed, thereby creating an interactive platform for DTNs resolution.