Calling GLPK From MATLAB

Before writing this post, my original aim was to find a roboust MIP solver that can be used through Matlab on the Win32 platform. However, I found several interfaces to the popular CPLEX (such as Claude Tadonki's solution) but these solutions have not been updated for several years. Fortunately, I hit on Nicolo' Giorgetti's glpkmex project that is more active and there is no restriction on the problem size in glpk comparing to CPLEX.

In the following, I write down my experiences and a workaround of the integration of Matlab and glpkmex including GLPK.

GLPK

The GLPK (GNU Linear Programming Kit) package is intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in ANSI C and organized in the form of a callable library.

GLPK supports the GNU MathProg modeling language, which is a subset of the AMPL language.

The GLPK package includes the following main components:

• primal and dual simplex methods
• primal-dual interior-point method
• branch-and-cut method
• translator for GNU MathProg
• application program interface (API)
• stand-alone LP/MIP solver

glpkmex

In order to use GLPK, Matlab needs an interface for the GLPK library. glpkmex is a Matlab MEX interface for the GLPK library which offers:

• to use GLPK through a simple matlab command, namely glpk
• to solve LP/MILP problems by defining all data and parameters in the Matlab workspace
• to save the original model on a file specified by the user with one of the formats supported by GLPK: CPLEX LP, fixed MPS, free MPS, plain text (see GLPK's reference manual for further details

Integration

In the glpkmex site, precompiled version can be found for easy usage. This 'official' version is updated on 2007/08/22 and it is compilant with GLPK v4.20. Fortunately, Niels Klitgord updated this version to the v4.37 (2009/03/29) glpk but it requires some manual work (compilation) before usage.

Installation GLPK on Win32

After downloading the GLPK, one can compile-it with batches within the 'glpk-4.xx\w32' directory. If 'Optimal solution found' message appears in command line, then everything is OK.

If any problem occures, a very good instruction is available how to compile the source source on Win32.

It is important to use the compatible versions, because glpkmex is very sensitive to the GLPK interface.

Compiling glpkmex

Inthe glpkmex package the makeglpkmex.m file supports to compile the glpkcc.cpp file, but it has several bugs (e.g. sensitive to spaces in directory names, and uses slash in some cases instead of backslash) so it is recommended to use it cautiously.

Some Experiences

After integration I compared it with Matlab's built-in 'bintprog' function on my sample datasets (100 decision variables) and the results were fascinating: it solved them faster than 2 magnitudes (200-600 times faster).