13 citations · 22 across the 8 of their papers we have counts for
8 papers
On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs
Sergey S. Ketkov, Oleg A. Prokopyev
Exact algorithms for solving mixed-integer bilevel linear programs (MIBLPs) typically rely on sequences of lower and upper bounds that converge to the optimal value. These procedur…
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…
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…
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…
Fractional 0-1 programming and submodularity
Shaoning Han, Andres Gomez, Oleg A Prokopyev
In this note we study multiple-ratio fractional 0--1 programs, a broad class of NP-hard combinatorial optimization problems. In particular, under some relatively mild assumptions w…
An approach to the distributionally robust shortest path problem
Sergey S. Ketkov, Oleg A. Prokopyev, Evgenii P. Burashnikov
In this study we consider the shortest path problem, where the arc costs are subject to distributional uncertainty. Basically, the decision-maker attempts to minimize her worst-cas…
On Greedy and Strategic Evaders in Sequential Interdiction Settings with Incomplete Information
Sergey S. Ketkov, Oleg A. Prokopyev
We consider a class of sequential network interdiction problem settings where the interdictor has incomplete initial information about the network while the evader has complete kno…