Abstract
In classical constraint satisfaction, redundant modeling has been shown effective in increasing constraint propagation and reducing search space for many problem instances. In this paper, we investigate, for the first time, how to benefit the same from redundant modeling inweighted constraint satisfaction problems (WCSPs), a common soft constraint framework for modeling optimization and over-constrained problems. Our work focuses on a popular and special class of problems, namely,permutation problems. First, we show how to automatically generate a redundant permutation WCSP model from an existing permutation WCSP usinggeneralized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints and relying on the standardnode consistency (NC*) andarc consistency (AC*) algorithms would miss pruning opportunities, which are available even in a single model. Based on these observations, we suggest two approaches to handle the combined WCSP models. In our first approach, we propose\(m\text {-NC}_{\text c}^*\) and\(m\text {-AC}_{\text c}^*\) and their associated algorithms for effectively enforcing node and arc consistencies in a combined model withm sub-models. The two notions are strictly stronger than NC* and AC* respectively. While the first approach specifically refines NC* and AC* so as to apply to combined models, in our second approach, we propose a parameterized local consistency LB(m,Φ). The consistency can be instantiated withany local consistency Φ for single models and applied to a combined model withm sub-models. We also provide a simple algorithm to enforce LB(m,Φ). With the two suggested approaches, we demonstrate their applicabilities on several permutation problems in the experiments. Prototype implementations of our proposed algorithms confirm that applying\(2\text {-NC}_{\text c}^*,\;2\text {-AC}_{\text c}^*\), and LB(2,Φ) on combined models allow far more constraint propagation than applying the state-of-the-art AC*, FDAC*, and EDAC* algorithms on single models of hard benchmark problems.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bistarelli, S., Fargier, H., Montanari, U., Rossi, F., Schiex, T., & Verfaillie, G. (1996). Semiring-based CSPs and valued CSPs: Basic properties and comparison. InOver-constrained systems, (Vol 1106, pp. 111–150).
Bistarelli, S., Montanari, U., & Rossi, F. (1997). Semiring-based constraint satisfaction and optimization.Journal of the ACM, 44(2), 201–236.
Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., & Fargier, H. (1999). Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison.Constraints, 4(3), 199–240.
Bouveret, S., Heras, F., de Givry, S., Larrosa, J., Sanchez, M., & Schiex, T. (2005). ToolBar: A state-of-the-art platform for WCSP. Technical report,http://www.inra.fr/bia/T/degivry/ToolBar.pdf.
Cheng, B. M. W., Choi, K. M. F., Lee, J. H. M., & Wu, J. C. K. (1999). Increasing constraint propagation by redundant modeling: an experience report.Constraints, 4(2), 167–192.
Cheng, B. M. W., Lee, J. H. M., & Wu, J. C. K. (1996a). A constraint-based nurse rostering system using a redundant modeling approach. InProceedings of the 8th international conference on tools with artificial intelligence, (pp. 140–148).
Cheng, B. M. W., Lee, J. H. M., & Wu, J. C. K. (1996b). Speeding up constraint propagation by redundant modeling. InProceedings of the 2nd international conference on principles and practice of constraint programming, (pp. 91–103).
Cheng, B. M. W., Lee, J. H. M., & Wu, J. C. K. (1997). A nurse rostering system using constraint programming and redundant modeling.IEEE Transactions in Information Technology in Biomedicine, 1(1), 44–54.
Choueiry, B. Y., Faltings, B., & Noubir, G. (1994). Abstraction methods for resource allocation. InProceedings of the workshop on theory reformulation and abstraction, (pp. 2–71/2–90).
Cotta, C., Dotú, I., Fernández, A. J., & Van Hentenryck, P. (2007). Local search-based hybrid algorithms for finding golomb rulers.Constraints, 12(3), 263–291.
de Givry, S., Heras, F., Zytnicki, M., & Larrosa, J. (2005). Existential arc consistency: Getting closer to full arc consistency in weighted CSPs. InProceedings of the 19th international joint conference on artificial intelligence (pp 84–89).
Debruyne, R., & Bessière, C. (1997). Some practicable filtering techniques for the constraint satisfaction problem. InProceedings of the 15th international joint conference on artificial intelligence (pp. 412–417).
Dotú, I., del Val, A., & Cebrián, M. (2003). Redundant modeling for the quasigroup completion problem. InProceedings of the 9th international conference on principles and practice of constraint programming (pp. 288–302).
Easton, K., Nemhauser, G. L., & Trick, M. A. (2002). Solving the travelling tournament problem: A combined integer programming and constraint programming approach. InProceedings of the 4th international conference on practice and theory of automated timetabling IV (pp. 100–112).
Fargier, H., & Lang, J. (1993). Uncertainty in constraint satisfaction problems: A probabilistic approach. InProceedings of the European conference on symbolic and quantitative approaches to reasoning and uncertainty (pp. 97–104).
Fox, M. S. (1983).Constraint-directed search: A case study of job-shop scheduling. PhD thesis, Pittsburgh, PA: Robotics Institute, Carnegie Mellon University.
Fox, M. S., Allen, B., & Strohm, G. (1982). Job-shop scheduling: An investigation in constraint-directed reasoning. InProceedings of the 2nd conference of the American association for artificial intelligence (pp. 155–158).
Freuder, E. C., Wallace, R. J. (1992). Partial constraint satisfaction.Artificial Intelligence, 58(1–3), 21–70.
Gent, I. P., & Walsh, T. (1999). CSPLib: A benchmark library for constraints. InProceedings of the 5th international conference on principles and practice of constraint programming (pp. 480–481). Available athttp://www.csplib.org/.
Hnich, B., Smith, B., and Walsh, T. (2004). Dual modelling of permutation and injection problems.Journal of Artificial Intelligence Research, 21, 357–391.
Hnich, B., & Walsh, T. (2002). Models of injection problems. InProceedings of the 8th international conference on principles and practice of constraint programming (p. 781).
Hooker, J. N., Ottosson, G., Thorsteinsson, E. S., & Kim, H. J. (1999). On integrating constraint propagation and linear programming for combinatorial optimization. InProceedings of the 16th national conference on artificial intelligence (pp. 136–141).
Land, A. H., & Doig, A. G. (1960). An automatic method for solving discrete programming problems.Econometrica, 28, 497–520.
Larrosa, J. (2002). Node and arc consistency in weighted CSP. InProceedings of the 18th national conference on artificial intelligence (pp. 48–53).
Larrosa, J., & Schiex, T. (2003). In the quest of the best form of local consistency for weighted CSP. InProceedings of the 18th international joint conference on artificial intelligence (pp. 239–244).
Larrosa, J., & Schiex, T. (2004). Solving weighted CSP by maintaining arc consistency.Artificial Intelligence, 159(1–2), 1–26.
Law, Y. C., & Lee, J. H. M. (2002). Model induction: A new source of CSP model redundancy. InProceedings of the 18th national conference on artificial intelligence (pp. 54–60).
Law, Y. C., Lee, J. H. M., & Smith, B. M. (2007). Automatic generation of redundant models for permutation constraint satisfaction problems.Constraints, 12(4), 469–505.
Law, Y. C., Lee, J. H. M., & Woo, M. H. C. (2006). Speeding up weighted constraint satisfaction using redundant modeling. InProceedings of the 19th Australian joint conference on artificial intelligence (pp. 59–68).
Law, Y. C., Lee, J. H. M., & Woo, M. H. C. (2007). A parameterized local consistency for redundant modeling in weighted csps. InProceedings of the 20th Australian joint conference on artificial intelligence (pp. 191–201).
Lee, J. H. M., & Siu, C. F. K. (2006). Weighted constraint satisfaction with set variables. InProceedings of the 21st national conference on artificial intelligence (pp. 80–85).
Lee, J. H. M., & Siu, C. F. K. (2008). Stronger consistencies in wcsps with set variables. InProceedings of the 20th IEEE international conference on tools with artificial intelligence, pp. 291–298.
Mackworth, A. K. (1977). Consistency in networks of relations.Artificial Intelligence, 8(1), 99–118.
Manisterski, E., Sarne, D., & Kraus, S. (2008) Cooperative search with concurrent interactions.Journal of Artificial Intelligence Research, 32, 1–36.
Marti, P., & Rueher, M. (1995). A distributed cooperating constraints solving system.International Journal on Artificial Intelligence Tools, 4, 4–1.
Montoyo, A., Suarez, A., Rigau, G., & Palomar, M. (2005). Combining knowledge- and corpus-based word-sense-disambiguation methods.Journal of Artificial Intelligence Research, 23, 299–330.
Nadel, B. A. (1990). Representation selection for constraint satisfaction: A case study using n-queens.IEEE Expert: Intelligent Systems and Their Applications, 5(3), 16–23.
Ruttkay, Z. (1994). Fuzzy constraint satisfaction. InProceedings of the 1st IEEE conference on evolutionary computing (pp. 542–547).
Sathi, A., & Fox, M. S. (1989). Constraint-directed negotiation of resource reallocations. InDistributed Artificial Intelligence, 2, 163–193.
Schiex, T. (1992). Possibilistic constraint satisfaction problems or “how to handle soft constraints?”. InProceedings of the 8th conference on uncertainty in artificial intelligence (pp. 268–275).
Schiex, T. (2000). Arc consistency for soft constraints. InProceedings of the 6th international conference on principles and practice of constraint programming (pp. 411–424).
Schiex, T., Fargier, H., & Verfaillie, G. (1995). Valued constraint satisfaction problems: hard and easy problems. InProceedings of the 14th international joint conference on artificial intelligence (pp. 631–637).
Shapiro, L. G., & Haralick, R. M. (1981). Structural descriptions and inexact matching.IEEE Transactions Pattern Analysis Machine Intelligence, 3, 504–519.
Smith, B. M. (2000). Modelling a permutation problem. InProceedings of ECAI’2000 workshop on modelling and solving problems with constraints.
Smith, B. M. (2001). Dual models of permutation problems. InProceedings of the 7th international conference on principles and practice of constraint programming (pp. 615–619).
Van Hentenryck, P., & Michel, L. (2005). Nondeterministic control for hybrid search. InProceedings of the 2nd international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 380–395).
Van Hentenryck, P., & Michel, L. (2006). Nondeterministic control for hybrid search.Constraints, 11(4), 353–373.
Wallace, M. (2006). Hybrid algorithms in constraint programming. InProceedings of the 11th annual ERCIM international workshop on constraint solving and contraint logic programming (pp. 1–32).
Walsh, T. (2001). Permutation problems and channelling constraints. InProceedings of the 8th international conference on logic for programming, artificial intelligence and reasoning (pp. 377–391).
Waltz, D. (1975). Understanding line drawings of scenes with shadows. InThe psychology of computer vision (pp. 19–91).
Author information
Authors and Affiliations
Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong
Yat Chiu Law, Jimmy H. M. Lee & May H. C. Woo
- Yat Chiu Law
You can also search for this author inPubMed Google Scholar
- Jimmy H. M. Lee
You can also search for this author inPubMed Google Scholar
- May H. C. Woo
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toYat Chiu Law.
Rights and permissions
About this article
Cite this article
Law, Y.C., Lee, J.H.M. & Woo, M.H.C. Redundant modeling in permutation weighted constraint satisfaction problems.Constraints15, 354–403 (2010). https://doi.org/10.1007/s10601-009-9075-2
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative