Matthew Steel
EMAILCV [PDF]
EDUCATIONAL DOCS
An integer program solver using branch-and-bound on top of the revised simplex method.
It solves the problem "Max cTx subject to Ax=b; x∈ℕ"
Source [tar.gz] licensed under the WTFPL
Updated on 21/Confusion/3175.
It seemed strange not to programmed a branch and bound integer program solver after so much theory on IP at university. This project was largely an exercise in self-education on implementation details.
The most interesting question to answer was, if we only ever keep the inverse of the B matrix (the subset of columns of A that correspont to "active" x-variables) in the simplex solver, how do we add constraints and variables? Won't adding new columns and rows to the A matrix (and hence to the inverse-B matrix) upset things? Anyway, problem solved.
The code is old and smelly, but going back and making it nice isn't going to teach me anything new.
Some work was skirted around by branching into a revised-simplex phase1/phase2 algorithm instead of the (more traditional) dual simplex method. We add constraints to get to integrality, making the current solution infeasible. We get back to feasibility by using an artificial cost vector instead of using the dual simplex method. Laziness!
At the moment the code only supports depth-first node selection and most-fractional variable branching, though it'd be trivial to add more interesting schemes. Depth-first node selection is more interesting than best-first because it means we get to do the "bounding" in "branch and bound".
The linear program solver isn't too clever either. No fancy pricing or entering variable strategies (column generation etc). Constraints can only be specified in a "standard form". No generality lost, though.
Bed and Breakfast is mostly suitable for cheating on homework assignments asking you to solve integer programs by hand, drawing the B&B tree. I can't recommend it for serious work, and I recommend you check your results thoroughly if you do use it at all. For a real IP solver you'd do better with CBC, from the COIN-OR project.