乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:19:48Z","timestamp":1672291188383},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2007,8]]},"abstract":"\n A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model. However, some redundant constraints are\n propagation redundant<\/jats:italic>\n and hence do not contribute additional propagation information to the constraint solver. Redundant constraints arise naturally in the process of redundant modeling where two models of the same problem are connected and combined through channeling constraints. In this paper, we give general theorems for proving propagation redundancy of one constraint with respect to channeling constraints and constraints in the other model. We illustrate, on problems from CSPlib (http:\/\/www.csplib.org), how detecting and removing propagation redundant constraints in redundant modeling can speed up search by several order of magnitudes.\n <\/jats:p>","DOI":"10.1145\/1276920.1276925","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"23","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Removing propagation redundant constraints in redundant modeling"],"prefix":"10.1145","volume":"8","author":[{"given":"C. W.","family":"Choi","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong"}]},{"given":"J. H.M.","family":"Lee","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong"}]},{"given":"P. J.","family":"Stuckey","sequence":"additional","affiliation":[{"name":"NICTA Victoria Laboratory and the University of Melbourne, Australia"}]}],"member":"320","published-online":{"date-parts":[[2007,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218213002000903"},{"key":"e_1_2_1_2_1","volume-title":"Principles of Constraint Programming","author":"Apt K.","unstructured":"Apt , K. 2003. Principles of Constraint Programming . Cambridge University Press . Apt, K. 2003. Principles of Constraint Programming. Cambridge University Press."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068401000072"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 1st International Conference on Computational Logic (CL00)","author":"Azevedo F.","unstructured":"Azevedo , F. and Barahona , P . 2000. Modelling digital circuits problems with set constraints . In Proceedings of the 1st International Conference on Computational Logic (CL00) . 414--428. Azevedo, F. and Barahona, P. 2000. Modelling digital circuits problems with set constraints. In Proceedings of the 1st International Conference on Computational Logic (CL00). 414--428."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP02)","author":"Barnier N.","unstructured":"Barnier , N. and Brisset , P . 2002. Solving the Kirkman's schoolgirl problem in a few seconds . In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP02) . 477--491. Barnier, N. and Brisset, P. 2002. Solving the Kirkman's schoolgirl problem in a few seconds. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP02). 477--491."},{"key":"e_1_2_1_6_1","volume-title":"Joint ERCIM\/CologNet International Workshop on Constraint Solving and Constraint Logic Programming. 109--120","author":"Brand S.","year":"2003","unstructured":"Brand , S. 2003 . A note on redundant rules in rule-based constraint programming. In Recent Advances in Constraints , Joint ERCIM\/CologNet International Workshop on Constraint Solving and Constraint Logic Programming. 109--120 . Brand, S. 2003. A note on redundant rules in rule-based constraint programming. In Recent Advances in Constraints, Joint ERCIM\/CologNet International Workshop on Constraint Solving and Constraint Logic Programming. 109--120."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.35.2.164"},{"key":"e_1_2_1_8_1","unstructured":"Cheadle A. Harvey W. Sadler A. Schimpf J. Shen K. and Wallace M. 2003. ECL^{i<\/sup>PS^{e<\/sup>: An introduction. Tech. rep. IC-Parc-03-1 IC-Parc Imperial College London. Cheadle A. Harvey W. Sadler A. Schimpf J. Shen K. and Wallace M. 2003. ECL^{i<\/sup>PS^{e<\/sup>: An introduction. Tech. rep. IC-Parc-03-1 IC-Parc Imperial College London."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009894810205"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems. 3--17","author":"Choi C. W.","unstructured":"Choi , C. W. and Lee , J. H. M. 2002. On the pruning behaviour of minimal combined models for permutation CSPs . In Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems. 3--17 . Choi, C. W. and Lee, J. H. M. 2002. On the pruning behaviour of minimal combined models for permutation CSPs. In Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems. 3--17."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03)","author":"Choi C. W.","unstructured":"Choi , C. W. , Lee , J. H. M. , and Stuckey , P. J . 2003a. Propagation redundancy for permutation channels . In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03) . 1370--1371. Choi, C. W., Lee, J. H. M., and Stuckey, P. J. 2003a. Propagation redundancy for permutation channels. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03). 1370--1371."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP'03)","author":"Choi C. W.","unstructured":"Choi , C. W. , Lee , J. H. M. , and Stuckey , P. J . 2003b. Propagation redundancy in redundant modelling . In Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP'03) . 229--243. Choi, C. W., Lee, J. H. M., and Stuckey, P. J. 2003b. Propagation redundancy in redundant modelling. In Proceedings of the 9th International Conference on Principles and Practice of Constraint Programming (CP'03). 229--243."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322292"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 16th Eureopean Conference on Artificial Intelligence (ECAI'04)","author":"Frisch A. M.","unstructured":"Frisch , A. M. , Jefferson , C. , and Miguel , I . 2004. Symmetry breaking as a prelude to implied constraints: A constraint modelling pattern . In Proceedings of the 16th Eureopean Conference on Artificial Intelligence (ECAI'04) . 171--175. Frisch, A. M., Jefferson, C., and Miguel, I. 2004. Symmetry breaking as a prelude to implied constraints: A constraint modelling pattern. In Proceedings of the 16th Eureopean Conference on Artificial Intelligence (ECAI'04). 171--175."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/145448.145491"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00137870"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 4th International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR'02)","author":"Hnich B.","unstructured":"Hnich , B. , Kiziltan , Z. , and Walsh , T . 2002. Modelling a balanced academic curriculum problem . In Proceedings of the 4th International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR'02) . 121--131. Hnich, B., Kiziltan, Z., and Walsh, T. 2002. Modelling a balanced academic curriculum problem. In Proceedings of the 4th International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR'02). 121--131."},{"key":"e_1_2_1_18_1","first-page":"357","article-title":"Dual modelling of permutation and injection problems","volume":"21","author":"Hnich B.","year":"2004","unstructured":"Hnich , B. , Walsh , T. , and Smith , B. M. 2004 . Dual modelling of permutation and injection problems . J. AI Resear. 21 , 357 -- 391 . Hnich, B., Walsh, T., and Smith, B. M. 2004. Dual modelling of permutation and injection problems. J. AI Resear. 21, 357--391.","journal-title":"J. AI Resear."},{"key":"e_1_2_1_19_1","unstructured":"ILOG. 1999. ILOG Solver 4.4: Reference Manual. ILOG. 1999. ILOG Solver 4.4: Reference Manual."},{"key":"e_1_2_1_20_1","first-page":"99","article-title":"Consistency in networks of relations","volume":"8","author":"Mackworth A. K.","year":"1977","unstructured":"Mackworth , A. K. 1977 . Consistency in networks of relations . AI 8 , 1, 99 -- 118 . Mackworth, A. K. 1977. Consistency in networks of relations. AI 8, 1, 99--118.","journal-title":"AI"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/5625.003.0004"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 8th European Conference on Artificial Intelligence (ECAI'88)","author":"Mohr R.","unstructured":"Mohr , R. and Masini , G . 1988. Good old discrete relaxation . In Proceedings of the 8th European Conference on Artificial Intelligence (ECAI'88) . 651--656. Mohr, R. and Masini, G. 1988. Good old discrete relaxation. In Proceedings of the 8th European Conference on Artificial Intelligence (ECAI'88). 651--656."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/647489.727147"},{"key":"e_1_2_1_25_1","volume-title":"-C","author":"Puget J.-F.","year":"2001","unstructured":"Puget , J.-F. and R\u00e9gin , J . -C . 2001 . Solving the all interval problem. http:\/\/4c.ucc.ie\/~tw\/csplib\/prob\/prob007\/puget.pdf. Puget, J.-F. and R\u00e9gin, J.-C. 2001. Solving the all interval problem. http:\/\/4c.ucc.ie\/~tw\/csplib\/prob\/prob007\/puget.pdf."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 12th National Conference on Artificial Intelligence (AAAI'94)","author":"R\u00e9gin J.-C.","year":"1994","unstructured":"R\u00e9gin , J.-C. 1994 . A filtering algorithm for constraints of difference in CSPs . In Proceedings of the 12th National Conference on Artificial Intelligence (AAAI'94) . 362--367. R\u00e9gin, J.-C. 1994. A filtering algorithm for constraints of difference in CSPs. In Proceedings of the 12th National Conference on Artificial Intelligence (AAAI'94). 362--367."},{"key":"e_1_2_1_27_1","first-page":"10","article-title":"SICStus Prolog User's Manual","volume":"3","author":"Stus Prolog","year":"2003","unstructured":"SIC Stus Prolog . 2003 . SICStus Prolog User's Manual , Release 3 . 10 .1. SICStus Prolog. 2003. SICStus Prolog User's Manual, Release 3.10.1.","journal-title":"Release"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence (AAAI'00)","author":"Smith B.","unstructured":"Smith , B. , Stergiou , K. , and Walsh , T . 2000. Using auxiliary variables and implied constraints to model non-binary problems . In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI'00) . 182--187. Smith, B., Stergiou, K., and Walsh, T. 2000. Using auxiliary variables and implied constraints to model non-binary problems. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI'00). 182--187."},{"key":"e_1_2_1_29_1","volume-title":"Modelling a permutation problem. Resear. rep","author":"Smith B. M.","year":"2000","unstructured":"Smith , B. M. 2000. Modelling a permutation problem. Resear. rep . 2000 .18, School of Computer Studies, University of Leeds. Smith, B. M. 2000. Modelling a permutation problem. Resear. rep. 2000.18, School of Computer Studies, University of Leeds."},{"key":"e_1_2_1_30_1","volume-title":"Dual models in constraint programming. Resear. rep","author":"Smith B. M.","year":"2001","unstructured":"Smith , B. M. 2001. Dual models in constraint programming. Resear. rep . 2001 .02, School of Computer Studies, University of Leeds. Smith, B. M. 2001. Dual models in constraint programming. Resear. rep. 2001.02, School of Computer Studies, University of Leeds."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(98)10006-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/645710.664453"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_49"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1276920.1276925","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:59:20Z","timestamp":1672257560000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1276920.1276925"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1145\/1276920.1276925"],"URL":"https:\/\/doi.org\/10.1145\/1276920.1276925","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8]]},"assertion":[{"value":"2007-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}}}}}