A Study of Alternative Relaxation Approaches for a Manpower Planning Problem.

摘要

This paper examines a variety of relaxation strategies for zero-one integer programming problems, containing from 54 to 2, 683 variables, that arise in manpower planning applications. These strategies are compared by a primal criterion, which emphasizes the ability to obtain high quality feasible solutions. This contrasts with the usual dual criterion for comparing relaxations, which emphasizes objective function bounds obtained from solutions that are generally not feasible. The changed emphasis requires a change in the use of relaxations, which may be viewed from the standpoint of generating trial solutions for heuristic programming or as a fundamental component of branch and bound. Computer tests show that a combined surrogate-Lagrangean strategy is the most effective for the problems examined followed by a pure surrogate relaxation strategy. All other approaches, including generalized Lagrangean relaxation, fared substantially worse, particularly in terms of solution quality. (Author)