Skip to main content
Article
The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem
SIAM Journal on Optimization
  • Lizhi Wang, Iowa State University
  • Pan Xu, University of Maryland at College Park
Document Type
Article
Publication Version
Published Version
Publication Date
1-1-2017
DOI
10.1137/15M1051592
Abstract

This paper presents an exact algorithm for the bilevel integer linear programming (BILP) problem. The proposed algorithm, which we call the watermelon algorithm, uses a multiway disjunction cut to remove bilevel infeasible solutions from the search space, which was motivated by how watermelon seeds can be carved out by a scoop. Serving as the scoop, a polyhedron is designed to enclose as many bilevel infeasible solutions as possible, and then the complement of this polyhedron is applied to the search space as a multiway disjunction cut in a branch-and-bound framework. We have proved that the watermelon algorithm is able to solve all BILP instances finitely and correctly, providing either a global optimal solution or a certificate of infeasibility or unboundedness. Computational experiment results on two sets of small- to medium-sized instances suggest that the watermelon algorithm could be significantly more efficient than previous branch-and-bound based BILP algorithms.

Comments

This article is published as Wang, Lizhi, and Pan Xu. "The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem." SIAM Journal on Optimization 27, no. 3 (2017): 1403-1430. doi: 10.1137/15M1051592. Posted with permission.

Copyright Owner
Society for Industrial and Applied Mathematics
Language
en
File Format
application/pdf
Citation Information
Lizhi Wang and Pan Xu. "The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem" SIAM Journal on Optimization Vol. 27 Iss. 3 (2017) p. 1403 - 1430
Available at: http://works.bepress.com/lizhi_wang/11/