4 papers
On the Complexity of Bilevel Linear and Quadratic Programs in Fixed Dimensions
Sergey S. Ketkov, Oleg A. Prokopyev
It is well-known that general bilevel linear programs (BLPs) are strongly -hard, even when the leader's and the follower's objective functions are exact opposites. However, the…
On Big-M Reformulations of Bilevel Linear Programs: Hardness of A Posteriori Verification
Sergey S. Ketkov, Oleg A. Prokopyev
A standard approach to solving optimistic bilevel linear programs (BLPs) is to replace the lower-level problem with its Karush-Kuhn-Tucker (KKT) optimality conditions and reformula…
Data-driven interdiction with asymmetric cost uncertainty: a distributionally robust optimization approach
Sergey S. Ketkov, Oleg A. Prokopyev
We consider a class of stochastic interdiction games between an upper-level decision-maker (the leader) and a lower-level decision-maker (the follower), where uncertainty lies in t…
On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
Sergey S. Ketkov, Oleg A. Prokopyev
In this study, we consider a class of linear matroid interdiction problems, where the feasible sets for the upper-level decision-maker (referred to as a leader) and the lower-level…