论文标题
使用排名结构的弱点多层的大量刻面定义不平等的衍生
Derivations of large classes of facet-defining inequalities of the weak order polytope using ranking structures
论文作者
论文摘要
对订购多型的研究对于解决各种具有挑战性的组合优化问题的解决方案至关重要。例如，在分支和切割方法中，从这些多面体定义不平等的方面定义不平等（FDI）代表了迄今为止某些问题已知的最有效的解决方案方法之一。弱顺序多层定义为对$ n $替代方案的所有二元订单的特征向量的凸壳，这些级别的反射性，及时性和完整对于解决计算社会选择，偏好汇总和比较概率的问题尤为重要。在大多数情况下，弱点多层的FDI是通过枚举和从其他组合多面体的FDI衍生而获得的。本文通过利用弱顺序的等效表示作为$ n $对象的排名，通过允许纽带并分组共享某些排名结构的特征向量，从而为弱顺序多层提供了新的FDI类。此外，我们证明了以前通过枚举获得的许多FDI实际上是这些基于排名的FDI的特殊情况。
The study of ordering polytopes has been essential to the solution of various challenging combinatorial optimization problems. For instance, the incorporation of facet defining inequalities (FDIs) from these polytopes in branch-and-cut approaches represents among the most effective solution methodologies known to date for some of these problems. The weak order polytope, defined as the convex hull of the characteristic vectors of all binary orders on $n$ alternatives that are reflexive, transitive, and complete, has been particularly important for tackling problems in computational social choice, preference aggregation, and comparative probability. For the most part, FDIs for the weak order polytope have been obtained through enumeration and through derivation from FDIs of other combinatorial polytopes. This paper derives new classes of FDIs for the weak order polytope by utilizing the equivalent representation of a weak order as a ranking of $n$ objects that allows ties and by grouping characteristic vectors that share certain ranking structures. Furthermore, we demonstrate that a number of FDIs previously obtained through enumeration are actually special cases of these ranking-based FDIs.
