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.