Optimization Online


Bilevel mixed-integer linear programs and the zero forcing set

Pierre-Louis Poirion(poirion***at***lix.polytechnique.fr)
Sonia Toubaline(toubaline***at***lix.polytechnique.fr)
Claudia D'Ambrosio(dambrosio***at***lix.polytechnique.fr)
Leo Liberti(liberti***at***lix.polytechnique.fr)

Abstract: 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.

Keywords: BIlevel programming; zero forcing set

Category 1: Integer Programming (Other )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 11/22/2015
Entry Accepted: 11/22/2015
Entry Last Modified: 11/22/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society