The watermelon algorithm for the bilevel integer linear programming problem

Lizhi Wang, Pan Xu

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1403-1430
Number of pages28
JournalSIAM Journal on Optimization
Issue number3
StatePublished - 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science


  • Bilevel optimization
  • Bound
  • Branch
  • Cutting plane


Dive into the research topics of 'The watermelon algorithm for the bilevel integer linear programming problem'. Together they form a unique fingerprint.

Cite this