Linear Mixed Integer Program Solver

Solve linear mixed integer problems with a branch and bound method.
5.8K Downloads
Updated 11 Sep 2009

View License

Solves the mixed integer linear problem:

min c'*x

s.t. A*x <= b
s.t. Aeq*x == beq
s.t. lb <= x <= ub
x(yidx) integer

where yidx is a logical index vector.

This program solves linear 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 Mészáros
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

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.

Cite As

Thomas Trötscher (2024). Linear Mixed Integer Program Solver (https://www.mathworks.com/matlabcentral/fileexchange/25259-linear-mixed-integer-program-solver), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2009b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and MATLAB Answers
Acknowledgements

Inspired: MINLP: Mixed Integer Nonlinear Programming

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.1.0.0

Added better description

1.0.0.0