Augmenting VSIDS heuristic for the RCPSP/t by initializing activity values using domain-specific information

Augmenting VSIDS heuristic for the RCPSP/t by initializing activity values using domain-specific information

Lenssen, Tijs (TU Delft Electrical Engineering, Mathematics and Computer Science)

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

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2023-07-04

The Variable State Independent Decaying Sum (VSIDS) heuristic is one of the most effective variable selection heuristics for Conflict-Driven Clause-Learning (CDCL) SAT solvers. It works by keeping track of the activity values for each variable, which get bumped and decayed based on conflict analysis. These activity values usually start out arbitrarily at zero, which prompts the question if initializing these values can result in better performance.
This paper presents several adaptations of the VSIDS heuristic specialized for solving the Resource-Constraint Project Scheduling Problem with time varying resource availabilities and demands (RCPSP/t). The approach uses domain-specific knowledge to initialize the activity values of VSIDS with more relevant values. The experiments presented in this paper show that this domain-specific knowledge can indeed benefit the heuristic and can lead to better solve times, allowing the solver to find solutions for 17% more of the instances and find proven optimal solutions for 5% more instances of the PSPLIB data set.

RCPSP
RCPSP/t
VSIDS
NP-hard
variable selection
Heuristics
SAT Solver

http://resolver.tudelft.nl/uuid:7ed8b13a-316c-4426-a5be-156aa8276449

Student theses

bachelor thesis

© 2023 Tijs Lenssen