---
title: "Existential arc consistency: Getting closer to full arc consistency in weighted CSPs"
authors:
  - "Simon de Givry"
  - "Federico Heras"
  - "Matthias Zytnicki"
  - "Javier Larrosa"
doi: ""
url: "https://ijcai.org/proceedings/2005/90"
pdf: "https://ijcai.org/proceedings/2005/0090.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "84-88"
track: ""
keywords:
---

# Existential arc consistency: Getting closer to full arc consistency in weighted CSPs

Simon de Givry, Federico Heras, Matthias Zytnicki, Javier Larrosa

*Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 84-88.

## Abstract

The weighted CSP framework is a soft constraint framework with a wide range of applications. Most current state-of-the-art complete solvers can be described as a basic depth-first branch and bound search that maintain some form of arc consistency during the search. In this paper we introduce a new stronger form of arc consistency, that we call existential directional arc consistency and we provide an algorithm to enforce it. The efficiency of the algorithm is empirically demonstrated in a variety of domains.