Solving the Multiscenario Max-Min Knapsack Problem Exactly with Column Generation and Branch-and-Bound
Joint Authors
Alves, Cláudio
Valério de Carvalho, José M.
Pinto, Telmo
Mansi, Raïd
Source
Mathematical Problems in Engineering
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-11, 11 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-02-23
Country of Publication
Egypt
No. of Pages
11
Main Subjects
Abstract EN
Despite other variants of the standard knapsack problem, very few solution approaches have beendevised for the multiscenario max-min knapsack problem.
The problem consists in finding the subsetof items whose total profit is maximized under the worst possible scenario.
In this paper, we describean exact solution method based on column generation and branch-and-bound for this problem.
Ourapproach relies on a reformulation of the standard compact integer programming model based on theDantzig-Wolfe decomposition principle.
The resulting model is potentially stronger than the originalone since the corresponding pricing subproblem does not have the integrality property.
The details ofthe reformulation are presented and analysed together with those concerning the column generationand branch-and-bound procedures.
To evaluate the performance of our algorithm, we conducted extensive computational experimentson large scale benchmark instances, and we compared our results with other state-of-the-artapproaches under similar circumstances.
We focused in particular on different relevant aspects thatallow an objective evaluation of the efficacy of our approach.
From different standpoints, the branch-and-price algorithm proved to outperform the other state-of-the-art methods described so far in theliterature.
American Psychological Association (APA)
Pinto, Telmo& Alves, Cláudio& Mansi, Raïd& Valério de Carvalho, José M.. 2015. Solving the Multiscenario Max-Min Knapsack Problem Exactly with Column Generation and Branch-and-Bound. Mathematical Problems in Engineering،Vol. 2015, no. 2015, pp.1-11.
https://search.emarefa.net/detail/BIM-1073851
Modern Language Association (MLA)
Pinto, Telmo…[et al.]. Solving the Multiscenario Max-Min Knapsack Problem Exactly with Column Generation and Branch-and-Bound. Mathematical Problems in Engineering No. 2015 (2015), pp.1-11.
https://search.emarefa.net/detail/BIM-1073851
American Medical Association (AMA)
Pinto, Telmo& Alves, Cláudio& Mansi, Raïd& Valério de Carvalho, José M.. Solving the Multiscenario Max-Min Knapsack Problem Exactly with Column Generation and Branch-and-Bound. Mathematical Problems in Engineering. 2015. Vol. 2015, no. 2015, pp.1-11.
https://search.emarefa.net/detail/BIM-1073851
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1073851