Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00268450
Contributor : Christine Carvalho de Matos <>
Submitted on : Wednesday, September 4, 2019 - 8:00:00 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Document(s) archivé(s) le : Thursday, February 6, 2020 - 3:50:47 AM

File

range.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Thomas Petit, Jean-Charles Régin, Christian Bessière. 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⟩

Share

Metrics

Record views

140

Files downloads

72