A new local consistency for weighted CSP dedicated to long domains

ABSTRACT

The weighted constraint satisfaction problem (WCSP) is a soft constraint framework with a wide range of applications. Most current complete solvers can be described as a depth-first branch and bound search that maintains some form of local consistency during the search. However, the known consistencies are unable to solve problems with huge domains because of their time and space complexities. In this paper, we adapt the 2B-consistency, a weaker form of arc consistency well-known in classic CSPs, into the bound arc consistency and we provide several algorithms to enforce it.

REFERENCES

• 1: Stefano Bistarelli , Philippe Codognet , Yan Georget , Francesca Rossi, Labeling and Partial Local Consistency for Soft Constraint Programming, Proceedings of the Second International Workshop on Practical Aspects of Declarative Languages, p.230-248, January 01, 2000
• 2: Martin Cooper , Thomas Schiex, Arc consistency for soft constraints, Artificial Intelligence, v.154 n.1-2, p.199-227, April 2004 [doi>10.1016/j.artint.2003.09.002]
• 3: D. Gautheret, F. Major, and R. Cedergren. Pattern searching/alignment with RNA primary and secondary structures: an effective descriptor for tRNA. Comp. Appl. Biosc., 6:325--331, 1990.
• 4: J. Gorodkin, L. L. Heyer, and G. D. Stormo. Finding the most significant common sequence and structure motifs in a set of RNA sequences. Nucleic Acids Research, 25:3724--3732, 1997.
• 5: Pascal Van Hentenryck , Yves Deville , Choh-Man Teng, A generic arc-consistency algorithm and its specializations, Artificial Intelligence, v.57 n.2-3, p.291-321, Oct. 1992 [doi>10.1016/0004-3702(92)90020-X ]
• 6: L. Khatib, P. Morris, R. Morris, and F. Rossi. Temporal constraint reasoning with preferences. In Proc. IJCAI 2001, pages 322--327, 2001.
• 7: Javier Larrosa, Node and arc consistency in weighted CSP, Eighteenth national conference on Artificial intelligence, p.48-53, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 8: Javier Larrosa , Pedro Meseguer , Thomas Schiex, Maintaining reversible DAC for Max-CSP, Artificial Intelligence, v.107 n.1, p.149-163, Jan. 1999 [doi>10.1016/S0004-3702(98)00108-8 ]
• 9: Javier Larrosa , Thomas Schiex, Solving weighted CSP by maintaining arc consistency, Artificial Intelligence, v.159 n.1-2, p.1-26, November 2004 [doi>10.1016/j.artint.2004.05.004]
• 10: O. Lhomme. Consistency techniques for numeric CSPs. In Proc. IJCAI 1993, pages 232--238, 1993.
• 11: C. Bessiere, Meta-constraints on violations for over constrained problems, Proceedings of the 12th IEEE International Conference on Tools with Artificial Intelligence, p.358, November 13-15, 2000
• 12: Thierry Petit , Jean-Charles Régin , Christian Bessière, Range-Based Algorithm for Max-CSP, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.280-294, September 09-13, 2002
• 13: Thomas Schiex, Arc Consistency for Soft Constraints, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.411-424, September 18-21, 2000
• 14: T. Schiex, H. Fargier, and G. Verfaillie. Valued constraint satisfaction problems: Hard and easy problems. In Proc. IJCAI 1995, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms

Keywords:
bound arc consistency, local consistency, weighted constraint satisfaction problem