A Branch-and-Cut Approach for a Generic Multiple-Product, Assembly-System Design Problem

This paper presents two new models to deal with different tooling requirements in the generic multiple-product assembly-system design (MPASD) problem and proposes a new branch-and-cut solution approach, which adds cuts at each node in the search tree. It employs the facet generation procedure (FGP) to generate facets of underlying knapsack polytopes. In addition, it uses the FGP in a new way to generate additional cuts and incorporates two new methods that exploit special structures of the MPASD problem to generate cuts. One new method is based on a principle that can be applied to solve generic 0-1 problems by exploiting embedded integral polytopes. The approach includes new heuristic and pre-processing methods, which are applied at the root node to manage the size of each instance. This paper establishes benchmarks for MPASD through an experiment in which the approach outperformed IBM's Optimization Subroutine Library (OSL), a commercially available solver.