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

Trivikram Dokka; Adam Letchford; Hasan  Mansoor

doi:10.1016/j.orl.2021.05.011

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

Trivikram Dokka, Adam Letchford, Hasan Mansoor

Queen's Management School

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

5 Downloads (Pure)

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 the
integer and 0-1 knapsack problems, and strongly NP-hard for the set packing problem.

Original language	English
Pages (from-to)	530-534
Number of pages	5
Journal	Operations Research Letters
Volume	49
Issue number	4
Early online date	31 May 2021
DOIs	https://doi.org/10.1016/j.orl.2021.05.011
Publication status	Published - Jul 2021

Access to Document

10.1016/j.orl.2021.05.011Licence: Unspecified

On the complexity of surrogate and group relaxation for integer linear programs
Copyright 2021 Elsevier. This manuscript is distributed under a Creative Commons Attribution-NonCommercial-NoDerivs License (https://creativecommons.org/licenses/by-nc-nd/4.0/), which permits distribution and reproduction for non-commercial purposes, provided the author and source are cited.
Accepted author manuscript, 296 KBLicence: CC BY-NC-ND

Cite this

@article{0f35db21f374412f94ff93cbc8d41c79,

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.",

author = "Trivikram Dokka and Adam Letchford and Hasan Mansoor",

year = "2021",

month = jul,

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",

}

TY - JOUR

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

AU - Dokka, Trivikram

AU - Letchford, Adam

AU - Mansoor, Hasan

PY - 2021/7

Y1 - 2021/7

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.

U2 - 10.1016/j.orl.2021.05.011

DO - 10.1016/j.orl.2021.05.011

M3 - Article

VL - 49

SP - 530

EP - 534

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 4

ER -

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

Abstract

Access to Document

Fingerprint

Cite this