Range-Based Algorithm for Max-CSP - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2002

Range-Based Algorithm for Max-CSP

Abstract

A Max-CSP consists of searching for a solution which minimizes the number of violated constraints. The best existing solving algorithm is PFC-MRDAC. It is based on the computation of a lower bound of the number of violations. To compute this lower bound it is required to evaluate the violations with respect to each value of each domain. Unfortunately, some applications imply thousands of variables with huge domains. In scheduling, it arises that numerous activities have to be scheduled over several months with a unit of time of a few minutes. In this situation using PFC-MRDAC requires a large amount of memory which can prevent from using it. In this paper, we propose an algorithm called the Range-based Max-CSP Algorithm (RMA), based on the exploitation of bound-based filtering algorithms of constraints. This technique does not require to study each value of each domain: its complexity depends only on the number of variables and the number of constraints. No assumption is made on the constraints except that their filtering algorithms are related to the bounds of the involved variables, the general case for scheduling constraints. Then, when the only information available for a variable x w.r.t. a constraint C are the new bounds of D(x) obtained by applying the filtering algorithm of C, the lower bounds of violations provided by PFC-MRDAC and RMA are identical.
Fichier principal
Vignette du fichier
range.pdf (281.24 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00268450 , version 1 (04-09-2019)

Identifiers

Cite

Thomas Petit, Jean-Charles Régin, Christian Bessiere. Range-Based Algorithm for Max-CSP. CP: Principles and Practice of Constraint Programming, Sep 2002, Ithaca, NY, United States. pp.280-294, ⟨10.1007/3-540-46135-3_19⟩. ⟨lirmm-00268450⟩
130 View
108 Download

Altmetric

Share

More