Details

Autor(en) / Beteiligte

• Larrosa, Javier
• Meseguer, Pedro
• Schiex, Thomas

Titel

Maintaining reversible DAC for Max-CSP

Ist Teil von

• Artificial intelligence, 1999, Vol.107 (1), p.149-163

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

1999

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We introduce an exact algorithm for maximizing the number of satisfied constraints in an overconstrained CSP (Max-CSP). The algorithm, which can also solve weighted CSP, probabilistic CSP and other similar problems, is based on directed arc-inconsistency counts (DAC). The usage of DAC increases the lower bound of branch and bound based algorithms for Max-CSP, improving their efficiency. Originally, DAC were defined following a static variable ordering. In this paper, we relax this condition, showing how DAC can be defined from a directed constraint graph. These new graph-based DAC can be effectively used for lower bound computation. Interestingly, any directed constraint graph of the considered problem is suitable for DAC computation, so the selected graph can change dynamically during search, aiming at optimizing the exploitation of directed arc-inconsistencies. In addition, directed arc-inconsistencies are maintained during search, propagating the effect of value pruning. With these new elements we present the PFC maintaining reversible DAC algorithm (PFC-MRDAC), a natural successor of PFC-DAC for Max-CSP. We provide experimental evidence for the superiority of PFC-MRDAC on random and real overconstrained CSP instances, including problems with weighted constraints.