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 metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Christine Carvalho De Matos Connect in order to contact the contributor
Submitted on : Wednesday, September 4, 2019 - 8:00:00 PM
Last modification on : Tuesday, September 6, 2022 - 4:53:21 PM
Long-term archiving on: : Thursday, February 6, 2020 - 3:50:47 AM


Files produced by the author(s)




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⟩



Record views


Files downloads