Reversible DAC and Other Improvements for Solving Max-CSP

Javier Larrosa, Pedro Meseguer, Thomas Schiex, Gérard Verfaillie

Following the work of R. Wallace on Max-CSP, later improved by J. Larrosa and P. Meseguer, we tested a number of possible improvements of the usage of directed arc consistency for the partial forward checking algorithm (PFC). The main improvement consists in exploiting a non standard form of DAC, called reversible DAC where each constraint is exploited in a direction which is not necessarily determined by the variable ordering and can change dynamically during the search. Other improvements include: (i) avoiding some constraint checks when forward-checking by exploiting the constraint checks performed during DAC preprocessing (ii) using a dynamic variable ordering during the search, (iii) maintaining the directed arc-consistency counts during the search as values get deleted. These improvements have been assessed empirically on random CSP instances. Some of them lead to very large performance gains with respect to the initial algorithm.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.