Consistencies for Ultra-Weak Solutions in Minimax Weighted CSPs Using the Duality Principle
| Autor: | Arnaud Lallouet, Jimmy H. M. Lee, Terrence W. K. Mak |
|---|---|
| Přispěvatelé: | Equipe CODAG - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), The Chinese University of Hong Kong [Hong Kong], Milano, Michela, Référent, Greyc |
| Rok vydání: | 2012 |
| Předmět: |
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]
soft constraint satisfaction minimax game search Mathematical optimization Computation Constrained optimization Duality (optimization) 0102 computer and information sciences 02 engineering and technology Minimax 01 natural sciences Upper and lower bounds [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Local consistency consistency algorithms 020201 artificial intelligence & image processing Algorithm Constraint satisfaction problem constraint optimization Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783642335570 CP Principles and Practice of Constraint Programming Principles and Practice of Constraint Programming, Oct 2012, Quebec, Canada. pp.373-389 |
| DOI: | 10.1007/978-3-642-33558-7_29 |
| Popis: | International audience; MinimaxWeighted Constraint Satisfaction Problems (formerly called QWCSPs) are a framework for modeling soft constrained problems with adversarial conditions. In this paper, we describe novel definitions and implementations of node, arc and full directional arc consistency notions to help reduce search space on top of the basic tree search with alpha-beta pruning for solving ultraweak solutions. In particular, these consistencies approximate the lower and upper bounds of the cost of a problem by exploiting the semantics of the quantifiers and reusing techniques from both Weighted and Quantified CSPs. Lower bound computation employs standard estimation of costs in the sub-problems used in alpha-beta search. In estimating upper bounds, we propose two approaches based on the Duality Principle: duality of quantifiers and duality of constraints. The first duality amounts to changing quantifiers from min to max, while the second duality re-uses the lower bound approximation functions on dual constraints to generate upper bounds. Experiments on three benchmarks comparing basic alpha-beta pruning and the six consistencies from the two dualities are performed to confirm the feasibility and efficiency of our proposal. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|