STRUCTURED PARTITIONING PROBLEMS

In many important combinatorial optimization problems, such as bin packing, allocating customer classes to queueing facilities, vehicle routing, multi-item inventory replenishment and combined routing/inventory control, an optimal partition into groups needs to be determined for a finite collection of objects; each is characterized by a single attribute. The cost is often separable in the groups and the group cost often depends on the cardinality and some aggregate measure of the attributes, such as the sum or the maximum element. An upper bound (capacity) may be specified for the cardinality of each group and the number of groups in the partition may either be fixed or variable. The objects are indexed in nondecreasing order of their attribute values and within a given partition the groups are indexed in nondecreasing order of their cardinalities. We identify easily verifiable analytical properties of the group cost function under which it is shown that an optimal partition exists of one of three increasingly special structures, thus allowing for increasingly simple solution methods. We give examples of all the above listed types of planning problems, and apply our results for the identification of efficient solution methods (wherever possible).