Constraint Programming for Optimization Under Uncertainty in Stochastic Inventory Control
School
Supervisors
Abstract
Constraint Programming (CP) is a programming paradigm where relations between variables can be stated in the form of constraints. CP features discrete domains and global constraints. Global constraints capture interesting substructures of a problem, encapsulate dedicated inference algorithms based on feasibility and/or optimality reasoning, and provide information to the search process on the most viable course. Stochastic Constraint Programming (SCP) is a novel framework that generalizes CP stochastic problems, allowing both to model and solve this class of problems by using any available existing CP solver. Although this framework proves to be extremely flexible in terms of modelling power, its current implementation does not scale well. In order to enhance this framework, in this dissertation we propose a general extension for SCP: global chance-constraints. In contrast to global constraints, which represent relations among a non-fixed number of decision variables, global chance-constraints represent relations among a non-fixed number of decision variables and stochastic variables. Nevertheless, as global constraints do, global chance-constraints encapsulate dedicated inference algorithms based on feasibility and/or optimality reasoning and may provide information to the search process. We call optimization-oriented global chance-constraints those global chance-constraints performing optimality reasoning. We applied global chance-constraints encapsulating dedicated inference algorithms based on feasibility and/or optimality reasoning to problems in the area of stochastic inventory control. Our computational experience shows that global chance-constraints let us model and solve to optimality problems that could not or could be only approximately solved by other existing approaches. It also shows that filtering based on optimality reasoning is extremely effective for this class of problems.