Abstract
The task at hand is that of a soft constraint problem with adversarial conditions. By amalgamating the weighted and quantified constraint satisfaction frameworks, a Minimax Weighted Constraint Satisfaction Problem (formerly Quantified Weighted Constraint Satisfaction Problem) consists of a set of finite domain variables, a set of soft constraints, and a min or max quantifier associated with each of these variables. We formally define the framework, suggest three solution concepts, and propose a complete solver based on alpha-beta pruning techniques. We discuss in depth our 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 ultra-weak 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 Constraint Satisfaction Problems. 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Allis, L.V. (1994). Searching for solutions in games and artificial intelligence. Ph.D. thesis, University of Limburg.
Apt, K. (2003). Principles of constraint programming. New York: Cambridge University Press.
Arora, S., & Barak, B. (2009). Computational complexity: a modern approach, 1st edn. Cambridge University Press.
Benedetti, M., Lallouet, A., Vautard, J. (2008). Quantified constraint optimization. In CP’08 (pp. 463–477).
Bordeaux, L., Cadoli, M., Mancini, T. (2005). CSP properties for quantified constraints: definitions and complexity. In AAAI’05 (pp. 360–365).
Bordeaux, L., & Monfroy, E. (2002). Beyond NP: arc-consistency for quantified constraints. In CP’02 (pp. 371–386).
Brown, K.N., Little, J., Creed, P.J., Freuder, E.C. (2004). Adversarial constraint satisfaction by game-tree search. In ECAI’04 (pp. 151–155).
Cabon, B, de Givry, S., Lobjois, L., Schiex, T., Warners, J. (1999). Radio link frequency assignment. CONSTRAINTS, 4, 79–89.
Cooper, M, de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M., Werner, T. (2010). Soft arc consistency revisited. Artificial Intelligence, 174 (7–8), 449–478.
Cooper, M.C., De Givry, S., Schiex, T. (2007). Optimal soft arc consistency. In IJCAI’07 (pp. 68–73).
Debruyne, R., & Bessiere, C. (1997). From restricted path consistency to max-restricted path consistency. In CP’97 (pp. 312–326).
Dempe, S. (2002). Foundations of bilevel programming. Kluwer Academic Publishers.
Gent, I.P., Nightingale, P., Stergiou, K. (2005). QCSP-Solve: a solver for quantified constraint satisfaction problems. In IJCAI’05 (pp. 138–143).
van den Herik, H.J., Uiterwijk, J.W.H.M., van Rijswijck, J. (2002). Games solved: now and in the future. Artificial Intelligence, 134 (1-2), 277–311.
Lallouet, A., Lee, J.H.M., Mak, T.W.K. (2012). Consistencies for ultra-weak solutions in minimax weighted csps using the duality principle. In CP’12 (pp. 373–389).
Larrosa, J., & Schiex, T. (2003). In the quest of the best form of local consistency for weighted CSP. In IJCAI’03 (pp. 239–244).
Larrosa, J., & Schiex, T. (2004). Solving weighted CSP by maintaining arc consistency. Artificial Intelligence, 159 (1-2), 1–26.
Lee, J.H.M., & Leung, K.L. (2012). Consistency techniques for flow-based projection-safe global cost functions in weighted constraint satisfaction. JAIR, 43, 257–292.
Lee, J.H.M., Leung, K.L., Wu, Y. (2012). Polynomially decomposable global cost functions in weighted constraint satisfaction. In AAAI’12 (pp. 507–513).
Lee, J.H.M., & Mak, T.W.K. (2012). A value ordering heuristic for solving ultra-weak solutions in minimax weighted csps. In ICTAI’12 (pp. 17–24).
Lee, J.H.M., Mak, T.W.K., Yip, J. (2011). Weighted constraint satisfaction problems with min-max quantifiers. In ICTAI ’11 (pp. 769–776).
Lee, J.H.M., & Shum, Y.W. (2011). Modeling soft global constraints as linear programs in weighted constraint satisfaction. In ICTAI ’11 (pp. 305–312).
Mamoulis, N., & Stergiou, K. (2004). Algorithms for quantified constraint satisfaction problems. In CP’04 (pp. 752–756).
Murty, K.G. (1985). Linear and combinatorial programming. R. E. Krieger.
Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (2007). Algorithmic game theory. Cambridge University Press.
Pralet, C., Schiex, T., Verfaillie, G. (2006). Decomposition of multi-operator queries on semiring-based graphical models. In CP’06 (pp. 437–452).
Pralet, C., Schiex, T., Verfaillie, G. (2009). Sequential decision-making problems - representation and solution. Wiley.
Prieditis, A.E., & Fletcher, E. (1998). Two-agent ida*. Journal of Experimental & Theoretical Artificial Intelligence, 10 (4), 451–485.
Rossi, F., van Beek, P., Walsh, T. (2006). Handbook of constraint programming (foundations of artificial intelligence). New York: Elsevier Science Inc.
Russell, S.J., & Norvig, P. (2003). Artificial intelligence: a modern approach. Pearson Education.
Schaeffer, J., Burch, N., Bjrnsson, Y., Kishimoto, A., Mller, M., Lake, R., Lu, P., Sutphen, S. (2007). Checkers is solved. Science, 317 (5844), 1518–1522.
Sturtevant, N.R., & Korf, R.E. (2000). On pruning techniques for multi-player games. In AAAI’00 (pp. 201–207).
Von Neumann, J., & Morgenstern, O. (1944). Theory of games and economic behavior. Princeton University Press.
Walsh, T. (2002). Stochastic constraint programming. In ECAI ’02 (pp. 111–115).
Wolsey, L.A. (1998). Integer programming. Wiley.
Wu, Y. (2011). Tractable projection-safe soft global constraints in weighted constraint satisfaction. Master’s thesis, The Chinese University of Hong Kong.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lallouet, A., Lee, J.H.M., Mak, T.W.K. et al. Ultra-weak solutions and consistency enforcement in minimax weighted constraint satisfaction. Constraints 20, 109–154 (2015). https://doi.org/10.1007/s10601-014-9174-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-014-9174-6