Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling

In this paper, two meta-strategies for computing lower bounds (for minimization problems) are described. Constructive (direct) methods directly calculate a bound value by relaxing a problem and solving this relaxation. Destructive improvement techniques restrict a problem by setting a maximal objective function value F and try to contradict (destruct) the feasibility of this reduced problem. In case of success, F or even F + 1 is a valid lower bound value. The fundamental properties and differences of both meta-strategies are explained by applying them to the well-known resource-constrained project scheduling problem (RCPSP). For this problem, only a few constructive bound arguments are available in the literature. We present a number of extensions and new methods as well as techniques for reducing problem data which can be exploited within the destructive improvement framework. Comprehensive numerical experiments show that the new constructive bound arguments clearly provide better bounds than the former ones and that further really significant improvements are obtained through an appropriate application of destructive improvement. (C) 1999 Elsevier Science B.V. All rights reserved.