On the strength of relaxations of multidimensional knapsack problems

Branch-and-bound algorithms for integer programming problems typically employ bounds derived from well-known relaxations, such as the Lagrangian, surrogate, or composite relaxations. Although the bounds derived from these relaxations are stronger than the bound obtained from the linear programming relaxation (LPR), in the case of multidimensional knapsack problems, i.e., integer programming problems with nonnegative objective-function and constraint coefficients, the improvement in the bound that can be realized using these relaxations is limited. In particular, we show that the improvement in the quality of the bound using any of these relaxations cannot exceed the magnitude of the largest coefficient in the objective function, nor can it exceed one-half of the optimal objective-function value of LPR. This implies, for example, that for those problem classes in which all of the objective-function coefficients are equal to 1, the bound derived from the surrogate relaxation cannot be better than the bound obtained by simply rounding the LPR bound. Awareness of these properties is important in the development of algorithms, since this class of problems subsumes many well-known integer programming problems.