Optimization Online


Solving bilevel combinatorial optimization as bilinear min-max optimization via a branch-and-cut algorithm

Artur Alves Pessoa(artur***at***producao.uff.br )
Michael Poss(michael.poss***at***hds.utc.fr)
Marcos Costa Roboredo(marcos.roboredo***at***ime.uerj.br)

Abstract: In this paper, we propose a generic branch-and -cut algorithm for a special class of bi-level combinatorial optimization problems. Namely, we study such problems that can be reformulated as bilinear min-max combinatorial optimization problems. We show that the reformulation can be efficiently solved by a branch-and-cut algorithm whose cuts represent the inner maximization feasibility set. The algorithm generalizes a method developed recently by Roboredo and Pessoa for two particular bi-level problems. In addition, we apply the algorithm on the r-Interdiction Median Problem with Forti cation (RIMF). The RIMF considers sets of facilities and customers where each customer is served by the nearest facility unless the facility is interdicted and not forti ed. The objective is to minimize the total weighted distance by fortifying q facilities knowing that r facilities will be interdicted. Our numerical results show that our method is more suitable on large instances than the best exact method found in literature.

Keywords: Integer programming, Min-max problems, Bilevel Problems, r-Interdiction Median Problem with fortification

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 10/01/2014
Entry Accepted: 10/02/2014
Entry Last Modified: 10/01/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