Sebastian Pokutta's Blog

Mathematics and related topics

The GNU Linear Programming Kit (GLPK) : Resources, Tutorials etc.

with 12 comments

The GNU Linear Programming Kit (glpk) is a very versatile Mixed Integer Linear Programming solver that is especially well suited for teaching and research purposes. Although the performance of the solver cannot match the performance of cplex, Gurobi, scip, or CBC, it has a lot of unique features on the one hand and glpk can be used as a modeling language for the mentioned solvers on the other hand. From the project homepage:

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

If you have other resources that you would like to see added here, just drop me a line!

There is also an official help-archive / mailing list with news and discussions. If you encounter any problems using GLPK this is also the right place to seek help.

— 10 reasons why you might want to use GLPK in class —

  1. GLPK is free
    GLPK is released under  the GPL and thus comes with the full source code.
  2. Easy installation
    The installation of GLPK is really simple on almost all platforms. For Windows, glpk binaries can be obtained as part of the GUSEK GUI (see below). Beware, the “glpk for windows” binaries seems to be outdated so do not use those and rather download GUSEK or get the latest binaries from the here. Most linux distributions come either with a copy of GLPK installed or GLPK can be installed via the respective package manager. On Mac OS X, GLPK can be compiled and installed used the typical “./configure”, “make”, “make install” or alternatively the GUSEK Gui can be used via Wine (see below). No hassle with compilation problems such as missing libraries etc; nothing is more frustrating than wanting to go ahead full speed and software problems jeopardize that.
  3. GLPK comes with a stand-alone solver and a callable library
    GLPK can be either used as a library, or as a stand-alone solver which is called glpsol. This solver can read either mps, cplex-lp, or GNU MathProg files. The latter format are the models generated by the modeling language GMPL that comes with GLPK. The solver is a branch-and-cut solver generating Gomory’s mixed integer cuts, mir cuts, mixed cover cuts, and clique cuts. It also has a feasibility pump.
  4. GLPK comes with the modeling language GMPL which is compatible with AMPL
    GLPK comes with its own modeling language, the GNU MathProg Language (GMPL) which is a subset of AMPL. This language is very versatile and modeling with it is extremely easy. Also, GLPK comes with a lot of examples that give a pretty good overview on how to formulate optimization problems in GNU MathProg.
  5. Modeling language and solver can be used independently
    If you have the feeling at some point that GNU MathProg is a cool modeling language (afterall it is almost AMPL but free) but you need to use a different (maybe more powerful) solver like cplex or CBC you can still continue using your old models written in GNU MathProg or even write new ones as you can use the modeling language and the solver separately: Using glpsol (the standalone solver) with the appropriate parameter set, you can write cplex-lp or mps files for example that you can use as input for e.g., cplex.
  6. GMPL is extremely easy to learn
    Consider the example below — nothing more to say.
  7. GUI for Windows, Mac OS X, and Linux available
    The GUSEK GUI (see below) provides a nice user interface to use GLPK on Windows, Mac OS X, and Linux (for the latter two using Wine). It comes with an integrated editor from which you can solve your models right away. Also most of the parameters of the glpsol standalone solver can be controlled via the GUI. There is also a new GUI, GLPK Lab for Windows, available.
  8. Database support and formatted text output
    GLPK can get its data for models from basically any database with an ODBC driver. It can also write the result to back into the database. Further the output of glpsol can be formatted using c-style printf statements combined with if and for statements. (see below)
  9. Java, python, matlab interface available
    There are many interfaces for GLPK available including Matlab, Octave, R, Java, Python (see below).
  10. Exact simplex algorithm integrated
    GLPK comes with the option to use an exact simplex implementation using rationals, i.e., no rounding errors etc. This is very helpful when using GLPK for research purposes and an exact solution is important (e.g., for verifying the derivation of cutting planes).

— An example —


# A TRANSPORTATION PROBLEM
#
# This problem finds a least cost shipping schedule that meets
# requirements at markets and supplies at factories.
#
#  References:
#              Dantzig G B, "Linear Programming and Extensions."
#              Princeton University Press, Princeton, New Jersey, 1963,
#              Chapter 3-3.

set I;
/* canning plants */

set J;
/* markets */

param a{i in I};
/* capacity of plant i in cases */

param b{j in J};
/* demand at market j in cases */

param d{i in I, j in J};
/* distance in thousands of miles */

param f;
/* freight in dollars per case per thousand miles */

param c{i in I, j in J} := f * d[i,j] / 1000;
/* transport cost in thousands of dollars per case */

var x{i in I, j in J} >= 0;
/* shipment quantities in cases */

minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];
/* total transportation costs in thousands of dollars */

s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i];
/* observe supply limit at plant i */

s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j];
/* satisfy demand at market j */

data;

set I := Seattle San-Diego;
set J := New-York Chicago Topeka;
param a :=
       Seattle     350
       San-Diego   600;
param b :=
       New-York    325
       Chicago     300
       Topeka      275;
param d :              New-York   Chicago   Topeka :=
Seattle                    2.5        1.7       1.8
San-Diego                  2.5        1.8       1.4  ;

param f := 90;
end;

— Tutorials —

A series of three tutorials on using glpk  is available on the IBM website

  1. The GNU Linear Programming Kit, Part 1: Introduction to linear optimization
  2. The GNU Linear Programming Kit, Part 2: Intermediate problems in linear programming
  3. The GNU Linear Programming Kit, Part 3: Advanced problems and elegant solutions

These tutorials deal in particular with using glpsol, the standalone mip solver and the modeling language GNU MathProg which is very similar to AMPL (actually GNU MathProg is a subset of AMPL). Several examples and well-known optimization problems are discussed, modeled, and solved using glpk. Another very nice website/blog with a lot of examples and information about GLPK and GMPL is

  1. Jeffrey Kantor’s “Introduction to Operations Research”.

— Additional tools and interfaces —

There are several other tools available for GLPK. For example GUSEK is a nice IDE for glpk which was originally developed for Windows but using Wine (and respectively WineBottler for Mac OS X) perfectly runs on Mac OS X and probably Linux as well.

Also there are a variety of interfaces available for GLPK:

Matlab/Octave: GLPKMEX is a Matlab interface for GLPK. It can also be used with Octave. From the website:

GLPKMEX is a Matlab MEX interface for the GLPK library which offers the following potentials:

  • Possibility to use GLPK through a simple matlab command, namely glpk.
  • Possibility to solve LP/MILP problems by defining all data and parameters in the Matlab workspace.
  • Easy definition of all GLPK parameters from which you can specify, for instance, which solver to use (simplex or interior point), activate/deactivate presolver, etc…
  • Possibility 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).
  • A few Matlab examples to show how simple is to define and solve LP/MILP problems.
  • An automatic script to compile your own mex interface.
  • And more… GLPKMEX includes now a simple Matlab-coded QP solver (still in beta version) developed by the author of GLPKMEX which uses GLPK to solve QP problems. A few examples are included in the distribution.

R: R/GLPK is an interface for the statistic package R.

There are several interfaces for Python:

Python: python-glpk (see also GLPK’s Wikipedia page).
PyGLPK:
PyGLPK
PyMathProg:
Python MathProg (GMPL)

Java: GLPK-java is an interface for Java.

YALMIP: YALMIP is a free Matlab interface/Matlab modeling environment for various solvers which can also access GLPK using GLPKMEX.

Many more interface can be found on GLPK’s Wikipedia page.

— Database support and formatted text output —

Reading and writing from databases within GMPL is fairly simple:

table data IN "CSV" "data.csv":
      s <- [FROM,TO], d~DISTANCE, c~COST;
table result{(f,t) in s} OUT "CSV" "result.csv":
      f~FROM, t~TO, x[f,t]~FLOW;

Also text output of the solution can be formatted fairly easily:


============================================================================================
===                                  Production Schedule                           =========
============================================================================================

        1	2	3	4	5	6	7	8	9	10
prod	7	5	7	11	11	4	10	0	9	8
stock	0	0	3	9	0	0	1	0	0	0
demand	7	5	4	5	20	4	9	1	9	8
level	3	3	3	3	3	3	3	3	3	3
change
pstop	*	*	*	*	*	*	*	-	*	*

Using statements like:

printf("\n");
printf("============================================================================================\n");
printf("===                                  Production Schedule                           =========\n");
printf("============================================================================================\n");
printf("\n");

printf "\t";
for {i in TP}
    printf "%d\t",i ;
printf "\n";
printf "prod\t";
for {i in TP}
    printf "%d\t", sum{k in Lev} x[i,k] ;
printf "\n";

printf "stock\t";
for {i in TP}
    printf "%d\t",s[i] ;
printf "\n";

printf "demand\t";
for {i in TP}
    printf "%d\t",demand[i] ;
printf "\n";

printf "level\t";
for {i in TP}
    printf "%d\t",sum{j in Lev} j*l[i,j] ;
printf "\n";

printf "change\t";
for {i in TP} {
    for {(j,k) in C : w[j,k,i] == 1} {
        printf "%d->%d", j, k;}
    printf "\t";
}
printf "\n";

printf "pstop\t";
for {i in TP} {
    printf "%s\t", if sum{k in Lev} x[i,k] == 0  then "-" else "*";
}

in GMPL. Using the text output capabilities of GMPL almost any text-based output format can be generated that can be then used later in other programs. You can, for example, use the output formatting to generate .dot files which you can plot then with graphviz or you can generate gnuplot compatible output for nice charts. Also, using the table driver, you can generate output that you feed directly into Excel, g-docs, or Open Office either via copy-and-paste or by importing .csv files.

You can also directly read and write data using GMPL’s ODBC support; to setup GMPL ODBC for WindowsXP see here. Here are two examples for reading/write Excel spreadsheets and Access databases (thx to Noli for the examples / see comments):

Accessing Excel spreadsheets:

Reading data from a sheet (e.g. transp_demand as SHEET1)


table markets IN "iODBC"
   'DSN=glpk_excel;UID=transp.xls'
'SELECT * FROM [transp_demand$]' :
J <- [ MARKET ], b ~ DEMAND;

Writing results


table result{i in I, j in J: x[i,j]} OUT "iODBC"
'DSN=glpk_excel;UID=transp.xls'
'INSERT INTO [transp_result$] VALUES (?,?,?)' :
i ~ LOC1, j ~ LOC2, x[i,j] ~ QUANTITY;

Accessing Access databases:

Reading data from mdb table.

table plants IN "ODBC"
       'DSN=glpk_mdb'
       'SELECT PLANT, CAPA AS CAPACITY'
       'FROM transp_capa' :
       I <- [ PLANT ], a ~ CAPACITY;

Writing results in mdb table.

table result{i in I, j in J: x[i,j]} OUT "iODBC"
       'DSN=glpk_mdb'
       'DELETE FROM transp_result;'
       'INSERT INTO transp_result VALUES (?,?,?)' :
       i ~ LOC1, j ~ LOC2, x[i,j] ~ QUANTITY;

Similarly you can access an sqlite3 database. You simply need to exchange the DSN (see Noli’s comment below).

— Links —

  1. GNU Linear Programming Kit (glpk)
  2. GUSEK IDE
  3. Wine HQ
  4. WineBottler (WINE for Mac OS X)
  5. The GNU Linear Programming Kit, Part 1: Introduction to linear optimization
  6. The GNU Linear Programming Kit, Part 2: Intermediate problems in linear programming
  7. The GNU Linear Programming Kit, Part 3: Advanced problems and elegant solutions
  8. Jeffrey Kantor’s “Introduction to Operations Research”
  9. GLPKMex: Matlab/Octave interface
  10. R/GLPK: R interface
  11. python-glpk: Python interface
  12. GLPK Lab
  13. GLPK-java: Jave interface
  14. YALMIP: Matlab modeling environment for various solvers
  15. GLPK’s Wikipedia page

Written by Sebastian

January 24, 2010 at 2:01 pm

12 Responses

Subscribe to comments with RSS.

  1. […] with much information about GLPK, interfaces to other software, tutorials, etc. can be found here. Possibly related posts: (automatically generated)GLPK 4.41 releasedGLPK 4.38 releasedGLPK 4.39 […]

  2. Sebastian nice write up!

    I just like to add examples for MathProg (GMPL) ODBC / iODBC (Mac and Linux) database support.

    The following example tested in Windows XP and will work in Mac OS X and Linux with iODBC support.

    EXCEL
    Reading data from a sheet (e.g. transp_demand as SHEET1)

    table markets IN “iODBC”
    ‘DSN=glpk_excel;UID=transp.xls’
    ‘SELECT * FROM [transp_demand$]’ :
    J <- [ MARKET ], b ~ DEMAND;

    Writing results
    table result{i in I, j in J: x[i,j]} OUT "iODBC"
    'DSN=glpk_excel;UID=transp.xls'
    'INSERT INTO [transp_result$] VALUES (?,?,?)' :
    i ~ LOC1, j ~ LOC2, x[i,j] ~ QUANTITY;

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Access database MDB

    Reading data from mdb table.

    table plants IN "ODBC"
    'DSN=glpk_mdb'
    'SELECT PLANT, CAPA AS CAPACITY'
    'FROM transp_capa' :
    I <- [ PLANT ], a ~ CAPACITY;

    Writing results in mdb table.

    table result{i in I, j in J: x[i,j]} OUT "iODBC"
    'DSN=glpk_mdb'
    'DELETE FROM transp_result;'
    'INSERT INTO transp_result VALUES (?,?,?)' :
    i ~ LOC1, j ~ LOC2, x[i,j] ~ QUANTITY;

    SQLite3

    Reading data from sqlite3 (transp.db3).

    table plants IN "iODBC"
    'DSN=glpk_sqlite3'
    'SELECT PLANT, CAPA AS CAPACITY'
    'FROM transp_capa' :
    I <- [ PLANT ], a ~ CAPACITY;

    Writing results in sqlite3 table.

    table result{i in I, j in J: x[i,j]} OUT "iODBC"
    'DSN=glpk_sqlite3' #UID=transp.db3'
    'DELETE FROM transp_result;'
    'INSERT INTO transp_result VALUES (?,?,?)' :
    i ~ LOC1, j ~ LOC2, x[i,j] ~ QUANTITY;

    To setup MathProg ODBC in WindowsXP

    http://www.mail-archive.com/help-glpk@gnu.org/msg03732.html

    Regards, Noli

    Noli

    February 12, 2010 at 9:24 pm

    • Thx a lot! That is indeed very helpful! The connectivity, especially to databases and Excel is a big plus of GMPL/GLPK.

      I will merge your comment with the main article.

      All the best,
      Sebastian

      Sebastian

      February 13, 2010 at 12:13 am

  3. Recent GLPK/MathProg Windows binaries in this site.

    http://winglpk.sourceforge.net/

    Download http://sourceforge.net/projects/winglpk/

    PyMathProg – Python MathProg (GMPL)

    http://pymprog.sourceforge.net/

    Download http://sourceforge.net/projects/pymprog/

    Noli

    Noli

    February 13, 2010 at 12:30 am

  4. Python GLPK – pythonic implementation of GLPK also used in PyMathProg

    http://www.cs.cornell.edu/~tomf/pyglpk/

    What’s New with GLPK/MathProg, visit the help glpk archive http://www.mail-archive.com/help-glpk@gnu.org/
    and also subscribe to help glpk http://lists.gnu.org/mailman/listinfo/help-glpk for questions, support, etc.

    Noli

    Noli

    February 13, 2010 at 12:46 am

    • Thanks a lot! I merged the links back into the main article.

      Sebastian

      Sebastian

      February 13, 2010 at 10:56 am

  5. TextAdept and GLPK with ODBC support for Windows, Mac OS X and Linux

    Running GUSEK IDE in Wine and Winebottle does not support ODBC tables (database and spreadsheet data input and output).

    Use TextAdept with GLPK lexer/plugin for ODBC support

    TextAdept

    http://code.google.com/p/textadept/

    Visit the help glpk and ask for the glpk plugin for textadept.

    Noli

    Using TextAdept with GLPK

    Noli

    February 22, 2010 at 11:14 pm

  6. […] More information on GLPK including tutorials, examples, and tools can be found here. […]

  7. There is now an evolving wikibook on GLPK:

    http://en.wikibooks.org/wiki/GLPK

    Robbie Morrison

    October 18, 2010 at 7:56 am

  8. Hello!

    (Gusek help)
    I was trying to read a string column from MS Access
    I defined parameter ‘y’ for that purpose : but it says it has to be a number.
    is there a way to read a column of strings?

    I altered the table: added an extra colum – Test(text)

    set I;
    /* canning plants */

    param a{i in I};
    /* capacity of plant i in cases */

    param y{i in I};

    table plants IN “ODBC”
    ‘DRIVER={Microsoft Access Driver (*.mdb)};dbq=glpk.mdb’
    ‘SELECT PLANT, CAPA AS CAPACITY, Test’
    ‘FROM transp_capa’ :
    I <- [ PLANT ], a ~ CAPACITY, y ~ Test;

    Thanks
    Mandar

    Mandar

    March 2, 2011 at 7:21 pm

  9. Nice work man!

    I’m using glpk, going to post some of my modelling online then I send you the link.

    thanks for sharing knowledge!

    Jacson Querubin

    May 29, 2012 at 10:59 pm

  10. […] Excel is not the home for you. Moving to the command line, we can stay in free-land by modeling in GLPK, but honestly, the solver that comes with GLPK kinda blows on large problems. Consider instead […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 25 other followers

%d bloggers like this: