Deriving Information from Sampling and Diving

• Autorzy: Lombardi M. , Milano M. , Roli A. , Zanarini A.
• Języki publikacji: EN

Abstrakty

EN

We investigate the impact of information extracted from sampling and diving on the solution of Constraint Satisfaction Problems (CSP). A sample is a complete assignment of variables to values taken from their domain according to a given distribution. Diving consists in repeatedly performing depth first search attempts with random variable and value selection, constraint propagation enabled and backtracking disabled; each attempt is called a dive and, unless a feasible solution is found, it is a partial assignment of variables (whereas a sample is a –possibly infeasible– complete assignment). While the probability of finding a feasible solution via sampling or diving is negligible if the problem is difficult enough, samples and dives are very fast to generate and, intuitively, even when they are infeasible, they can provide some statistical information on search space structure. The aim of this paper is to understand to what extent it is possible to support the CSP solving process with information derived from sampling and diving. In particular, we are interested in extracting from samples and dives precise indications on the quality of individual variable-value assignments with respect to feasibility. We formally prove that even uniform sampling could provide precise evaluation of the quality of single variable-value assignments; as expected, this requires huge sample sizes and is therefore not useful in practice. On the contrary, diving is much better suited for assignment evaluation purposes. We undertake a thorough experimental analysis on a collection of Partial Latin Square and Car Sequencing instances to assess the quality of information provided by dives. Dive features are identified and their impact on search is evaluated. Results show that diving provides information that can be fruitfully exploited.

Słowa kluczowe

EN

constraint satisfaction problems; sampling method; diving; heuristics evaluation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 2/3
• Strony: 267--287
• Opis fizyczny: Bibliogr. 21 poz., tab.

Twórcy

autor

Lombardi M.

autor

Milano M.

autor

Roli A.

autor

Zanarini A.

• DEIS, Alma Mater Studiorum Universita di Bologna V.le Risorgimento 2, 40136, Bologna, Italy,

Bibliografia

• [1] Beck, J. C.: Solution-GuidedMulti-Point Constructive Search for Job Shop Scheduling, Journal of Artificial Intelligence Research, 29, 2007, 49-77.
• [2] Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting Systematic Search by Weighting Constraints, Proc. of ECAI, Ios Pr Inc, 2004, ISBN 1586034529.
• [3] Colbourn, C. J.: The Complexity Of Completing Partial Latin Squares, Discrete Applied Mathematics, 8(1), 1984, 25-30.
• [4] Gogate, V., Dechter, R.: A New Algorithm For Sampling CSP Solutions Uniformly At Random, in: Principles and Practice of Constraint Programming - CP 2006 (F. Benhamou, Ed.), vol. 4204 of Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg, Germany, 2006, 711-715.
• [5] Gogate, V., Dechter, R.: Approximate Counting by Sampling the Backtrack-free Search Space, Proc. Of AAAI, AAAI Press, 2007, ISBN 978-1-57735-323-2.
• [6] Gomes, C., Shmoys, D.: Completing Quasigroups Or Latin Squares: A Structured Graph Coloring Problem, Proc. of the COLOR, 2002.
• [7] Gomes, C. P., Sabharwal, A., Selman, B.: Near-Uniform Sampling Of Combinatorial Spaces Using XOR Constraints, Advances In Neural Information Processing Systems, 19, 2007, 481.
• [8] Gomes, C. P., Shmoys, D. B.: Approximations And Randomization To Boost CSP Techniques, Annals of Operations Research, 130(1), 2004, 117-141.
• [9] Grimes, D., Wallace, R. J.: Learning To Identify Global Bottlenecks In Constraint Satisfaction Search, 20th International FLAIRS conference, 2007.
• [10] van Hoeve, W., Milano, M.: Decomposition Based Search-A theoretical and experimental evaluation, Arxiv preprint cs/0407040, 2004.
• [11] Hsu, E. I., Kitching, M., Bacchus, F., Mcllraith, S. A.: Using Expectation Maximization to Find Likely Assignments for Solving CSP'S, Proc. of AAAI, 22, Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2007.
• [12] Knuth, D.: Estimating The Efficiency Of Backtrack Programs, Mathematics of computation, 29(129), 1975, 121-136, ISSN 0025-5718.
• [13] Le Bras, R., Zanarini, A., Pesant, G.: Efficient Generic Search Heuristics within the EMBP Framework, Proceedings of the 15th international conference on Principles and practice of constraint programming, Springer-Verlag, 2009, ISBN 3642042430.
• [14] Lombardi, M., Milano, M., Roli, A., Zanarini, A.: Deriving information from sampling and diving, in: Emergent Perspectives in Artificial Intelligence - AI*IA 2009 (R. Serra, R. Cucchiara, Eds.), vol. 5883 of Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg, Germany, 2009, 82-91.
• [15] Papoulis, A., Pillai, S. U., A, P., SU, P.: Probability, Random Variables, And Stochastic Processes, McGraw-Hill New York, 1965.
• [16] Parrello, B., Kabat, W., Wos, L.: Job-Shop Scheduling Using Automated Reasoning: A Case Study Of The Car-Sequencing Problem, Journal of Automated Reasoning, 2(1), 1986, 1-42, ISSN 0168-7433.
• [17] Refalo, P.: Impact-Based Search Strategies for Constraint Programming, in: Principles and Practice of Constraint Programming - CP 2004 (M. Wallace, Ed.), vol. 3258 of Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg, Germany, 2004, 557-571.
• [18] Régin, J.-C., Puget, J.-F.: A Filtering Algorithm for Global Sequencing Constraints, in: Principles and Practice of Constraint Programming - CP 1997 (G. Smolka, Ed.), vol. 1330 of Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg, Germany, 1997, 32-46.
• [19] Rodgers, J. L., Nicewander, W. A.: Thirteen Ways to Look at the Correlation Coefficient, The American Statistician, 42(1), 1988, pp. 59-66, ISSN 00031305.
• [20] Ruml, W.: Adaptive Tree Search, Ph.D. Thesis, Harvard University Cambridge, Massachusetts, 2002.
• [21] Zanarini, A., Pesant, G.: Solution Counting Algorithms For Constraint-Centered Search Heuristics, Constraints, 14(3), 2009, 392-413.