我今天可能需要实现整数线性规划，我想知道是否有任何伪代码或相对无痛（注释良好）的源代码来解释如何实现它？强烈偏爱伪代码。
请注意，我不是在寻找一个严肃的完整项目，它具有所有“微调”以获得最佳性能。我正在寻找一个最基本的求解器来演示整数线性规划是如何工作的，而不是一一尝试所有选项。
谢谢。
问问题
4448 次
1 回答
8
这个问题是一个很大的问题，所以让我一步一步地尝试：
当您说Integer Linear Program时，我假设您的意思是具有线性约束和目标函数的 IP。
1. 从单纯形算法开始。 （即使这对 IP 不起作用，除非在线性程序具有“完整性”属性的“幸运”情况下。）但是单纯形始终是一个很好的起点，尤其是。因为您对第一原理方法感兴趣
令人惊讶的是，PseudoCode 并不是那么容易找到，尽管解决的例子很多。 这是 Simplex 算法中步骤的一个示例。（不是伪代码）
在第3.1.4 节计算过程摘要中，有一些接近伪代码的内容。
该文档还对可以实现的单纯形算法进行了总结，尤其是。如果您按照前面部分中的示例进行操作。
请注意，Simplex 是相对容易理解（尤其是逐步）但难以实现的算法之一。关于为什么会这样的一个很好的讨论可以在这里找到。
2. 整数规划——“最简单”的情况。 许多人倾向于从“背包”问题开始。
您可以在此处找到伪代码和 Java 实现。
3. 难度/复杂度增加的IP。
- 资本预算问题
- 作业问题
- 运输问题
4. 通用型 vs 专用型 您现在有一个选择：
- 4a。您可以构建“通用”IP Solver（但需要很长时间才能运行）
- 4b。为特殊类型的问题构建专用 IP 求解器。
对于 4a：您可以假设 0/1 变量并演示分支定界技术。您可以找到树的实现并根据自己的目的进行修改。（本质上，穷举搜索的巧妙实现。）
对于 4b：你可以举一个案例，比如作业问题，匈牙利算法经常被使用，因为它很容易理解并且可以一次性教给一群学生。 topcoder 中的本教程非常广泛地涵盖了数学、伪代码和真实代码。
答案很长，但我希望这与您所希望的一致。
于 2012-10-10T00:14:46.700 回答