pep*_*dip 3 integer pseudocode linear-programming
我今天可能需要实现整数线性规划,我想知道是否有任何伪代码或相对无痛(评论很好)的源代码解释如何实现它？强烈偏爱伪代码.
请注意,我并不是在寻找一个具有所有"微调"的严肃完整项目,以获得最佳性能.我正在寻找最基本的求解器,它演示整数线性编程如何工作与逐个尝试所有选项.
谢谢.
这个问题是一个很大的问题,所以让我一步一步地尝试:
当你说整数线性程序时,我假设你的意思是具有线性约束和目标函数的IP.
1.从Simplex算法开始. (即使这不适用于IP,除非你的线性程序具有"完整性"属性的"幸运"情况.)但Simplex始终是一个好的起点,尤其是.因为你对第一原理方法感兴趣
令人惊讶的是,PseudoCode并不容易找到,尽管解决的例子很多. 这是 Simplex算法中步骤的一个示例.(不是Psuedo代码)
在第3.1.4节"计算过程摘要"中,有一些与伪代码相近的内容.
本文档还总结了可以实现的Simplex算法,尤其是.如果您按照前面部分中的示例进行操作.
请注意,Simplex是相对容易理解的算法之一(尤其是逐步),但是很难实现.这里可以找到一个非常好的讨论原因.
2.整数编程 - "最简单"的情况. 许多人倾向于从"背包"问题开始.
您可以在此处找到伪代码和Java实现.
3. IP越来越难以复杂化.
4.通用与专业 您现在可以选择:
对于4a:您可以假设0/1变量并演示分支定界技术.您可以找到树的实现并根据自己的目的进行修改.(基本上,穷举搜索的巧妙实现.)
对于4b:你可以选择一个案例,比如分配问题,因为它很容易理解并且可以一次性地教给一组学生,因此经常使用匈牙利算法. topcoder中的这个教程非常广泛地介绍了数学,伪和真实代码.
答案很长,但我希望这与你所希望的一致.