  


Bilevel mixedinteger linear programs and the zero forcing set
PierreLouis Poirion(poirionlix.polytechnique.fr) Abstract: We study a class of bilevel binary linear programs with lower level variables in the upperlevel constraints. Under certain assumptions, we prove that the problem can be reformulated as a singlelevel binary linear program, and propose a finitely terminating cut generation algorithm to solve it. We then relax the assumptions by means of a general rowandcolumn 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 ) Citation: Download: [PDF] Entry Submitted: 11/22/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  