2019/05/22 by Rachid Oucheikh, Oucheikh, Rachid, Ismaïl Berrada +3
Computer Science · #AI-based Problem Solving and Planning #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Model-Driven Software Engineering Techniques
paper · pdf · doi:10.48550/arxiv.1905.09083
openalex publication_date 2019/05/22 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
Constraint Satisfaction Problem (CSP) is a framework for modeling and solving\na variety of real-world problems. Once the problem is expressed as a finite set\nof constraints, the goal is to find the variables' values satisfying them. Even\nthough the problem is in general NP-complete, there are some approximation and\npractical techniques to tackle its intractability. One of the most widely used\ntechniques is the Constraint Propagation. It consists in explicitly excluding\nvalues or combination of values for some variables whenever they make a given\nsubset of constraints unsatisfied. In this paper, we deal with a CSP subclass\nwhich we call 4-CSP and whose constraint network infers relations of the form:\n x \∼ \α, x-y \∼ \β , (x-y) - (z-t) \∼ \λ , where x,\ny, z and t are real variables, \α , \β and \λ are real\nconstants and \∼ \∈ \≤ , \≥ . The paper provides the first\ngraph-based proofs of the 4-CSP tractability and elaborates algorithms for\n4-CSP resolution based on the positive linear dependence theory, the hypergraph\nclosure and the constraint propagation technique. Time and space complexities\nof the resolution algorithms are proved to be polynomial.\n