PhD Research Seminar: Analysis of Bilivel Optimization Problems with Incomplete Information and Learning

Where: https://zoom.us/j/442268392

When: June 28, 18:10–19:30 

Topic: Analysis of Bilivel Optimization Problems with Incomplete Information and Learning
Speaker: Sergey Ketkov, third-year PhD student, HSE Nizhny Novgorod

In this study we consider a class of network routing problems where either the structure of the network or precise costs of specified arcs are subject to uncertainty. In general, such problems can be formalized as bilevel (or multi-level) optimization problems, where a leader picks some path in the network, while a follower sets the costs of arcs so as to prevent (at maximally possible extent) the leader's movement through the network.

In the first part, we assume that the follower learns the structure of the network and the exact costs of particular arcs by observing the leader's decisions. In the second part, we suppose that the structure of the network is determinisitic, but the arc costs are subject to distributional uncertainty. In other words, the leader attempts to minimize its expected loss against the worst-case possible distribution of the cost vector, which is deemed possible under the existing information.

The goal of the study is to construct exact and approximate formulations for the outlined optimization problems that can be solved rather effectively using off-the-shelf mixed-integer programming (MIP) solvers. Furthermore, we expect that the obtained formulations can be practically relevant with respect to some classes of network interdiction and sensor allocation problems.