Optimization Online


Solving Bilevel Mixed Integer Program by Reformulations and Decomposition

Bo Zeng(bzeng***at***usf.edu)
Yu An(yan2***at***mail.usf.edu)

Abstract: In this paper, we study bilevel mixed integer programming (MIP) problem and present a novel computing scheme based on reformulations and decomposition strategy. By converting bilevel MIP into a constrained mathematical program, we present its single-level reformulations that are friendly to perform analysis and build insights. Then, we develop a decomposition algorithm based on column-and-constraint generation method, which converges to the optimal value within nite operations. A preliminary computational study on randomly generated instances is presented, which demonstrates that the developed computing scheme has a superior capacity over existing methods. As it is generally applicable, easy-to-use and computationally strong, we believe that this solution method makes an important progress in solving challenging bilevel MIP problem.

Keywords: bilevel optimization, mixed integer programming, reformulation, decomposition algorithm

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

Category 2: Complementarity and Variational Inequalities


Download: [PDF]

Entry Submitted: 07/22/2014
Entry Accepted: 07/22/2014
Entry Last Modified: 07/22/2014

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