Analyzing and Modeling the Maximum Diversity Problem by Zero‐One Programming*

作者：Ching‐Chung Kuo, Fred Glover, Krishna S. Dhir · 发表于：Decision Sciences · 年份：1993 · DOI：10.1111/j.1540-5915.1993.tb00509.x · 被引用次数：207 · 研究领域：Vehicle Routing Optimization Methods、Optimization and Mathematical Programming、Supply Chain and Inventory Management

ABSTRACT The problem of maximizing diversity deals with selecting a set of elements from some larger collection such that the selected elements exhibit the greatest variety of characteristics. A new model is proposed in which the concept of diversity is quantifiable and measurable. A quadratic zero‐one model is formulated for diversity maximization. Based upon the formulation, it is shown that the maximum diversity problem is NP‐hard. Two equivalent linear integer programs are then presented that offer progressively greater computational efficiency. Another formulation is also introduced which involves a different diversity objective. An example is given to illustrate how additional considerations can be incorporated into the maximum diversity model.