Uncertain Data Dependency Constraints in Matrix Models

详细信息    查看全文

• 作者：C. Gervet (14)
  S. Galichet (14)
  
  14. LISTIC ; Laboratoire d鈥橧nformatique ; Syst猫mes ; Traitement de l鈥橧nformation et de la Connaissance ; Universit茅 de Savoie ; BP 80439 ; 74944 ; Annecy-Le-Vieux Cedex ; France
  
• 关键词：Data uncertainty ; Data constraints ; Interval reasoning ; Interval linear programs
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9075
• 期：1
• 页码：173-181
• 全文大小：166 KB
• 参考文献：1. Benhamou, F Inteval constraint logic programming. In: Podelski, A eds. (1995) Constraint Programming: Basics and Trends. Springer, Heidelberg, pp. 1-21 CrossRef
  2. Benhamou, F, Goualard, F Universally quantified interval constraints. In: Dechter, R eds. (2000) Principles and Practice of Constraint Programming - CP 2000. Springer, Heidelberg, pp. 67-82 CrossRef
  3. Ben-Tal, A, Nemirovski, A (1999) Robust solutions of uncertain liner programs. Operations Research Letters 25: pp. 1-13 CrossRef
  4. Bertsimas, D., Brown, D.: Constructing uncertainty sets for robust linear optimization. Operations Research (2009)
  5. Bordeaux, L, Monfroy, E Beyond NP: Arc-consistency for quantified constraints. In: Hentenryck, P eds. (2002) Principles and Practice of Constraint Programming - CP 2002. Springer, Heidelberg, pp. 371-386 CrossRef
  6. Brown, K., Miguel, I.: Chapter 21: uncertainty and change. In: Handbook of Constraint Programming. Elsevier (2006)
  7. Cheadle, A.M., Harvey, W., Sadler, A.J., Schimpf, J., Shen, K., Wallace, M.G.: ECLiPSe: An Introduction. Tech. Rep. IC-Parc-03-1, Imperial College London, London, UK
  8. Chinneck, JW, Ramadan, K (2000) Linear programming with interval coefficients. J. Operational Research Society 51: pp. 209-220 CrossRef
  9. Fargier, H., Lang, J., Schiex, T.: Mixed constraint satisfaction: A framework for decision problems under incomplete knowledge. In: Proc. of AAAI-1996 (1996)
  10. Gent, I., Nightingale, P., Stergiou, K.: QCSP-solve: A solver for quantified constraint satisfaction problems. In: Proc. of IJCAI (2005)
  11. Gervet, C, Galichet, S On combining regression analysis and constraint programming. In: Laurent, A, Strauss, O, Bouchon-Meunier, B, Yager, RR eds. (2014) Information Processing and Management of Uncertainty in Knowledge-Based Systems. Springer, Heidelberg, pp. 284-293 CrossRef
  12. Inuiguchi, M., Kume, Y.: Goal programming problems with interval coefficients and target intervals. European Journl of Oper. Res. 52 (1991)
  13. Medina, A., Taft, N., Salamatian, K., Bhattacharyya, S. Diot, C.: Traffic matrix estimation: existing techniques and new directions. In: Proceedings of ACM SIGCOMM02 (2002)
  14. Oettli, W (1965) On the solution set of a linear system with inaccurate coefficients. J. SIAM: Series B, Numerical Analysis 2: pp. 115-118
  15. Ratschan, S (2006) Efficient solving of quantified inequality constraints over the real numbers. ACM Trans. Computat. Logic 7: pp. 723-748 CrossRef
  16. Rossi, F., van Beek, P., Walsh, T.: Handbook of Constraint Programming. Elsevier (2006)
  17. Saad, A, Gervet, C, Abdennadher, S Constraint reasoning with uncertain data using CDF-intervals. In: Lodi, A, Milano, M, Toth, P eds. (2010) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Springer, Heidelberg, pp. 292-306 CrossRef
  18. Tarim, S, Kingsman, B (2004) The stochastic dynamic production/inventory lot-sizing problem with service-level constraints. International Journal of Production Economics 88: pp. 105-119 CrossRef
  19. Hentenryck, P, Michel, L, Deville, Y (1997) Numerica: A Modeling Language for Global Optimization. The MIT Press, Cambridge Mass
  20. Yorke-Smith, N., Gervet, C.: Certainty closure: Reliable constraint reasoning with uncertain data. In: ACM Transactions on Computational Logic 10(1) (2009)
  
• 作者单位：Integration of AI and OR Techniques in Constraint Programming
• 丛书名：978-3-319-18007-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Uncertain data due to imprecise measurements is commonly specified as bounded intervals in a constraint decision or optimization problem. Dependencies do exist among such data, e.g. upper bound on the sum of uncertain production rates per machine, sum of traffic distribution ratios from a router over several links. For tractability reasons existing approaches in constraint programming or robust optimization frameworks assume independence of the data. This assumption is safe, but can lead to large solution spaces, and a loss of problem structure. Thus it cannot be overlooked. In this paper we identify the context of matrix models and show how data dependency constraints over the columns of such matrices can be modeled and handled efficiently in relationship with the decision variables. Matrix models are linear models whereby the matrix cells specify for instance, the duration of production per item, the production rates, or the wage costs, in applications such as production planning, economics, inventory management. Data imprecision applies to the cells of the matrix and the output vector. Our approach contributes the following results: 1) the identification of the context of matrix models with data constraints, 2) an efficient modeling approach of such constraints that suits solvers from multiple paradigms. An illustration of the approach and its benefits are shown on a production planning problem.