机构名称：
¥ 1.0
范围。优化问题的很大一部分等同于优化线性程序，其中可行区域是由线性不等式定义的多面体。解决此类问题的复杂性受到多面体结构的很大影响。尤其是当多面体是整数时，众所周知，我们可以在多项式时间内解决问题的大小[7]。实际上，最有效的算法之一仍然是Dantzig开发的单纯形方法。即使该方法以不良的理论性能而闻名[8，9]，它已经看到了新的兴趣和几种理论进步[5]，特别是最近的一些发展，连接了多面体的结构以及该算法的效率[1]。该算法的另一个兴趣点是与问题本身的多面体结构的密切联系。尤其是，影响单纯形算法性能的一个关键因素是多面体直径，它限制了最坏情况下所需的枢轴数量。在这种情况下，赫尔希猜想的弱形式已被证明对由完全单型矩阵定义的多型植物有效[2，6]。box-tdi polyhedra是可以用box-tdi系统描述的多面体。这些多面体直接概括了由完全单型矩阵描述的多面体[3]。此外，即使整数线性编程最近已被证明在Box-TDI Polyhedra上是NP-HARD [4]，当此Polyhedra是整数时，该主题尚未探索。该项目的主要目的是研究Box-TDI Polyhedra是否承认直径范围的改善，以及这是否对线性编程算法的效率有影响。
“ box-tdi polytopes的算法和结构属性...
主要关键词
相关文件推荐
