DII CGO
inicioir al DIIbuscar
fcfm
top
topleft
learning in combinatorial optimization: how and what to explore

Learning in Combinatorial Optimization: How and What to Explore?

Denis Sauré

 

We study sequential combinatorial optimization under model uncertainty. We show that for balancing the implied exploration vs exploitation trade-off it is critical to resolve the issue of what information to collect and how to do so. Our answer to these questions lies in solving an adjunct formulation, which looks for the cheapest solution-based optimality guarantee. We develop fundamental limit on performance, and develop an efficient policy implementable in real-time.