Sha*_*han 3 algorithm optimization linear-programming np-hard
我正在尝试使用整数线性编程(ILP)实现问题的解决方案.由于问题是NP难的,我想知道Simplex Method提供的解决方案是否是最优的？任何人都可以使用Simplex方法评论ILP的最优性或指向某些来源.是否有其他算法可以为ILP问题提供最佳解决方案？
编辑:我正在寻找对ILP的任何算法(单纯形法,分支和界限和切割平面)获得的解的最优性的是/否答案.
har*_*old 5
Simplex方法不处理您想要整数的约束.简单地舍入结果并不能保证提供最佳解决方案.
如果约束矩阵是完全对偶积分,则使用单纯形法解决ILP问题确实有效.
该解决ILP有些算法(不受限于全偶积分约束矩阵)的分支限界,这是实现简单,通常效果很好,如果成本是相当均匀(极不统一的成本使其尝试了很多的尝试,看起来有前途的首先,但结果不是)和切割飞机,我真的不太了解,但它可能是好的,因为人们正在使用它.
归档时间：
12 年，11 月 前
查看次数：
2683 次
最近记录：
12 年，10 月 前