Consecutive Optimizers for a Partitioning Problem with Applications to Optimal Inventory Groupings for Joint Replenishment

A. K. Chakravarty, J. B. Orlin, U. G. Rothblum

Operations Research · 1985 · Volume 33 · Issue 4

Abstract

We consider several subclasses of the problem of grouping n items (indexed 1, 2, …, n ) into m subsets so as to minimize the function g ( S 1 , …, S m ). In general, these problems are very difficult to solve to optimality, even for the case m = 2. We provide several sufficient conditions on g (·) that guarantee that there is an optimum partition in which each subset consists of consecutive integers (or else the partition S 1 , …, S m satisfies a more general condition called “semiconsecutiveness”). Moreover, by restricting attention to “consecutive” (or “semiconsecutive”) partitions, we can solve the partition problem in polynomial time for small values of m . If, in addition, g is symmetric, then the partition problem is solvable in purely polynomial time. We apply these results to generalizations of a problem in inventory groupings considered by the authors in a previous paper. We also relate the results to the Neyman-Pearson lemma in statistical hypothesis testing and to a graph partitioning problem of Barnes and Hoffman.

Keywords

334 partitioning items into subgroups, 625 optimal inventory groupings

Enable JavaScript for citation tools and additional paper interactions.