Benders decomposition with integer subproblem

被引:14
作者
Fakhri, Ashkan [1 ,2 ]
Ghatee, Mehdi [1 ,2 ]
Fragkogios, Antonios [3 ]
Saharidis, Georgios K. D. [3 ]
机构
[1] Amirkabir Univ Technol, Dept Math & Comp Sci, 424 Hafez Ave, Tehran 158754413, Iran
[2] Amirkabir Univ Technol, Intelligent Transportat Res Inst, Tehran, Iran
[3] Univ Thessaly, Dept Mech Engn, Polytech Sch, Bolos 38834, Greece
关键词
Benders decomposition; Integer subproblem; Branch and cut; Local cuts; Global cuts; STOCHASTIC PROGRAMS; ALGORITHM; CUTS; OPTIMIZATION;
D O I
10.1016/j.eswa.2017.07.017
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The application of Benders decomposition method to a problem might result in a subproblem including integer variables. In this case, it is not able to apply the classical Benders algorithm. In this study we present a Branch-and-Cut algorithm, which introduces the notion of "Local Cuts" as well as "Global Cuts". The integrality constraints of the subproblem are relaxed and the relaxed problem is solved in a branch-and-bound framework, where in each node, the Benders algorithm is applied between the master problem and the relaxed subproblem. Benders cuts generated in a node of the branch-and bound tree are proved to be valid for all its descendants, but they are not necessarily valid for the non-descendant nodes. These cuts, referred to as local cuts, can be used to warm start the master problem of each descendant node, thus leading to better initial bounds. Furthermore, a novel way is presented for defining the local cuts in a general form. This general form is in fact a function of the subproblems' variables and enables us to reuse the generated (local) cuts in the whole tree by updating some values of the function. The performance of the proposed algorithm is tested on the classical Capacitated Fixed Charge Multiple Knapsack Problem (CFCMKP). (C) 2017 Elsevier Ltd. All rights reserved.
引用
收藏
页码:20 / 30
页数:11
相关论文
共 50 条
[11]   Logic-based benders decomposition for wildfire suppression [J].
Harris, Mitchell G. ;
Forbes, Michael A. ;
Taimre, Thomas .
COMPUTERS & OPERATIONS RESEARCH, 2023, 160
[12]   Benders decomposition for bi-objective linear programs [J].
Raith, Andrea ;
Lusby, Richard ;
Yousefkhan, Ali Akbar Sohrabi .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2025, 322 (02) :376-400
[13]   A modification of Benders' decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse [J].
Sherali, HD ;
Fraticelli, BMP .
JOURNAL OF GLOBAL OPTIMIZATION, 2002, 22 (1-4) :319-342
[14]   The Benders decomposition algorithm: A literature review [J].
Rahmaniani, Ragheb ;
Crainic, Teodor Gabriel ;
Gendreau, Michel ;
Rei, Walter .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 259 (03) :801-817
[15]   Accelerating Benders Decomposition by Local Branching [J].
Rei, Walter ;
Cordeau, Jean-Francois ;
Gendreau, Michel ;
Soriano, Patrick .
INFORMS JOURNAL ON COMPUTING, 2009, 21 (02) :333-345
[16]   A Benders decomposition approach for a combined heat and power economic dispatch [J].
Abdolmohammadi, Hamid Reza ;
Kazemi, Ahad .
ENERGY CONVERSION AND MANAGEMENT, 2013, 71 :21-31
[17]   A framework for generalized Benders' decomposition and its application to multilevel optimization [J].
Bolusani, Suresh ;
Ralphs, Ted K. .
MATHEMATICAL PROGRAMMING, 2022, 196 (1-2) :389-426
[18]   Distribution Systems Reconfiguration Based on OPF Using Benders Decomposition [J].
Khodr, H. M. ;
Martinez-Crespo, J. ;
Matos, M. A. ;
Pereira, J. .
IEEE TRANSACTIONS ON POWER DELIVERY, 2009, 24 (04) :2166-2176
[19]   Computationally efficient solution of mixed integer model predictive control problems via machine learning aided Benders Decomposition [J].
Mitrai, Ilias ;
Daoutidis, Prodromos .
JOURNAL OF PROCESS CONTROL, 2024, 137
[20]   Benders decomposition to accelerate determination of optimal railway intervention programmes [J].
Mehranfar, Hamed ;
Adey, Bryan T. ;
Burkhalter, Marcel ;
Moghtadernejad, Saviz .
INFRASTRUCTURE ASSET MANAGEMENT, 2023, 10 (04) :171-188