×

zbMATH — the first resource for mathematics

Finding reliable solutions: event-driven probabilistic constraint programming. (English) Zbl 1181.90208
Summary: Real-life management decisions are usually made in uncertain environments, and decision support systems that ignore this uncertainty are unlikely to provide realistic guidance. We show that previous approaches fail to provide appropriate support for reasoning about reliability under uncertainty. We propose a new framework that addresses this issue by allowing logical dependencies between constraints. Reliability is then defined in terms of key constraints called “events”, which are related to other constraints via these dependencies. We illustrate our approach on three problems, contrast it with existing frameworks, and discuss future developments.

MSC:
90C15 Stochastic programming
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Beck, J. C., & Wilson, N. (2007). Proactive algorithms for job shop scheduling with probabilistic durations. Journal of Artificial Intelligence Research, 28, 183–232. · Zbl 1182.68023
[2] Bidot, J. (2005). A general framework integrating techniques for scheduling under uncertainty. Ph.D. thesis, Ecole Nationale d’Ingèieurs de Tarbes.
[3] Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. New York: Springer. · Zbl 0892.90142
[4] Bistarelli, S., Montanari, U., & Rossi, F. (2002). Soft constraint logic programming and generalized shortest path problems. Journal of Heuristics, 8(1), 25–41. · Zbl 1073.90563
[5] Charnes, A., & Cooper, W. W. (1959). Chance-constrainted programming. Management Science, 6(1), 73–79. · Zbl 0995.90600
[6] Davenport, A., & Beck, J. C. (2000). A survey of techiniques for scheduling with uncertainty (Technical Report). Available at: http://www.tidel.mie.utoronto.ca/publications.php .
[7] de Kok, A. G., & Graves, S. C. (2003). Handbooks in operations research and management science: supply chain management: design, coordination and operation (Vol. 11). Amsterdam: Elsevier. · Zbl 1101.90311
[8] Fargier, H., Martin-Clouaire, R., Lang, J., & Schiex, T. (1995). A constraint satisfaction framework for decision under uncertainty. In Proceedings of the eleventh international conference on uncertainty in artificial intelligence, Montreal, Canada. · Zbl 0940.68133
[9] Freuder, E. C., & Richard, J. W. (1992). Partial constraint satisfaction. Artificial Intelligence.
[10] Herroelen, W., & Leus, R. (2005). Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165, 289–306. · Zbl 1066.90050
[11] 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 sixteenth national conference on artificial intelligence (pp. 136–141). Menlo Park/Cambridge: AAAI Press/MIT Press.
[12] Jain, V., & Grossmann, I. E. (2001). Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS Journal on Computing, 13, 258–276. · Zbl 1238.90106
[13] Jeffreys, H. (1961). Theory of probability. Oxford: Clarendon. · Zbl 0116.34904
[14] Kall, P., & Wallace, S. W. (1994). Stochastic programming. New York: Wiley. · Zbl 0812.90122
[15] Kingsman, B. G. (1985). Raw materials purchasing: an operational research approach. Elmsford: Pergamon.
[16] Liu, B. (1995a). Dependent-chance goal programming: a class of stochastic programming (Technical Report). Institute of System Science, Chinese Academy of Sciences.
[17] Liu, B. (1995b). Dependent-chance goal programming and its genetic algorithm approach (Technical Report). Institute of System Science, Chinese Academy of Sciences.
[18] Liu, B. (1997). Dependent-chance programming: A class of stochastic optimization. Computers & Mathematics with Applications, 34, 89–104. · Zbl 0905.90127
[19] Liu, B. (1999). Uncertain programming. New York: Wiley.
[20] Liu, B., & Iwamura, K. (1997). Modelling stochastic decision systems using dependent-chance programming. European Journal of Operational Research, 101, 193–203. · Zbl 0916.90213
[21] Liu, B., & Ku, C. (1993). Dependent-chance goal programming and an application. Journal of Systems Engineering & Electronics, 4, 40–47.
[22] McKay, M. D., Beckman, R. J., & Conover, W. J. (1979). A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 21, 239–245. · Zbl 0415.62011
[23] Porteus, E. L. (2002). Foundations of stochastic inventory theory. Stanford: Stanford University Press.
[24] Sengupta, J. K. (1972). Stochastic programming: methods and applications. Amsterdam: North-Holland. · Zbl 0262.90049
[25] Tarim, S. A., Manandhar, S., & Walsh, T. (2003). Scenario-based stochastic constraint programming. In Proceedings of the eighteenth international joint conference on artificial intelligence, Acapulco, Mexico (pp. 257–262). · Zbl 1103.68828
[26] Tarim, S. A., Manandhar, S., & Walsh, T. (2006). Stochastic constraint programming: A scenario-based approach. Constraints, 11, 53–80. · Zbl 1103.68828
[27] Vajda, S. (1972). Probabilistic programming. San Diego: Academic Press.
[28] Wu, Y., Zhou, J., & Yang, J. (2005). Dependent-chance programming model for stochastic network bottleneck capacity expansion based on neural network and genetic algorithm. In Lecture notes in computer science : Vol. 3612. Advances in Natural Computation (pp. 120–128). Berlin: Springer.
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.