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

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

Crynodeb

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)

Iaith wreiddiol	Saesneg
Tudalennau (o-i)	674 – 678
Cyfnodolyn	Operations Research Letters
Cyfrol	50
Rhif cyhoeddi	6
Dyddiad ar-lein cynnar	19 Hyd 2022
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1016/j.orl.2022.10.003
Statws	Cyhoeddwyd - 1 Tach 2022
Cyhoeddwyd yn allanol	Ie

Mynediad at Ddogfen

10.1016/j.orl.2022.10.003Trwydded: CC BY

Dyfynnu hyn

@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

Crynodeb

Mynediad at Ddogfen

Ôl bys

Dyfynnu hyn