It has been well documented that assemble-to-order (ATO) problems are difficult to solve, but that certain heuristics can perform well in practice. We develop a new primal-dual framework that extends the standard approximate complementary slackness (ACS) conditions, providing a systematic way to establishing worst-case approximation guarantees for a diverse set of ATO heuristic policies. In particular, our approach suggests a structural limitation on the performance of the class of newsvendor decomposition heuristics; we establish an asymptotically tight approximation guarantee that grows with the maximum degree of any product node in the ATO structure. We also leverage primal-dual analysis to develop a different heuristic which combines LP-rounding with a stochastic subgradient algorithm. We establish 1.8 approximation factor guarantee for this heuristic, which does not depend on the ATO structure. In addition to providing worst-case approximation bounds, our numerical results suggest that the latter heuristic outperforms newsvendor heuristics in terms of both the worst-case and average performance.
More generally, the presented primal-dual framework is readily applicable to general integer programs beyond the ATO problem, and could yield development of performance bounds for heuristics in other challenging Operations Management problems.
Venue: 01.10.011 (Garching)
Date: Monday 12th March, 2018 (starting at 13:00)