Structured partitioning problems

Structured partitioning problems

0.00 Avg rating0 Votes
Article ID: iaor1993801
Country: United States
Volume: 39
Issue: 1
Start Page Number: 130
End Page Number: 149
Publication Date: Jan 1991
Journal: Operations Research
Authors: ,
Keywords: sets
Abstract:

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. The authors 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. They give examples of all the above listed types of planning problems, and apply the present results for the identification of efficient solution methods (whenever possible).

Reviews

Required fields are marked *. Your email address will not be published.