Uppsala University Department of Information Technology

Technical Report 2004-015

Set Variables and Local Search

Magnus Ågren

April 2004

Many combinatorial (optimisation) problems have natural models based on, or including, set variables and set constraints. This modelling device has been around for quite some time in the constraint programming area, and proved its usefulness in many applications. This paper introduces set variables and set constraints also in the local search area. It presents a way of representing set variables in the local search context, where we deal with concepts like transition functions, neighbourhoods, and penalty costs. Furthermore, some common set constraints and their penalty costs are defined. These constraints are later used to model three problems and some initial experimental results are reported.

Note: Updated May 2004

Available as PDF (206 kB, no cover)

Download BibTeX entry.

Uppsala Universitet