A Flexible Enumeration Scheme for Zero-One Programming

Abstract

Each of the main enumerative methods for zero-one programming has a drawback: the branch-and-bound (multi-branch) approach may require an inordinate amount of storage capacity and the backtrack implicit-enumeration (single-branch) approach circumvents this storage problem only by restricting the flexibility of the search. This paper outlines an implicit-enumeration scheme that, while maintaining a low storage requirement, allows the same flexibility in backward branching (backtracking is no longer mandatory) as we commonly have in forward branching. Preliminary computational results are presented.