Home > Research > Publications & Outputs > Revisiting surrogate relaxation for the multidi...

Associated organisational unit

Electronic data

  • mkp-surrogate

    Accepted author manuscript, 284 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

Revisiting surrogate relaxation for the multidimensional knapsack problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
<mark>Journal publication date</mark>30/11/2022
<mark>Journal</mark>Operations Research Letters
Issue number6
Volume50
Number of pages5
Pages (from-to)674-678
Publication StatusPublished
Early online date24/10/22
<mark>Original language</mark>English

Abstract

The multidimensional knapsack problem (MKP) is a classic problem in combinatorial optimisation. Several authors have proposed to use surrogate relaxation to compute upper bounds for the MKP. In their papers, the surrogate dual is solved heuristically. We show that, using a modern dual simplex solver as a subroutine, one can solve the surrogate dual exactly in reasonable computing times. On the other hand, the resulting upper bound tends to be strong only for relatively small MKP instances.