Combining SAT solvers with heuristic ideas for solving RCPSP with logical constraints

Combining SAT solvers with heuristic ideas for solving RCPSP with logical constraints: An exploration of variable ordering heuristics impact on solving RCPSP-log

Tudor, Iarina (TU Delft Electrical Engineering, Mathematics and Computer Science)

Demirović, E. (mentor)
Sidorov, K. (mentor)
Flippo, M.L. (mentor)
Decouchant, Jérémie (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2023-07-04

This paper provides a novel method of solving the resource-constrained project scheduling problem (RCPSP) with logical constraints (RCPSP-log) using satisfiability (SAT) solving and integrating variable selection heuristics. The extension provides two additional precedences: OR constraints and bidirectional (BI) relations, making it possible to express more complex dependencies between tasks. OR constraints enable a task to be dependent on multiple preceding tasks, while BI relations do not allow tasks to be executed at the same time. Both problems are known to be NP-hard.

The solution method consists of using a max satisfiability (MaxSAT) solver combined with variable selection heuristics. The paper investigates two heuristics, based on the greedy approach of scheduling each activity as early as possible and variable conflict analysis.

The results on well-known datasets from the literature show that most of the instances can be solved within the designated time limit. The proposed approaches contribute to reducing the makespan, especially when dealing with no logical constraints or only OR relations. For BI constraints, the algorithm is having difficulties in finding solutions, especially when increasing the number of activities, reporting fewer solutions than the baselines. Overall, the results provide insight into the integration of variable selection heuristics for SAT solving, with the potential for more investigation into problem-specific ideas.

RCPSP-Log
NP-Hard Algorithms
heuristics
SAT solver

http://resolver.tudelft.nl/uuid:7d74efbc-0f76-409e-bef2-1262d92c3516

Student theses

bachelor thesis

© 2023 Iarina Tudor