Combinational Optimal Stopping Problems
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 2016
- Accession Number
- AD1006903
Entities
People
- Pavlo Krokhmal
Organizations
- University of Iowa