We study a class of bilevel binary linear programs with lower level variables in the upper-level constraints. Under certain assumptions, we prove that the problem can be reformulated as a single-level binary linear program, and propose a finitely terminating cut generation algorithm to solve it. We then relax the assumptions by means of a general row-and-column generation framework. As an illustrative application we consider the minimum zero forcing set problem, a variant of the dominating set problem, and prove that it can be written as a binary linear bilevel program. Finally, we perform some numerical experiments to showcase the practical applicability of our methods.
Article
View Bilevel mixed-integer linear programs and the zero forcing set