EPIA'03 - 11th Portuguese Conference on Artificial Intelligence

	Session: December 6, 17:15-18:45, Room A
Title:	Solving Set Partitioning Problems with Global Constraint Propagation
	Ricardo Saldanha and Ernesto Morgado
Abstract:	We propose a constraint-based approach for solving set partitioning problems. We show that an efficient, open and easily modifying model is obtained by using a constraint propagator that is global because it enforces consistency between local knowledge (such as variable domains) and global knowledge (such as the optimisation goal), and dynamic because it propagates the decisions taken during the search process. This propagator derives new constraints based on the existing ones by efficiently chaining a set of propagation rules that we present here and demonstrate. Once added to the constraint hypergraph, these new constraints increase its consistency level, making it more backtrack free. This propagator can be used not only to prune efficiently the search space, but also to prove in certain cases that a given solution is optimal. This approach was tested with five crew duty scheduling problems supplied by two operators from the railway and bus domains. Results were compared with the ones obtained with an approach that is a good representative of the industrial state-of-the-art.

Back to schedule.