论文标题
可行二进制程序的直径
Diameter Polytopes of Feasible Binary Programs
论文作者
论文摘要
可行的二进制程序通常具有多个最佳解决方案，这在应用程序中引起了人们的关注，因为它们允许用户在替代Optima之间进行选择而不会降低目标函数。在本文中，我们介绍了可行二进制程序的最佳直径，作为测量所有最佳解决方案之间多样性的指标。此外，我们介绍了直径二进制程序，其最佳方法包含给定可行二进制程序的两个最佳解决方案，这些解决方案相对于最佳直径尽可能多样化。我们的主要兴趣是研究直径多层的研究，即直径二进制程序的多层。在适当的条件下，我们表明直径多层的大部分结构是从给定二进制程序的基础上继承的。最后，我们将结果应用于直径二进制程序和直径多层，以与给定的二进制程序相对应的线性排序问题和对称的旅行推销员问题。
Feasible binary programs often have multiple optimal solutions, which is of interest in applications as they allow the user to choose between alternative optima without deteriorating the objective function. In this article, we present the optimal diameter of a feasible binary program as a metric for measuring the diversity among all optimal solutions. In addition, we present the diameter binary program whose optima contains two optimal solutions of the given feasible binary program that are as diverse as possible with respect to the optimal diameter. Our primary interest is in the study of the diameter polytope, i.e., the polytope underlying the diameter binary program. Under suitable conditions, we show that much of the structure of the diameter polytope is inherited from the polytope underlying the given binary program. Finally, we apply our results on the diameter binary program and diameter polytope to cases where the given binary program corresponds to the linear ordering problem and the symmetric traveling salesman problem.
