A Bounding Minimization Problem for Primal Integer Programming

Computational experiments with the primal integer programming algorithm indicate that in many cases the optimal value of the objective function is obtained in a very few iterations but a large number of iterations are required to establish optimality; thus, an alternative proof of optimality is needed. This paper describes an algorithm for obtaining an upper bound (such an alternative) on the value of the objective function. This bound is based on the best bound obtainable from dual solutions to a class of related linear programs. Computational results illustrating the effectiveness of this bounding technique are presented.