×

zbMATH — the first resource for mathematics

A branch-and-cut approach for a generic multiple-product, assembly-system design problem. (English) Zbl 1239.90080
Summary: We present 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.

MSC:
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B35 Deterministic scheduling theory in operations research
Software:
OSL
PDF BibTeX XML Cite
Full Text: DOI