Home > Research > Publications & Outputs > On the complexity of surrogate and group relaxa...

Research

Associated organisational unit

Electronic data

  • relaxation-complexity

    Rights statement: This is the author’s version of a work that was accepted for publication in Operations Research Letters. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Operations Research Letters, 49, 4, 2021 DOI: 10.1016/j.orl.2021.05.011

    Accepted author manuscript, 296 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

On the complexity of surrogate and group relaxation for integer linear programs

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

Published

Standard

On the complexity of surrogate and group relaxation for integer linear programs. / Dokka, Trivikram; Letchford, Adam; Mansoor, Hasan.
In: Operations Research Letters, Vol. 49, No. 4, 31.07.2021, p. 530-534.

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

Harvard

Dokka, T, Letchford, A & Mansoor, H 2021, 'On the complexity of surrogate and group relaxation for integer linear programs', Operations Research Letters, vol. 49, no. 4, pp. 530-534. https://doi.org/10.1016/j.orl.2021.05.011

APA

Dokka, T., Letchford, A., & Mansoor, H. (2021). On the complexity of surrogate and group relaxation for integer linear programs. Operations Research Letters, 49(4), 530-534. https://doi.org/10.1016/j.orl.2021.05.011

Vancouver

Dokka T, Letchford A, Mansoor H. On the complexity of surrogate and group relaxation for integer linear programs. Operations Research Letters. 2021 Jul 31;49(4):530-534. Epub 2021 May 31. doi: 10.1016/j.orl.2021.05.011

Author

Dokka, Trivikram ; Letchford, Adam ; Mansoor, Hasan. / On the complexity of surrogate and group relaxation for integer linear programs. In: Operations Research Letters. 2021 ; Vol. 49, No. 4. pp. 530-534.

Bibtex

@article{955adc476e6a4805a1c900b025a923fb,
title = "On the complexity of surrogate and group relaxation for integer linear programs",
abstract = "Surrogate and group relaxation have been used to compute bounds for various integer linear programming problems. We prove that (a) when only inequalities are surrogated, the surrogate dual is NP-hard, but solvable in pseudo-polynomial time under certain conditions; (b) when equations are surrogated, the surrogate dual exhibits unusual complexity behaviour; (c) the group relaxation is NP-hard for theinteger and 0-1 knapsack problems, and strongly NP-hard for the set packing problem.",
keywords = "Integer programming, Surrogate relaxation, Group relaxation",
author = "Trivikram Dokka and Adam Letchford and Hasan Mansoor",
note = "This is the author{\textquoteright}s version of a work that was accepted for publication in Operations Research Letters. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Operations Research Letters, vol. 49, issue 4, 2021 DOI:10.1016/j.orl.2021.05.011",
year = "2021",
month = jul,
day = "31",
doi = "10.1016/j.orl.2021.05.011",
language = "English",
volume = "49",
pages = "530--534",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "4",

}

RIS

TY - JOUR

T1 - On the complexity of surrogate and group relaxation for integer linear programs

AU - Dokka, Trivikram

AU - Letchford, Adam

AU - Mansoor, Hasan

N1 - This is the author’s version of a work that was accepted for publication in Operations Research Letters. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Operations Research Letters, vol. 49, issue 4, 2021 DOI:10.1016/j.orl.2021.05.011

PY - 2021/7/31

Y1 - 2021/7/31

N2 - Surrogate and group relaxation have been used to compute bounds for various integer linear programming problems. We prove that (a) when only inequalities are surrogated, the surrogate dual is NP-hard, but solvable in pseudo-polynomial time under certain conditions; (b) when equations are surrogated, the surrogate dual exhibits unusual complexity behaviour; (c) the group relaxation is NP-hard for theinteger and 0-1 knapsack problems, and strongly NP-hard for the set packing problem.

AB - Surrogate and group relaxation have been used to compute bounds for various integer linear programming problems. We prove that (a) when only inequalities are surrogated, the surrogate dual is NP-hard, but solvable in pseudo-polynomial time under certain conditions; (b) when equations are surrogated, the surrogate dual exhibits unusual complexity behaviour; (c) the group relaxation is NP-hard for theinteger and 0-1 knapsack problems, and strongly NP-hard for the set packing problem.

KW - Integer programming

KW - Surrogate relaxation

KW - Group relaxation

U2 - 10.1016/j.orl.2021.05.011

DO - 10.1016/j.orl.2021.05.011

M3 - Journal article

VL - 49

SP - 530

EP - 534

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 4

ER -