期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 291, 期 2, 页码 661-679出版社
ELSEVIER
DOI: 10.1016/j.ejor.2020.10.002
关键词
Integer programming; Bilevel programming; Branch and bound; Enhanced branching
资金
- Key Program of the NSFC [71931009]
- General Program of the NSFC [71671023]
- National Science Foundation of US [1761022]
- Foundation for Innovative Research Groups of NSFC [71421001]
- key projects of of International Cooperation and Exchanges NSFC [72010107002]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1761022] Funding Source: National Science Foundation
In this paper, an enhanced branch-and-bound algorithm is proposed for a class of BILP problems, which can significantly reduce computation time while maintaining solution quality. Computational studies show that the enhanced branching rule achieves significant speedup and superior performance on large-sized BILP instances with complex lower-level problems.
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. (C) 2020 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据