期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 267, 期 1, 页码 40-51出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2017.11.043
关键词
(O) Combinatorial optimization; Bilevel optimization; Interdiction problems; Mixed-integer programming; Heuristics
资金
- Vienna Science and Technology Fund (WWTF) [ICT15-014]
- MIUR, Italy (PRIN project)
- Austrian Research Fund (FWF) [P 26755-N19]
- Austrian Science Fund (FWF) [P26755] Funding Source: Austrian Science Fund (FWF)
We consider a subfamily of mixed-integer linear bilevel problems that we call Generalized Interdiction Problems. This class of problems includes, among others, the widely-studied interdiction problems, i.e., zero-sum Stackelberg games where two players (called the leader and the follower) share a set of items, and the leader can interdict the usage of certain items by the follower: Problems of this type can be modeled as Mixed-Integer Nonlinear Programming problems, whose exact solution can be very hard. In this paper we propose a new heuristic scheme based on a single-level and compact mixed-integer linear programming reformulation of the problem obtained by relaxing the integrality of the follower variables. A distinguished feature of our method is that general-purpose mixed-integer cutting planes for the follower problem are exploited, on the fly, to dynamically improve the reformulation. The resulting heuristic algorithm proved very effective on a large number of test instances, often providing an (almost) optimal solution within very short computing times. (C) 2017 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据