Augmenting Constraint Programming Variable Selection with Domain-Specific Heuristics for a Prize-Collecting Scheduling Problem

Bachelor thesis (2024)

Authors

N. Petrov Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (coach)
I.C.W.M. Marijnissen Algorithmics - EEMCS (graduation committee member)
M.L. Flippo Algorithmics - EEMCS (mentor)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
More Info
expand_more

Published Date

20-06-2024

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

This paper investigates the inclusion of domain-specific variable selection heuristics
in Constraint Programming (CP) solvers for the Prize-Collecting Job Sequencing
with One Common and Multiple Secondary Resources (PC-JSOCMSR) problem. We
propose two variable selection heuristics: a greedy variable selection method based on
densities, Highest Density First (HDF), and a modified Variable State Independent
Decaying Sum (VSIDS) initialized with job densities, referred to as VSIDS + Density.
Experimental results on benchmark instance sets reveal that the proposed heuristics
do not outperform the baseline VSIDS heuristic. Overall, they lead to higher conflict
counts and slower convergence. These findings highlight the robustness of generalpurpose
heuristics like VSIDS in diverse problem instances. Future research should
explore other domain-specific heuristics, as the current experiment demonstrates that
the proposed heuristics do not improve performance.

Files

Research_paper_final_nikola_pe... (pdf)
(pdf | 0.659 Mb)
Unknown license