Title: Complexity in linear multilevel programming
| Speaker: | Noah Weninger |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract:Bilevel linear programming (BLP) is a generalization of linear programming (LP) in which a subset of the variables is constrained to be optimal for a second LP, called the lower-level problem. Multilevel linear programming (MLP) extends this further by replacing the lower-level LP with a BLP or even another MLP, up to some finite number of levels. MLP can be seen as a game-theoretic extension of LP where multiple decision makers with competing interests each have control over some subset of the variables in the problem. We discuss the computational complexity of solving MLP problems, including some recent results on the complexity of determining whether MLPs are unbounded (Rodrigues, Carvalho, and Anjos 2024). We will end with an interesting open problem about the complexity of determining unboundedness for a
special case of BLP.