Solve linear mixed integer problems with a branch and bound method.

contents.m

% LINEAR MIXED INTEGER PROGRAM SOLVER
% This program solves mixed integer problems with a branch and bound
% method. It is highly recommended to use a different solver than linprog
% for solving the lp-relaxations. There are three good alternatives
% available online with pre-compiled mex files:
% 1. CLP by the COIN-OR project.
% MEX interface can be found at:
% http://control.ee.ethz.ch/~joloef/clp.php
% 2. BPMPD by Csaba Mszros
% MEX interface can be found at:
% http://www.pserc.cornell.edu/bpmpd/
% 3. QSOPT by David Applegate, William Cook, Sanjeeb Dash, and Monika Mevenkamp
% MEX interface can be found at:
% http://control.ee.ethz.ch/~joloef/mexqsopt.msql
% To use another solver specify options.solver = 'clp','bp' or 'qsopt';
% see mipoptions
%
% Functions:
% miprog - Solve the linear mip problem
% mipoptions - Loads default options, see source for explanation
% lpr - Solves the lp relaxation
% miptest - Runs a tiny test problem
% Other:
% testproblem.mat - Contains a small testproblem
%
% Further work:
% Add heuristics to create a good initial integer solution
% Add cuts to the problem (branch and cut method)
%
% Some testing with the problem shows that it works well with up to
% around 30 integer variables and 10000 lp variables if you use qsopt or
% clp. However, the performance is far from that of commercial solvers;
% this program is intended for educational purposes.
%
% Thomas Trtscher 2009