Repetitive Combinatorial Optimization with Learning

University Of Pittsburgh, Pittsburgh PA

Investigators

Abstract

This award provides funding for the development of solution methods for repetitive stochastic combinatorial optimization problems with parameter uncertainties that can only be resolved through active learning. The focus will be on a class of combinatorial stochastic semi-bandit problems (CSSP) where several instances of a given combinatorial formulation must be solved sequentially through time, with the objective of minimizing cumulative cost, when there is initial uncertainty about the instances. From a methodological point of view, CSSPs introduce new questions to the well-known exploration vs. exploitation paradigm: in addition to answering the usual non-trivial question of when to explore/exploit, in CSSP the questions of what to explore/exploit and how to do so are also non-trivial. Solution techniques will combine elements from statistical learning and combinatorial optimization under uncertainty. A significant portion of the project will be devoted to study an interesting new class of optimization problems that provide answers to some of the fundamental questions in this research. Complexity of such optimization problems, as well as its practical solvability, will be addressed and practical solution methods will be embedded in proposed algorithms for CSSPs. The resulting algorithms, which will be tested extensively, should integrate the various results to design efficient and implementable policies. If successful, the results of this research will provide an attractive approach to addressing data and parameter uncertainty in OR practice. The focus on computationally implementable policies will likely result in practical approaches for a varied range of applications in areas such as delivery of humanitarian aid, weapon target assignment, network reliability and online advertisement. The proposed policies will likely lead to the development of new questions and methods in both combinatorial optimization and learning theory.