Revisiting surrogate relaxation for the multidimensional knapsack problem

Trivikram Dokka; Adam N. Letchford; M. Hasan Mansoor

doi:10.1016/j.orl.2022.10.003

Revisiting surrogate relaxation for the multidimensional knapsack problem

Trivikram Dokka
, Adam N. Letchford
, M. Hasan Mansoor

Queen's Management School, Belfast
Lancaster University

Research output: Contribution to journal › Article › peer-review

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. © 2022 The Author(s)

Original language	English
Pages (from-to)	674 – 678
Journal	Operations Research Letters
Volume	50
Issue number	6
Early online date	19 Oct 2022
DOIs	https://doi.org/10.1016/j.orl.2022.10.003
Publication status	Published - 1 Nov 2022
Externally published	Yes

Keywords

Combinatorial optimization
Subroutines
Computing time
Integer Program- ming
Knapsack problems
Multidimensional knapsack problems
Problem instances
Surrogate relaxation
Upper Bound
Integer programming

Access to Document

10.1016/j.orl.2022.10.003Licence: CC BY

Cite this

@article{fee3502237894663b58fb4d5e4559322,

title = "Revisiting surrogate relaxation for the multidimensional knapsack problem",

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. {\textcopyright} 2022 The Author(s)",

keywords = "Combinatorial optimization, Subroutines, Computing time, Integer Program- ming, Knapsack problems, Multidimensional knapsack problems, Problem instances, Surrogate relaxation, Upper Bound, Integer programming",

author = "Trivikram Dokka and Letchford, \{Adam N.\} and Mansoor, \{M. Hasan\}",

note = "Cited by: 3; All Open Access, Hybrid Gold Open Access",

year = "2022",

month = nov,

day = "1",

doi = "10.1016/j.orl.2022.10.003",

language = "English",

volume = "50",

pages = "674 – 678",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier BV",

number = "6",

}

TY - JOUR

T1 - Revisiting surrogate relaxation for the multidimensional knapsack problem

AU - Dokka, Trivikram

AU - Letchford, Adam N.

AU - Mansoor, M. Hasan

N1 - Cited by: 3; All Open Access, Hybrid Gold Open Access

PY - 2022/11/1

Y1 - 2022/11/1

N2 - 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. © 2022 The Author(s)

AB - 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. © 2022 The Author(s)

KW - Combinatorial optimization

KW - Subroutines

KW - Computing time

KW - Integer Program- ming

KW - Knapsack problems

KW - Multidimensional knapsack problems

KW - Problem instances

KW - Surrogate relaxation

KW - Upper Bound

KW - Integer programming

U2 - 10.1016/j.orl.2022.10.003

DO - 10.1016/j.orl.2022.10.003

M3 - Article

SN - 0167-6377

VL - 50

SP - 674

EP - 678

JO - Operations Research Letters

JF - Operations Research Letters

IS - 6

ER -

Revisiting surrogate relaxation for the multidimensional knapsack problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this