Benders decomposition with integer subproblem. (15th December 2017)

• Record Type: Journal Article
• Authors: Fakhri, Ashkan; Ghatee, Mehdi; Fragkogios, Antonios; Saharidis, Georgios K.D.
• Is Part Of: Expert systems with applications. Volume 89(2017)
• Page Start: 20
• Page End: 30
• Publication Date: 2017-12-15
• Subjects: Benders decomposition -- Integer subproblem -- Branch and cut -- Local cuts -- Global cuts; CFCMKP capacitated fixed charge multiple knapsack problem -- B&C-LC Branch-and-Cut algorithm with local cuts -- B&C-NotLC Branch-and-Cut algorithm without Local cuts -- A-RPSP(k) Augmented Relaxed Primal Subproblem of node k -- A-RDSP(k) Augmented Relaxed Dual Subproblem of node k -- A-RMP(k) Augmented Relaxed Master Problem of node k; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2017.07.017
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A Branch-and-Cut algorithm using Benders decomposition method is proposed. The algorithm is applied in case of integer subproblem. " Local" and " Global Cuts " are used to warm start the master problem in each node. The validity of the cuts is mathematically proved. A case study tests the efficiency of the algorithm. Abstract: 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).