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

Trivikram Dokka; Adam N. Letchford; M. 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 N. Letchford
, M. Hasan Mansoor

Queen's Management School, Belfast
Lancaster University

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

Crynodeb

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.

Iaith wreiddiol	Saesneg
Tudalennau (o-i)	530-534
Nifer y tudalennau	5
Cyfnodolyn	Operations Research Letters
Cyfrol	49
Rhif cyhoeddi	4
Dyddiad ar-lein cynnar	31 Mai 2021
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1016/j.orl.2021.05.011
Statws	Cyhoeddwyd - 1 Gorff 2021
Cyhoeddwyd yn allanol	Ie

Mynediad at Ddogfen

10.1016/j.orl.2021.05.011

https://www.sciencedirect.com/science/article/pii/S016763772100081X

Dyfynnu hyn

@article{feed908cad2943f0887ddb0e30518549,

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 the integer 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 Letchford, \{Adam N.\} and Mansoor, \{M. Hasan\}",

year = "2021",

month = jul,

day = "1",

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

language = "English",

volume = "49",

pages = "530--534",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier BV",

number = "4",

}

TY - JOUR

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

AU - Dokka, Trivikram

AU - Letchford, Adam N.

AU - Mansoor, M. Hasan

PY - 2021/7/1

Y1 - 2021/7/1

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 the integer 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 the integer 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 - Article

SN - 0167-6377

VL - 49

SP - 530

EP - 534

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

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

Crynodeb

Mynediad at Ddogfen

Ôl bys

Dyfynnu hyn