寻找“简单”的整数线性编程源代码/伪代码 [英] Looking for "simple" integer linear programming source code / pseudo code

问题描述

我今天可能需要实现整数线性规划，我想知道是否有任何伪代码或相对无痛（评论很好）的源代码可以解释如何实现它？强烈倾向于使用伪代码。

I may need to implement Integer Linear Programming today and I am wondering if there are any pseudo codes or relatively pain-free (well commented) source codes that explain how to implement it? With strong preference towards pseudo code.

请注意，我并不是在寻找一个完整的项目来进行所有微调以获得最佳性能。我正在寻找最基本的解算器来演示整数线性编程如何工作与逐个尝试所有选项。

Please note, I am not looking for a serious complete project with all the "fine tuning" to get the most optimal performance. I am looking for the most basic solver that demonstrates how integer linear programming works vs. trying all the options one by one.

谢谢。

推荐答案

这个问题很大，所以让我一步一步来试试：

This question is a big ask, so let me try it step-by-step:

当你说整数线性程序时，我假设你指的是具有线性约束和目标函数的IP。

When you say Integer Linear Program, I assume you mean IP's with linear constraints and objective function.

1。从单纯形算法开始。
（即使这不适用于IP，除了线性程序具有完整性属性的幸运情况。）但 Simplex 总是一个好的开始，特别是。因为你对第一原理方法感兴趣

1. Start with the Simplex Algorithm. (Even though this will NOT work for IP's, except in "lucky" cases where your linear program has the "integrality" property.) But the Simplex is always a good place to start, esp. since you are interested in a first principles approach

令人惊讶的是，PseudoCode并不容易找到，尽管解决的例子很多。
以下是Simplex算法步骤的一个示例。 （不是Psuedo代码）

Surprisingly, PseudoCode is not that easy to find, though solved examples are plentiful. Here's one example of the steps in the Simplex algorithm. (Not Psuedo code)

在 3.1部分.4计算程序摘要有一些接近伪代码的东西。

In Section 3.1.4 Summary of Computation Procedure there is something close to pseudo-code.

本文档还总结了可以实现的单纯形算法，尤其是。如果您按照前面几节中的示例进行操作。

This document also has a summary of the Simplex Algorithm that can be implemented, esp. if you follow the example in the preceding sections.

注意，Simplex是相对容易理解的算法之一（特别是步骤逐步）但众所周知难以实施。 非常好的讨论为什么这可以在这里找到。

Note that Simplex is one of those algorithms that is relative easy to understand (esp. step-by-step) but notoriously difficult to implement. A really good discussion of why this is so can be found here.

2。整数编程 - 最简单的情况。
许多人倾向于从背包问题开始。

您可以找到伪代码这里有一个Java实现。

3。 IP越来越难以复杂化。

• 资本预算问题


• 分配问题


• 运输问题

4。通用与专业
您现在可以选择：

4. General Purpose vs Specialized You now have a choice:

• 4a。您可以构建通用IP解算器（但需要很长时间才能运行）


• 4b。为特殊类型的问题构建专用IP解算器。

对于4a：您可以假设0/1变量并演示分支和技术。您可以找到树的实现并根据自己的目的进行修改。 （基本上，是详尽搜索的巧妙实现。）

For 4a: You can assume 0/1 variables and demonstrate branch-and-bound techniques. You can find implementations of trees and modify for your own purposes. (Essentially, clever implementations of exhaustive searches.)

对于4b：你可以采取一个案例，比如作业问题，其中<强>匈牙利算法经常被使用，因为它易于理解，可以一次性地教给一群学生。
topcoder中的本教程涵盖了数学，伪代码和真实代码。

For 4b: You could take one case, say the Assignment Problem, for which the Hungarian algorithm is often used since it is easy to understand and can be taught in one sitting to a group of students. This tutorial in topcoder covers it quite extensively with the math, pseudo and real code.

答案很长，但我希望这与你所希望的一致。

Long answer, but I hope this is along the lines of what you are hoping for.

这篇关于寻找“简单”的整数线性编程源代码/伪代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！