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.
Thanks.
This question is a big ask, so let me try it step-by-step:
When you say Integer Linear Program, I assume you mean IP's with linear constraints and objective function.
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
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)
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.
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. Integer Programming - The "simplest" case.
Many people tend to start with the "Knapsack" problem.
You can find both the pseudo-code and a Java implementation here.
3. IP's of increasing difficulty/complexity.
- Capital Budgeting Problem
- Assignment Problems
- Transportation Problems
4. General Purpose vs Specialized
You now have a choice:
- 4a. You can build 'general purpose' IP Solver (but will take a very long time to run)
- 4b. Build special purpose IP solvers for special types of problems.
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.)
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.
