Abstract
We study stochastic variants of flow-based global constraints as combinatorial chance constraints. As a specific case study, we focus on the stochastic weighted alldifferent constraint. We first show that determining the consistency of this constraint is NP-hard. We then show how the combinatorial structure of the alldifferent constraint can be used to define chance-based filtering, and to compute a policy. Our propagation algorithm can be extended immediately to related flow-based constraints such as the weighted cardinality constraint. The main benefits of our approach are that our chance-constrained global constraints can be integrated naturally in classical deterministic CP systems, and are more scalable than existing approaches for stochastic constraint programming.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice-Hall (1993)
Altarelli, F., Braunstein, A., Ramezanpour, A., Zecchina, R.: Stochastic Matching Problem. Physical Review Letters 106(190601) (2011)
Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When lp is the cure for your matching woes: Improved bounds for stochastic matchings. In: Proceedings of the 18th Annual European Symposium on Algorithms, pp. 218–230. Springer (2010)
Beldiceanu, N., Katriel, I., Thiel, S.: Filtering Algorithms for the Same Constraint. In: Régin, J.-C., Rueher, M. (eds.) CPAIOR 2004. LNCS, vol. 3011, pp. 65–79. Springer, Heidelberg (2004)
Brown, K.N., Miguel, I.: Uncertainty and Change. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, ch. 21. Elsevier (2006)
Chaudhuri, K., Daskalakis, C., Kleinberg, R.D., Lin, H.: Online bipartite perfect matching with augmentations. In: INFOCOM, pp. 1044–1052 (2009)
Chen, N., Immorlica, N., Karlin, A., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pp. 266–278 (2009)
Derman, C., Lieberman, G.J., Ross, S.M.: A Sequential Stochastic Assignment Problem. Management Science 18(7), 349–355 (1972)
Escoffier, B., Gourvès, L., Monnot, J., Spanjaard, O.: Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation. European Journal of Operational Research 205(1), 19–30 (2010)
Fargier, H., Lang, J.: Uncertainty in Constraint Satisfaction Problems: A Probabilistic Approach. In: Moral, S., Kruse, R., Clarke, E. (eds.) ECSQARU 1993. LNCS, vol. 747, pp. 97–104. Springer, Heidelberg (1993)
Fargier, H., Lang, J., Martin-Clouaire, R., Schiex, T.: A constraint satisfaction framework for decision under uncertainty. In: Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence, pp. 167–174. Morgan Kaufmann (1995)
Feldman, J., Mehta, A., Mirrokni, V.S., Muthukrishnan, S.: Online Stochastic Matching: Beating 1-1/e. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 117–126. IEEE Computer Society (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co. (1979)
Hauskrecht, M., Upfal, E.: A clustering approach to solving large stochastic matching problems. In: Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, pp. 219–226 (2001)
Hnich, B., Rossi, R., Tarim, S.A., Prestwich, S.: Synthesizing Filtering Algorithms for Global Chance-Constraints. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 439–453. Springer, Heidelberg (2009)
Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 587–596. ACM (2011)
Katriel, I., Kenyon-Mathieu, C., Upfal, E.: Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 171–182. Springer, Heidelberg (2007)
Kong, N., Schaefer, A.J.: A factor 1/2 approximation algorithm for two-stage stochastic matching problems. European Journal of Operational Research 172(3), 740–746 (2006)
Louveaux, F.V., Schultz, R.: Stochastic Integer Programming. In: Ruszczynski, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10. Elsevier (2003)
Majercik, S.M.: Stochastic Boolean Satisfiability. In: Biere, A., Heule, M., van Maaren, M., Walsh, T. (eds.) Handbook of Satisfiability, pp. 887–925. IOS Press (2009)
Régin, J.-C.: A Filtering Algorithm for Constraints of Difference in CSPs. In: Proceedings of the Twelfth National Conference on Artificial Intelligence, vol. 1, pp. 362–367. AAAI Press (1994)
Régin, J.C.: Cost-Based Arc Consistency for Global Cardinality Constraints. Constraints 7, 387–405 (2002)
Rossi, R., Tarim, S.A., Hnich, B., Prestwich, S.D.: A Global Chance-Constraint for Stochastic Inventory Systems Under Service Level Constraints. Constraints 13(4), 490–517 (2008)
Rossi, R., Tarim, S.A., Hnich, B., Prestwich, S.D.: Cost-Based Domain Filtering for Stochastic Constraint Programming. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 235–250. Springer, Heidelberg (2008)
Tarim, S.A., Manandhar, S., Walsh, T.: Stochastic Constraint Programming: A Scenario-Based Approach. Constraints 11(1), 53–80 (2006)
Tarim, S.A., Hnich, B., Rossi, R., Prestwich, S.D.: Cost-Based Filtering Techniques for Stochastic Inventory Control Under Service Level Constraints. Constraints 14(2), 137–176 (2009)
Terekhov, D., Beck, J.C.: A constraint programming approach for solving a queueing control problem. J. Artif. Int. Res. 32, 123–167 (2008)
Terekhov, D., Beck, J.C., Brown, K.N.: A Constraint Programming Approach for Solving a Queueing Design and Control Problem. INFORMS Journal on Computing 21(4), 549–561 (2009)
Walsh, T.: Stochastic Constraint Programming. In: Proceedings of the 15th Eureopean Conference on Artificial Intelligence, pp. 111–115. IOS Press (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cire, A.A., Coban, E., van Hoeve, WJ. (2012). Flow-Based Combinatorial Chance Constraints. In: Beldiceanu, N., Jussien, N., Pinson, É. (eds) Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems. CPAIOR 2012. Lecture Notes in Computer Science, vol 7298. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29828-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-29828-8_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29827-1
Online ISBN: 978-3-642-29828-8
eBook Packages: Computer ScienceComputer Science (R0)