Redundant modeling in permutation weighted constraint satisfaction problems.

*(English)*Zbl 1208.68202Summary: 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 in weighted 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 using generalized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints and relying on the standard node consistency (NC\(^*\)) and arc 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 with \(m\) 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 \(\text{LB}(m,\Phi )\). The consistency can be instantiated with \(any\) local consistency \(\Phi \) for single models and applied to a combined model with \(m\) sub-models. We also provide a simple algorithm to enforce \(\text{LB}(m,\Phi )\). 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 \(\text{LB}(2,\Phi )\) 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.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

##### Software:

CSPLib
PDF
BibTeX
XML
Cite

\textit{Y. C. Law} et al., Constraints 15, No. 3, 354--403 (2010; Zbl 1208.68202)

Full Text:
DOI

##### References:

[1] | Bistarelli, S., Fargier, H., Montanari, U., Rossi, F., Schiex, T., & Verfaillie, G. (1996). Semiring-based CSPs and valued CSPs: Basic properties and comparison. In Over-constrained systems, (Vol 1106, pp. 111–150). · Zbl 0946.68143 |

[2] | Bistarelli, S., Montanari, U., & Rossi, F. (1997). Semiring-based constraint satisfaction and optimization. Journal of the ACM, 44(2), 201–236. · Zbl 0890.68032 · doi:10.1145/256303.256306 |

[3] | 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. · Zbl 0946.68143 · doi:10.1023/A:1026441215081 |

[4] | 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 . |

[5] | 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. · Zbl 0949.68605 · doi:10.1023/A:1009894810205 |

[6] | Cheng, B. M. W., Lee, J. H. M., & Wu, J. C. K. (1996a). A constraint-based nurse rostering system using a redundant modeling approach. In Proceedings of the 8th international conference on tools with artificial intelligence, (pp. 140–148). |

[7] | Cheng, B. M. W., Lee, J. H. M., & Wu, J. C. K. (1996b). Speeding up constraint propagation by redundant modeling. In Proceedings of the 2nd international conference on principles and practice of constraint programming, (pp. 91–103). |

[8] | 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. · Zbl 05455939 · doi:10.1109/4233.594027 |

[9] | Choueiry, B. Y., Faltings, B., & Noubir, G. (1994). Abstraction methods for resource allocation. In Proceedings of the workshop on theory reformulation and abstraction, (pp. 2–71/2–90). |

[10] | 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. · Zbl 1211.90194 · doi:10.1007/s10601-007-9020-1 |

[11] | de Givry, S., Heras, F., Zytnicki, M., & Larrosa, J. (2005). Existential arc consistency: Getting closer to full arc consistency in weighted CSPs. In Proceedings of the 19th international joint conference on artificial intelligence (pp 84–89). |

[12] | Debruyne, R., & Bessière, C. (1997). Some practicable filtering techniques for the constraint satisfaction problem. In Proceedings of the 15th international joint conference on artificial intelligence (pp. 412–417). |

[13] | Dotú, I., del Val, A., & Cebrián, M. (2003). Redundant modeling for the quasigroup completion problem. In Proceedings of the 9th international conference on principles and practice of constraint programming (pp. 288–302). · Zbl 1273.68269 |

[14] | Easton, K., Nemhauser, G. L., & Trick, M. A. (2002). Solving the travelling tournament problem: A combined integer programming and constraint programming approach. In Proceedings of the 4th international conference on practice and theory of automated timetabling IV (pp. 100–112). |

[15] | Fargier, H., & Lang, J. (1993). Uncertainty in constraint satisfaction problems: A probabilistic approach. In Proceedings of the European conference on symbolic and quantitative approaches to reasoning and uncertainty (pp. 97–104). |

[16] | Fox, M. S. (1983). Constraint-directed search: A case study of job-shop scheduling. PhD thesis, Pittsburgh, PA: Robotics Institute, Carnegie Mellon University. · Zbl 0702.68032 |

[17] | Fox, M. S., Allen, B., & Strohm, G. (1982). Job-shop scheduling: An investigation in constraint-directed reasoning. In Proceedings of the 2nd conference of the American association for artificial intelligence (pp. 155–158). |

[18] | Freuder, E. C., Wallace, R. J. (1992). Partial constraint satisfaction. Artificial Intelligence, 58(1–3), 21–70. · Zbl 05472872 · doi:10.1016/0004-3702(92)90004-H |

[19] | Gent, I. P., & Walsh, T. (1999). CSPLib: A benchmark library for constraints. In Proceedings of the 5th international conference on principles and practice of constraint programming (pp. 480–481). Available at http://www.csplib.org/ . |

[20] | Hnich, B., Smith, B., and Walsh, T. (2004). Dual modelling of permutation and injection problems. Journal of Artificial Intelligence Research, 21, 357–391. · Zbl 1080.68667 |

[21] | Hnich, B., & Walsh, T. (2002). Models of injection problems. In Proceedings of the 8th international conference on principles and practice of constraint programming (p. 781). |

[22] | Hooker, J. N., Ottosson, G., Thorsteinsson, E. S., & Kim, H. J. (1999). On integrating constraint propagation and linear programming for combinatorial optimization. In Proceedings of the 16th national conference on artificial intelligence (pp. 136–141). |

[23] | Land, A. H., & Doig, A. G. (1960). An automatic method for solving discrete programming problems. Econometrica, 28, 497–520. · Zbl 0101.37004 · doi:10.2307/1910129 |

[24] | Larrosa, J. (2002). Node and arc consistency in weighted CSP. In Proceedings of the 18th national conference on artificial intelligence (pp. 48–53). |

[25] | Larrosa, J., & Schiex, T. (2003). In the quest of the best form of local consistency for weighted CSP. In Proceedings of the 18th international joint conference on artificial intelligence (pp. 239–244). |

[26] | Larrosa, J., & Schiex, T. (2004). Solving weighted CSP by maintaining arc consistency. Artificial Intelligence, 159(1–2), 1–26. · Zbl 1086.68592 · doi:10.1016/j.artint.2004.05.004 |

[27] | Law, Y. C., & Lee, J. H. M. (2002). Model induction: A new source of CSP model redundancy. In Proceedings of the 18th national conference on artificial intelligence (pp. 54–60). |

[28] | 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. · Zbl 1125.68112 · doi:10.1007/s10601-007-9024-x |

[29] | Law, Y. C., Lee, J. H. M., & Woo, M. H. C. (2006). Speeding up weighted constraint satisfaction using redundant modeling. In Proceedings of the 19th Australian joint conference on artificial intelligence (pp. 59–68). |

[30] | Law, Y. C., Lee, J. H. M., & Woo, M. H. C. (2007). A parameterized local consistency for redundant modeling in weighted csps. In Proceedings of the 20th Australian joint conference on artificial intelligence (pp. 191–201). |

[31] | Lee, J. H. M., & Siu, C. F. K. (2006). Weighted constraint satisfaction with set variables. In Proceedings of the 21st national conference on artificial intelligence (pp. 80–85). |

[32] | Lee, J. H. M., & Siu, C. F. K. (2008). Stronger consistencies in wcsps with set variables. In Proceedings of the 20th IEEE international conference on tools with artificial intelligence, pp. 291–298. |

[33] | Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99–118. · Zbl 0341.68061 · doi:10.1016/0004-3702(77)90007-8 |

[34] | Manisterski, E., Sarne, D., & Kraus, S. (2008) Cooperative search with concurrent interactions. Journal of Artificial Intelligence Research, 32, 1–36. · Zbl 1182.68063 |

[35] | Marti, P., & Rueher, M. (1995). A distributed cooperating constraints solving system. International Journal on Artificial Intelligence Tools, 4, 4–1. |

[36] | 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. · Zbl 1080.68703 |

[37] | 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. |

[38] | Ruttkay, Z. (1994). Fuzzy constraint satisfaction. In Proceedings of the 1st IEEE conference on evolutionary computing (pp. 542–547). |

[39] | Sathi, A., & Fox, M. S. (1989). Constraint-directed negotiation of resource reallocations. In Distributed Artificial Intelligence, 2, 163–193. |

[40] | Schiex, T. (1992). Possibilistic constraint satisfaction problems or ”how to handle soft constraints?”. In Proceedings of the 8th conference on uncertainty in artificial intelligence (pp. 268–275). |

[41] | Schiex, T. (2000). Arc consistency for soft constraints. In Proceedings of the 6th international conference on principles and practice of constraint programming (pp. 411–424). · Zbl 1044.68797 |

[42] | Schiex, T., Fargier, H., & Verfaillie, G. (1995). Valued constraint satisfaction problems: hard and easy problems. In Proceedings of the 14th international joint conference on artificial intelligence (pp. 631–637). |

[43] | Shapiro, L. G., & Haralick, R. M. (1981). Structural descriptions and inexact matching. IEEE Transactions Pattern Analysis Machine Intelligence, 3, 504–519. · doi:10.1109/TPAMI.1981.4767144 |

[44] | Smith, B. M. (2000). Modelling a permutation problem. In Proceedings of ECAI’2000 workshop on modelling and solving problems with constraints. |

[45] | Smith, B. M. (2001). Dual models of permutation problems. In Proceedings of the 7th international conference on principles and practice of constraint programming (pp. 615–619). · Zbl 1067.68674 |

[46] | Van Hentenryck, P., & Michel, L. (2005). Nondeterministic control for hybrid search. In Proceedings of the 2nd international conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 380–395). · Zbl 1133.68438 |

[47] | Van Hentenryck, P., & Michel, L. (2006). Nondeterministic control for hybrid search. Constraints, 11(4), 353–373. · Zbl 1112.68039 · doi:10.1007/s10601-006-9005-5 |

[48] | Wallace, M. (2006). Hybrid algorithms in constraint programming. In Proceedings of the 11th annual ERCIM international workshop on constraint solving and contraint logic programming (pp. 1–32). · Zbl 1176.68204 |

[49] | Walsh, T. (2001). Permutation problems and channelling constraints. In Proceedings of the 8th international conference on logic for programming, artificial intelligence and reasoning (pp. 377–391). · Zbl 1273.68365 |

[50] | Waltz, D. (1975). Understanding line drawings of scenes with shadows. In The psychology of computer vision (pp. 19–91). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.