Combinational Optimal Stopping Problems
Technical Report,01 Apr 2012,31 Dec 2015
University of Iowa Iowa City United States
Pagination or Media Count:
Optimal resource utilization is one of the most general meta-settings in operations research many hard optimization problems can be casted as problems of optimal resource utilization. Additional challenges are introduced by uncertainties the difficulties are further multiplied in a dynamic context. This project has considered a class of discrete and combinatorial optimal resource utilization problems under uncertainties that arise in the context of the optimal stopping problems. In addition, as a generalization of traditional stochastic formulations that optimize the expected payoff or cost, we considered risk averse discrete and combinatorial optimization problems, where the risk of the stopping decision was estimated using a coherent or convex risk measure. In particular, we developed a special class of certainty equivalent CE measures of risk that can be represented via solution of a specially formulated stochastic optimization problem. A number of solution techniques for discrete and combinatorial problems involving CE measures have been developed, including exact methods based on polyhedral approximations, branch-and-bound and branch-and-cut algorithms, scenario decomposition techniques, and combinatorial branch-and-bound methods for risk-averse combinatorial optimization problems.
- Operations Research