Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

If we have two representations of a problem as constraint satisfaction problem (CSP) models, it has been shown that combining the models using channeling constraints can increase constraint propagation in tree search CSP solvers. Handcrafting two CSP models for a problem, however, is often time-consuming. In this paper, we proposemodel induction, a process which generates a second CSP model from an existing model using channeling constraints, and study its theoretical properties. The generatedinduced model is in a different viewpoint, i.e., set of variables. It is mutually redundant to and can be combined with the input model, so that the combined model contains more redundant information, which is useful to increase constraint propagation. We also propose two methods of combining CSP models, namely model intersection and model channeling. The two methods allow combining two mutually redundant models in the same and different viewpoints respectively. We exploit the applications of model induction, intersection, and channeling and identify threenew classes of combined models, which contain different amounts of redundant information. We construct combined models of permutation CSPs and show in extensive benchmark results that the combined models are more robust and efficient to solve than the single models.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

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

  1. Ansótegui, C., & Manyà, F. (2004). Mapping problems with finite-domain variables into problems with Boolean variables. InProceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (pp. 1–15).

  2. Bessière, C., Régin, J.-C., Yap, R. H. C., & Zhang, Y. (2005). An optimal coarse-grained arc consistency algorithm.Artificial Intelligence,165(2), 165–185.

    Article MathSciNet  Google Scholar 

  3. 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.

    Article MATH  Google Scholar 

  4. Cheng, B. M. W., Lee, J. H. M., & Wu, J. C. K. (1996). Speeding up constraint propagation by redundant modeling. InProceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (pp. 91–103).

  5. Cheng, K. C. K., Lee, J. H. M., & Stuckey, P. J. (2003). Box constraint collections for adhoc constraints. InProceedings of the 9th International Conference on Principles and Practice of Constraint Programming (pp. 214–228).

  6. Cheng, K. C. K., Lee, J. H. M., & Stuckey, P. J. (2003). Efficient representation of adhoc constraints. InProceedings of the 18th International Joint Conference on Artificial Intelligence (pp. 1368–1369).

  7. Choi, C. W., Lee, J. H. M., & Stuckey, P. J. (2003). Propagation redundancy for permutation channels. InProceedings of the 18th International Joint Conference on Artificial Intelligence (pp. 1370–1371).

  8. Choi, C. W., Lee, J. H. M., & Stuckey, P. J. (2003). Propagation redundancy in redundant modelling. InProceedings of the 9th International Conference on Principles and Practice of Constraint Programming (pp. 229–243).

  9. Choi, C. W., Lee, J. H. M., & Stuckey, P. J. (2007). Removing propagation redundant constraints in redundant modeling.ACM Transactions on Computational Logic,8(4) (in press).

  10. Dao, T. B. H., Lallouet, A., Legtchenko, A., & Martin, L. (2002). Indexical-based solver learning. InProceedings of the 8th International Conference on Principles and Practice of Constraint Programming (pp. 541–556).

  11. 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).

  12. Flener, P., Frisch, A. M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., et al. (2002). Breaking row and column symmetries in matrix models. InProceedings of the 8th International Conference on Principles and Practice of Constraint Programming (pp. 462–476).

  13. Flener, P., Hnich, B., & Kiziltan, Z. (2001). Compiling high-level type constructors in constraint programming. InProceedings of the 3rd International Symposium on Practical Aspects of Declarative Languages (pp. 229–244).

  14. Frisch, A., Peugniez, T., Goggett, A., & Nightingale, P. (2005). Solving non-Boolean satisfiability problems with stochastic local search: A comparison of encodings.Journal of Automated Reasoning,35(1–3), 143–179.

    MATH MathSciNet  Google Scholar 

  15. Frisch, A. M., Grum, M., Jefferson, C., Hernández, B. M., & Miguel, I. (2007). The design of Essence: A constraint language for specifying combinatorial problems. InProceedings of the 20th International Joint Conference on Artificial Intelligence (pp. 80–87).

  16. Frisch, A. M., Jefferson, C., Hernández, B. M., & Miguel, I. (2005). The rules of constraint modelling. InProceedings of the 19th International Joint Conference on Artificial Intelligence (pp. 109–116).

  17. Geelen, P. A. (1992). Dual viewpoint heuristics for binary constraint satisfaction problems. InProceedings of the 10th European Conference on Artificial Intelligence (pp. 31–35).

  18. Gent, I. P. (2002). Arc consistency in SAT. InProceedings of the 15th European Conference on Artificial Intelligence (pp. 121–125).

  19. Hnich, B. (2003).Function variables for constraint programming. Ph.D. thesis, Department of Information Science, Uppsala University.

  20. Hnich, B., Smith, B. M., & Walsh, T. (2004). Dual modelling of permutation and injection problems.Journal of Artificial Intelligence Research,21, 357–391.

    MATH MathSciNet  Google Scholar 

  21. ILOG, S. A. (1999).ILOG Solver 4.4 Reference Manual.

  22. I. S. Laboratory (2003).SICStus Prolog User’s Manual. Swedish Institute of Computer Science.

  23. Jourdan, J. (1995).Concurrent constraint multiple models in CLP and CC languages: Toward a programming methodology by modelling. Ph.D. thesis, Université Denis Diderot, Paris VII.

  24. Jourdan, J. (1995). Concurrent constraint multiple models in CLP and CC languages: Toward a programming methodology by modelling. InProceedings of the INFORMS Conference.

  25. 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).

  26. Law, Y. C., & Lee, J. H. M. (2005). Breaking value symmetries in matrix models using channeling constraints. InProceedings of the 20th Annual ACM Symposium on Applied Computing (pp. 375–380).

  27. Law, Y. C., & Lee, J. H. M. (2006). Symmetry breaking constraints for value symmetries in constraint satisfaction.Constraints,11(2–3), 221–267.

    Article MATH MathSciNet  Google Scholar 

  28. Law, Y. C., Lee, J. H. M., & Smith, B. M. (2005). Generating a pair of mutually redundant random permutation CSPs. Technical report, Computer Science & Engineering, CUHK and Cork Constraint Computation Centre, UCC.

  29. Mackworth, A. K. (1977). Consistency in networks of relations.Artificial Intelligence,8(1), 99–118.

    Article MATH MathSciNet  Google Scholar 

  30. Marriott, K., & Stuckey, P. J. (1998).Programming with Constraints (Chapter 8, pp. 266–271). The MIT Press.

  31. Martínez-Hernández, B., & Frisch, A. M. (2006). The automatic generation of redundant representations and channelling constraints. InProceedings of the 5th International Workshop on Constraint Modelling and Reformulation (pp. 42–56).

  32. Rossi, F., Petrie, C., & Dhar, V. (1990). On the equivalence of constraint satisfaction problems. InProceedings of the 9th European Conference on Artificial Intelligence (pp. 550–556).

  33. Roussel, O. (2005). Some notes on the implementation ofcsp2sat+zchaff, a simple translator from CSP to SAT. InProceedings of the 2nd International Workshop on Constraint Propagation and Implementation (pp. 83–88).

  34. Smith, B. M. (2000). Modelling a permutation problem. Technical report 2000.18, School of Computer Studies, University of Leeds.

  35. Smith, B. M. (2001). Dual models in permutation problems. InProceedings of the 7th International Conference on Principles and Practice of Constraint Programming (pp. 615–619).

  36. Smith, B. M., & Dyer, M. E. (1996). Locating the phase transition in binary constraint satisfaction problems.Artificial Intelligence,81(1–2), 155–181.

    Article MathSciNet  Google Scholar 

  37. Walsh, T. (2000). SAT v CSP. InProceedings of the 6th International Conference on Principles and Practice of Constraint Programming (pp. 441–455).

  38. 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).

  39. Weigel, R., & Bliek, C. (1998). On reformulation of constraint satisfaction problems. InProceedings of 13th European Conference on Artificial Intelligence (pp. 254–258).

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong

    Yat Chiu Law & Jimmy H. M. Lee

  2. Cork Constraint Computation Centre, University College Cork, Cork, Ireland

    Barbara M. Smith

Authors
  1. Yat Chiu Law

    You can also search for this author inPubMed Google Scholar

  2. Jimmy H. M. Lee

    You can also search for this author inPubMed Google Scholar

  3. Barbara M. Smith

    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. & Smith, B.M. Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems.Constraints12, 469–505 (2007). https://doi.org/10.1007/s10601-007-9024-x

Download citation

Keywords

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp