Skip to Main content Skip to Navigation
Journal articles

Hybrid approaches for the two-scenario max-min knapsack problem

Abstract : In this paper, we deal with the two-scenario max-min knapsack (MNK) problem. First, we consider several formulations of MNK as a mixed integer programming problem. Then, we propose a hybrid method as an alternative to solve the MNK exactly. The approach combines relaxation technique and the temporary setting of variables to improve iteratively two sequences of upper and lower bounds. More precisely, pseudocuts are added to the problem to strengthen the bounds and reduce the gap between the best lower bound and the best upper bound. The algorithm stops when the proof of the optimality of the best solution is found. We also use a reduction technique to set some variables definitively at their optimal values. Numerical experiments demonstrate the robustness of the approach. In particular, our algorithm is efficient to solve large and correlated instances of MNK.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03723733
Contributor : Christophe Wilbaut Connect in order to contact the contributor
Submitted on : Friday, July 15, 2022 - 10:38:09 AM
Last modification on : Thursday, July 21, 2022 - 3:54:55 AM

File

Hanafi et al. - 2012 - Hybrid ...
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Saïd Hanafi, Raïd Mansi, Christophe Wilbaut, Arnaud Fréville. Hybrid approaches for the two-scenario max-min knapsack problem. International Transactions in Operational Research, Wiley, 2012, 19, pp.353 - 378. ⟨10.1111/j.1475-3995.2011.00836.x⟩. ⟨hal-03723733⟩

Share

Metrics

Record views

1

Files downloads

1