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

Research

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:

Keywords

View graph of relations

Revisiting surrogate relaxation for the multidimensional knapsack problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Revisiting surrogate relaxation for the multidimensional knapsack problem. / Dokka, Trivikram; Letchford, Adam; Mansoor, Hasan.
In: Operations Research Letters, Vol. 50, No. 6, 30.11.2022, p. 674-678.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Dokka, T, Letchford, A & Mansoor, H 2022, 'Revisiting surrogate relaxation for the multidimensional knapsack problem', Operations Research Letters, vol. 50, no. 6, pp. 674-678. https://doi.org/10.1016/j.orl.2022.10.003

APA

Dokka, T., Letchford, A., & Mansoor, H. (2022). Revisiting surrogate relaxation for the multidimensional knapsack problem. Operations Research Letters, 50(6), 674-678. https://doi.org/10.1016/j.orl.2022.10.003

Vancouver

Dokka T, Letchford A, Mansoor H. Revisiting surrogate relaxation for the multidimensional knapsack problem. Operations Research Letters. 2022 Nov 30;50(6):674-678. Epub 2022 Oct 24. doi: 10.1016/j.orl.2022.10.003

Author

Dokka, Trivikram ; Letchford, Adam ; Mansoor, Hasan. / Revisiting surrogate relaxation for the multidimensional knapsack problem. In: Operations Research Letters. 2022 ; Vol. 50, No. 6. pp. 674-678.

Bibtex

@article{8ac966147c1c4429967816f7e9074882,
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.",
keywords = "integer programming, combinatorial optimisation, knapsack problems",
author = "Trivikram Dokka and Adam Letchford and Hasan Mansoor",
year = "2022",
month = nov,
day = "30",
doi = "10.1016/j.orl.2022.10.003",
language = "English",
volume = "50",
pages = "674--678",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "6",

}

RIS

TY - JOUR

T1 - Revisiting surrogate relaxation for the multidimensional knapsack problem

AU - Dokka, Trivikram

AU - Letchford, Adam

AU - Mansoor, Hasan

PY - 2022/11/30

Y1 - 2022/11/30

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.

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.

KW - integer programming

KW - combinatorial optimisation

KW - knapsack problems

U2 - 10.1016/j.orl.2022.10.003

DO - 10.1016/j.orl.2022.10.003

M3 - Journal article

VL - 50

SP - 674

EP - 678

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 6

ER -