One-completion enumerative method for zero-one integer programming

Abstract

Scope and Method of Study: This study examines the effectiveness of a one-completion enumerative algorithm for solution of zero-one integer linear programming problems. The algorithm utilizes a search tree data structure to select partial solution vectors for active processing. A one completion test is incorporated in the algorithm to determine the need for explicit enumeration of search tree branches. Five zero-one integer problems are solved via the one- completion method. These same five problems are also used to test the effectiveness of reordering problem variables with respect to objective function coefficient magnitude before beginning the one-completion procedure.

Findings and Conclusions: The one-completion algorithm used in this study was shown to be as effective as the basic Balas additive algorithm for solution of small zero-one problems. For the five problems tested, three were solved faster with the one-completion method including problem reordering. For these same five problems, reordering reduced one-completion processing time by an average of 41%.