Code covered by the BSD License  

Highlights from
Linear Mixed Integer Program Solver

5.0

5.0 | 3 ratings Rate this file 62 Downloads (last 30 days) File Size: 9.08 KB File ID: #25259
image thumbnail

Linear Mixed Integer Program Solver

by

 

08 Sep 2009 (Updated )

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

| Watch this File

File Information
Description

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.

Acknowledgements

This file inspired Minlp: Mixed Integer Nonlinear Programming.

MATLAB release MATLAB 7.9 (R2009b)
Other requirements Preferably a good linear program solver, see description.
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (6)
21 Jan 2013 Catalina Nuñez  
03 Oct 2011 Christos

Note the updated links for CLP and QSOPT solvers:
1. CLP by the COIN-OR project.
MEX interface can be found at:
http://control.ee.ethz.ch/~johanl/clp.php
3. QSOPT by David Applegate, William Cook, Sanjeeb Dash, and Monika Mevenkamp
MEX interface can be found at:
http://control.ee.ethz.ch/~johanl/mexqsopt.msql

23 Sep 2011 BIG Y.

I like to use this file for the folowing mathematical model but I have never used Matlab before. Can some one help please?

Minimize Somme of X(ik(i)) for i=1 to k

subject to:

X(ik)- T(ijk) >= X(ih)
X(pk)- X(ik)+ H *[1-Y(ipk)] >= T(pqk)
X(ik)- X(pk)+ H *[Y(ipk)] >= T(ijk)
X(ik)>=0
Y(ipk)= 0 or 1

02 Jan 2011 tawfik tawfik

its a good implementation for MINLP

25 Aug 2010 Mariano

Thanks for your work.
I have a question: why " It is highly recommended to use a different solver than linprog for solving the lp-relaxations" ?

12 Sep 2009 Petter

Why use this instead of YALMIP?

Updates
11 Sep 2009

Added better description

Contact us