A Zero-One Goal-Programming Algorithm Using Partitioning and Constraint Aggregation

This paper offers a new approach to the solution of zero-one goal-programming problems. The number of non-zero variables required to satisfy a constraint completely is used to identify the priority levels that can be completely achieved, and also determine redundant constraints and invariant decision-variables. The priority levels that are so identified form the basis for a subprogramme of completely achievable constraints. These constraints are aggregated to form a single constraint, and a set of necessary and sufficient conditions are developed to generate the optimal solution. The algorithm has been coded in Pascal and compared with the Lee and Morris algorithm. The virtual CPU time required to solve those problems tested was less than 10 per cent of that required by the Lee and Morris algorithm. The algorithm may also be useful in solving other types of zero-one formulations.