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 Lagran gian, 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 k napsack 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 par ticular, we show that the improvement in the quality of the bound usin g any of these relaxations cannot exceed the magnitude of the largest coefficient in the objective function, nor can it exceed one-half of t he 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 rel axation cannot be better than the bound obtained by simply rounding th e LPR bound. Awareness of these properties is important in the develop ment of algorithms, since this class of problems subsumes many well-kn own integer programming problems.