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


Text available via DOI:

View graph of relations

Revisiting surrogate relaxation for the multidimensional knapsack problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

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


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.