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

Trivikram Dokka, Adam Letchford, Hasan Mansoor

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)530-534
Number of pages5
JournalOperations Research Letters
Volume49
Issue number4
Early online date31 May 2021
DOIs
Publication statusPublished - Jul 2021

Fingerprint

Dive into the research topics of 'On the complexity of surrogate and group relaxation for integer linear programs'. Together they form a unique fingerprint.

Cite this