Title: An efficient translation scheme for representing nurse rostering problems as satisfiability problems
Authors: Haspeslagh, Stefaan ×
Messelis, Tommy
Vanden Berghe, Greet
De Causmaecker, Patrick #
Issue Date: Feb-2013
Host Document: Fifth International Conference on Agents and Artificial Intelligence (ICAART 2013)
Conference: International Conference on Agents and Artificial Intelligence edition:2013 location:Barcelona, Spain date:15-18 February 2013
Article number: 177
Abstract: In this paper we present efficient translation schemes for converting nurse rostering problem instances into satisfiability problems (SAT). We define eight generic constraints types allowing the representation of a large number of nurse rostering constraints commonly found in literature. For each of the generic constraint types, we present efficient translation schemes to SAT. Special attention is paid to the representation of counting constraints. We developed a two way translation scheme for counting constraints using O(nlogn) variables and O(n2) clauses. We translated the instances of the First international nurse rostering competition 2010 to SAT and proved the infeasibility of the instances. The SAT translation was used for a hardness study of nurse rostering problem instances based on SAT features.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Computer Science Technology TC, Technology Campuses Ghent and Aalst
Technologiecluster Computerwetenschappen
Computer Science, Campus Kulak Kortrijk
Studiegebied Industriƫle Wetenschappen en Technologie - VIVES Zuid
Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
ICAART_2013_177_CR(1).pdf Accepted 685KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.