An enhanced branch-and-bound algorithm for bilevel integer linear programming

Shaonan Liu, Mingzheng Wang, Nan Kong and Xiangpei Hu

European Journal of Operational Research, 2021, vol. 291, issue 2, 661-679

Abstract: Bilevel integer linear programming (BILP) problems have been studied for decades. Many exact algorithms have been proposed in recent years for small- or medium-sized instances. However, few of these algorithms were shown to be efficient on large-sized instances. In this paper, we present an enhanced branch-and-bound algorithm for a class of BILP problems, which can discard a subspace from the search space in each iteration larger than that in a benchmark branch-and-bound algorithm. The corresponding enhanced branching rule can efficiently slow down the creation of new node problems so as to significantly reduce the computation time. Our scheme may be suboptimal if the lower-level problem is not unique optimal as the enhanced branching rule may discard bilevel feasible solutions that may turn out to be optimal to the bilevel programming. We present computational studies to evaluate the algorithm speedup and solution quality of our algorithm, compared with state-of-the-art algorithms from the literature on a large testbed of general BILP instances, some of which are still unsolved. The computational results show that our enhanced branching rule can achieve significant speedup on the benchmark branching rule with satisfying solution quality. In particular, our algorithm shows superior performance on large-sized BILP instances with a relatively complex lower-level problem.

Keywords: Integer programming; Bilevel programming; Branch and bound; Enhanced branching (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720308614
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:291:y:2021:i:2:p:661-679

DOI: 10.1016/j.ejor.2020.10.002

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().