Search

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.

Location-allocation problems involve the selection of locations that will be used as sources to satisfy a demand at various destinations. Associated with each potential source is a capacity limitation on output and a cost function which is broken down into a fixed charge plus an output dependent variable cost. Linear distribution costs comprise the remaining part of the total system cost. Configuration constraints which rule that specific source combinations are infeasible may be included for consideration. A solution procedure is presented that finds the minimal cost solution. The procedure utilizes a new enumerative search scheme in conjunction with adaptive bounds on the fixed costs, and constraints based on the dual variables to reduce the feasible solution set to a manageable size. For each of the small number of enumerated source configurations that pass all fixed cost and duality tests, a transportation problem is optimized to determine the minimum cost allocation. An experimental computer...