Wikibooks

GLPK/Print version

< GLPK


Introduction

Welcome to the GNU Linear Programming Kit Wikibook!

About this Wikibook

This Wikibook covers the mainline GLPK project and a number of separate initiatives. It is designed to complement rather than duplicate the official GLPK documentation.

The GLPK project

The core GNU Linear Programming Kit (GLPK) project comprises:

The GLPK project itself is hosted at www.gnu.org/software/glpk.

The GLPK wikipedia entry can be found at en.wikipedia.org/wiki/GLPK.

The GLPK project maintains two mailing lists: help-glpk@gnu.org and bug-glpk@gnu.org. To subscribe to either of these lists, visit lists.gnu.org/mailman/listinfo/help-glpk or lists.gnu.org/mailman/listinfo/bug-glpk respectively. These lists are solely for traffic concerning the mainline GLPK project — matters relating to third-party initiatives should be directed to those initiatives.

The official GLPK documentation can be found in the doc subdirectory after unpacking the latest GLPK tarfile. To obtain this tarfile, find a suitable GNU FTP mirror, open the glpk directory, and download the latest glpk-0.00.tar.gz entry. Alternatively, follow these step-by-step instructions.

In the first instance, GLPK is distributed as source code with the expectation that users will build their own binaries (libraries and executables) — to suit their individual constellation of operating system, processor architecture, and C compiler and their choice of GLPK configuration options. Some users prefer to download pre-compiled files instead — particularly users running Windows systems or common Linux distros — such binaries are often available from the wider GLPK community or from Linux software repositories, respectively.

Andrew Makhorin, Moscow Aviation Institute, is the lead developer and maintainer of GLPK. The first public release was October 2000.

Parallel initiatives

The GLPK project has spawned a number of parallel initiatives, some of which may migrate back into the main codebase and some of which will remain distinct and different.

Solver and language development

In terms of solver and language development, initiatives include:

  • the provision of specialist reporting
  • support for new problem formats and similar solver-wide features
  • refinements to the GLPK branch-and-bound solution process for particular applications
  • extensions to the MathProg language.

Source code contributions are normally provided as patches to the maintainer. There is no web-based code hosting for GLPK at present.

Deployment and usability

In terms of deployment and usability, initiatives include:

A key reason for this Wikibook is to provide a location in which to collect and compare these often diverse initiatives.

Closure

Remember to consult the official GLPK documentation, in the first instance, for issues that relate directly to GLPK. The author of GLPK, Andrew Makhorin, works hard to keep the official documentation current and comprehensive.

Try to run the latest version of GLPK. The codebase is under continual improvement and you do yourself a disservice by running stale code. You will also receive more interest on the Help-glpk mailing list if you raise an issue that relates to the latest release.


Scalable Vector Graphics

Scalable vector graphics (SVG) is an XML file format to describe two dimensional graphics. SVG 1.1 is the most recent version of the specification.

With a little effort, the MathProg printf statement can be used to generate SVG code.

Examples

Traveling salesman problem

 
SVG output generated with GLPK

The task in the traveling salesman problem is to find the shortest cyclic path through a given set of cities, visiting each city exactly once, and then returning to the start.

The model below shows how to output the solution as a scalable vector graphic. 

###################################################################
# This file demonstrates output to a scalable vector graphic (SVG).
#
# Solve with option --nomip to see the difference
#
# Traveling salesman problem
#
###################################################################

# output file
param filename, symbolic := "out.svg";
# number of cities
param n := 35;

# set of cities
set N := {1..n};
# set of bidirectional arcs
set E := setof{(i,j) in N cross N : i > j} (i,j);
# set of unidirectional arcs
set F := setof{(i,j) in N cross N : i != j} (i,j);

# random locations for the cities
param cx{i in N} := Uniform01();
param cy{i in N} := Uniform01();
#sum of x- and y- distance
#param d{(i,j) in E} := abs(cx[i]-cx[j])+abs(cy[i]-cy[j]);
#maximum of x- and y- distance
#param d{(i,j) in E} := max(abs(cx[i]-cx[j]),abs(cy[i]-cy[j]));
#euclidean distance
param d{(i,j) in E} := sqrt((cx[i]-cx[j])^2+(cy[i]-cy[j])^2);

# connection
var x{(i,j) in E}, >=0, <= 1, binary;
# flow
var f{(i,j) in F}, >= 0;

# Objective
minimize dist :
  sum{(i,j) in E} x[i,j] * d[i,j];

# Every city must have two connections for a round trip
s.t. two{ i in N } :
  sum{j in N : i > j} x[i,j] + sum{j in N : i < j} x[j,i] = 2;

# The following constraints force the graph to be connected
# Flow is controlled by binaries
s.t. flow1 {(i,j) in F} :
  f[i,j] <= (if (i==1) then n else n-1) 
          * (if (i < j) then x[j,i] else x[i,j]);

# One unit is consumed in each node
s.t. flow2 {i in N} :
  sum{(i,j) in F} (f[i,j]-f[j,i]) <= if (i==1) then n-1 else -1;

# There must be flow into every node
s.t. flow3 { i in N } :
  sum{(i,j) in F} f[j,i] >= 1;

solve;

# Output the solution as scalable vector graphic
# write header
printf "<?xml version=""1.0"" standalone=""no""?>\n" > filename;
printf "<!DOCTYPE svg PUBLIC ""-//W3C//DTD SVG 1.1//EN"" \n" >> filename;
printf """http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"">\n" >> filename;
printf "<svg width=""100\%"" height=""100\%"" version=""1.0"" \n" >> filename;
printf "xmlns=""http://www.w3.org/2000/svg"">\n" >> filename;
# draw circles for cities
for {i in N}
  printf "<circle cx=""%f"" cy=""%f"" r=""5"" stroke=""black"" stroke-width=" &
         """2"" fill=""red""/>\n", cx[i] * 500, cy[i] * 500 >> filename;
# draw solid black lines for integer connections
for {(i,j) in E : x[i,j] == 1}
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""" &
         " style=""stroke:black;stroke-width:2""/>\n", 
         cx[i] * 500, cy[i] * 500, cx[j] * 500, cy[j] * 500 >> filename;
# draw dashed red lines for fractional connections
for {(i,j) in E : x[i,j] > 0 && x[i,j] < 1}
  {
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""",
         cx[i] * 500, cy[i] * 500, cx[j] * 500, cy[j] * 500 >> filename;
  printf " style=""stroke:red;stroke-dasharray: 3 3;stroke-width:2""/>\n"
         >> filename;
  }
printf "</svg>\n" >> filename;
end;

Run the model (40 seconds on a Intel Core i5 processor): 

$ glpsol --math traveling.mod

This is what the created output file out.svg looks like (some lines removed): 

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" 
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="100%" height="100%" version="1.0" 
xmlns="http://www.w3.org/2000/svg">
<circle cx="14.843435" cy="64.155902" r="5" stroke="black" stroke-width="2" fill="red"/>
<circle cx="276.895963" cy="4.798338" r="5" stroke="black" stroke-width="2" fill="red"/>
...
<line x1="103.248022" y1="381.131207" x2="127.779724" y2="409.131953" style="stroke:black;stroke-width:2"/>
<line x1="103.248022" y1="381.131207" x2="96.365578" y2="282.627837" style="stroke:black;stroke-width:2"/>
</svg>

The resulting file can be viewed in an up-to-date web browser (like Firefox 3.6 or Internet Explorer 9) or viewed and modified using a (multi-platform) SVG editor (like Inkscape).

Clustering

 
Solution of a clustering problem created with GLPK

The example below concerns a clustering problem. Out of 500 towns select 20 to be cluster centers and assign the other towns to the cluster such that the sum of the population weighted euclidian distances between towns and centers is minimized. 

# Output file
param f, symbolic := "ct.svg";

# Centers
param nc := 20;
set C := {1 .. nc};

# Towns
param nt := 500;
set T := {1 .. nt};
param xt{T} := Uniform01();
param yt{T} := Uniform01();
param pt{T} := ceil(1000 * Uniform01());

# Image size
param scale := 1000;

# Colors
# saturation [0, 255]
param sat := 192;
param hue{c in C} := 6 * (c - 1) / nc;
param red{c in C} :=
  if hue[c] <= 1 or hue[c] >= 5 then 255
  else (if hue[c] >=2 and hue[c] <= 4 then 255 - sat
  else (if hue[c] <=2 then 255 - sat + sat * (2-hue[c])
  else 255 - sat + sat * (hue[c]-4) ));
param green{c in C} :=
  if hue[c] >= 1 and hue[c] <= 3 then 255
  else (if hue[c] >= 4 then 255 - sat
  else (if hue[c] <=1 then 255 - sat + sat * hue[c]
  else 255 - sat + sat * (4-hue[c]) ));
param blue{c in C} :=
  if hue[c] >= 3 and hue[c] <= 5 then 255
  else (if hue[c] <=2 then 255 - sat
  else (if hue[c] <=3 then 255 - sat + sat * (hue[c]-2)
  else 255 - sat + sat * (6-hue[c]) ));

var x{T,T}, binary;

minimize obj : sum{c in T, t in T : c != t} x[c,t] * pt[t]
               * sqrt((xt[c] - xt[t])^2 + (yt[c] - yt[t])^2);

s.t. cc : sum{c in T} x[c,c] = nc;
s.t. ct{c in T, t in T : c != t} : x[c,t] <= x[c,c];
s.t. tc{t in T} : sum{c in T} x[c,t] = 1;

solve;

for {c in T : x[c,c] > .5} {
  printf "Center %5.4f %5.4f\n", xt[c], yt[c];
  for {t in T : x[c,t] > .5} {
    printf "  Town %5.4f %5.4f (%5.0f)\n", xt[t], yt[t], pt[t];
  }
}

# Output the solution as scalable vector graphic

# header
printf "<?xml version=""1.0"" standalone=""no""?>\n" > f;
printf "<!DOCTYPE svg PUBLIC ""-//W3C//DTD SVG 1.1//EN"" \n" >> f;
printf """http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"">\n" >> f;
printf "<svg width=""%d"" height=""%d"" version=""1.0"" \n",
  1.2 * scale, 1.2 * scale >> f;
printf "xmlns=""http://www.w3.org/2000/svg"">\n" >> f;

# background
printf "<rect x=""0"" y=""0"" width=""%d"" height=""%d""" &
       " stroke=""none"" fill=""white""/>\n",
       1.2 * scale, 1.2 * scale>> f;

# border
printf "<rect x=""%d"" y=""%d"" width=""%d"" height=""%d""" &
       " stroke=""black"" stroke-width="".5"" fill=""white""/>\n",
       .1 * scale, .1 * scale, scale, scale >> f;

# circles for towns
for {t in T}
  printf {s in T, c in C : x[s,t] > .5
         && c = floor( .5 + sum{u in T : u <= s} x[u,u])}
         "<circle cx=""%f"" cy=""%f"" r=""%f"" stroke=""black"" " &
         "stroke-width=""1"" fill=""rgb(%d,%d,%d)""/>\n",
         (.1 + xt[t]) * scale, (.1 + yt[t]) * scale, .007 * sqrt(pt[t]/nt) *
	 scale, red[c], green[c] , blue[c] >> f;

# lines from towns to assigned centers
for {t in T, c in T : x[c,t] > .5}
  printf "<line x1=""%f"" y1=""%f"" x2=""%f"" y2=""%f""" &
         " style=""stroke:black;stroke-width:.5""/>\n",
         (.1 + xt[c]) * scale, (.1 + yt[c]) * scale,
         (.1 + xt[t]) * scale, (.1 + yt[t]) * scale >> f;

printf "</svg>\n" >> f;

end;


Gnuplot

Gnuplot is a program for generating two and three dimensional plots of functions, data, and data fits. Gnuplot is published under the GNU General Public License.

2D histogram

 
2D histogram generated with gnuplot from a GLPK solution

Gnuplot expects data for histograms to be in multiple columns.

The following example is based on examples/transp.mod from the GLPK source distribution: 

solve;
printf '""' > 'transp1.dat';
printf {j in J} ' "%s"', j >> 'transp1.dat';
printf '\n' >> 'transp1.dat';
for {i in I} {
  printf '"%s"', i >> 'transp1.dat';
  printf {j in J} ' %f', x[i,j] >> 'transp1.dat';
  printf '\n' >> 'transp1.dat';
}

The above MathProg statements (inserted before the data statements of transp.mod and saved as a file named transp1.mod) will create, using the command glpsol --math transp1.mod, the following content in the file transp1.dat: 

"" "New-York" "Chicago" "Topeka"
"Seattle" 50.000000 300.000000 0.000000
"San-Diego" 275.000000 0.000000 275.000000

Using gnuplot, a histogram of transp1.dat can be drawn and then saved as a PNG image: 

reset
set terminal png truecolor transparent font "Arial, 16" size 800x600
set output "transp1.png"
set title 'Result of transp.mod'
set style data histogram
set style histogram cluster gap 1
set style fill solid border &minus;1
set boxwidth 0.9
set bmargin 5
set grid y
set xrange [&minus;0.5:2.5]
set xtics out nomirror
plot 'transp1.dat' \
  using 2:xtic(1) title columnheader(2), \
  for [i=3:4] '' using i title columnheader(i)

The above commands can either be hand entered into an interactive gnuplot session. Invoke gnuplot from the command-line to start such a session. Alternatively, the same commands can be saved in a text file transp1.gp and then run as a script from within gnuplot: 

gnuplot> load "transp1.gp"

Finally, check the resulting transp1.png with any bitmap viewer, perhaps gthumb: 

gthumb transp1.png &

3D histogram

 
3D histogram generated with gnuplot from a GLPK solution

Gnuplot does not directly support native 3D histograms. Surfaces with rectangular grids can be passed to gnuplot using the following rules:

  • provide one text line per point, with each field separated by a space
  • consecutive points of one raster line should be on consecutive text lines
  • place a blank text line between points of consecutive raster lines.

To create a 3D histogram it is necessary to provide the 4 corner points of each pillar of the histogram. The following example is again based on examples/transp.mod: 

solve;

printf '' > 'transp2.dat';
for { i in I  } {
  for { j in J } {
    printf '%i "%s"', sum{k in I: k < i} 1, i >> 'transp2.dat';
    printf ' %i "%s"', sum{l in J: l < j} 1, j >> 'transp2.dat';
    printf ' %f', x[i,j] >> 'transp2.dat';
    printf '\n' >> 'transp2.dat';

    printf '%i "%s"', sum{k in I: k < i} 1, i >> 'transp2.dat';
    printf ' %i "%s"', sum{l in J: l <= j} 1, '' >> 'transp2.dat';
    printf ' %f', x[i,j] >> 'transp2.dat';
    printf '\n' >> 'transp2.dat';
    }
    printf '\n' >> 'transp2.dat';
  for { j in J } {
    printf '%i "%s"', sum{k in I: k <= i} 1, '' >> 'transp2.dat';
    printf ' %i "%s"', sum{l in J: l < j} 1, j >> 'transp2.dat';
    printf ' %f', x[i,j] >> 'transp2.dat';
    printf '\n' >> 'transp2.dat';

    printf '%i "%s"', sum{k in I: k <= i} 1, '' >> 'transp2.dat';
    printf ' %i "%s"', sum{l in J: l <= j} 1, '' >> 'transp2.dat';
    printf ' %f', x[i,j] >> 'transp2.dat';
    printf '\n' >> 'transp2.dat';
    }
    printf '\n' >> 'transp2.dat';
  }
data;

set I := San-Diego Seattle;

set J := Chicago New-York Topeka;

As before, a 3D histogram of transp2.dat can be drawn using gnuplot and saved as a PNG image: 

reset
set terminal png font "Arial, 16" transparent size 800,800
set output "transp2.png"
set title 'Result of transp.mod'
set xtic offset first 0.5, first −0.25, first 0 mirror
set ytic offset first 0.25, first 0.5, first 0 mirror
set nokey
set pm3d
set palette gray
set grid x y z
splot 'transp2.dat' using 1:3:5:xtic(2):ytic(4) with pm3d


Language Bindings

To use the GLPK library with languages other than C and C++, it is necessary to create code which can interface between the client and library languages. This code is known as a language binding.

Caution: GLPK is undergoing an overhaul of its application programming interface, with many APIs being deprecated. In parallel, several new APIs have been added. Users should therefore exercise considerable caution when evaluating or using language bindings that are not under active maintenance.

Specific languages

The following language bindings have dedicated pages:

  • Ada language bindings
  • C# language bindings
  • Fortran language bindings
  • GAMS language bindings
  • Java language bindings
  • JavaScript language bindings
  • Julia language bindings
  • Matlab (and Octave) language bindings
  • OCaml language bindings
  • Octave language bindings
  • OptimJ language bindings
  • Python language bindings
  • R language bindings
  • Ruby language bindings

The following language bindings do not yet have dedicated pages (please make them if you think it appropriate):

  • Common lisp language bindings — last active 2007, read this revealing posting
  • Erlang language bindings — last active GLPK 4.38 (02 May 2009)
  • Perl language bindings — last active 2007


Java

Java is an object-oriented application programming language.

GLPK for Java

 
GLPK for Java comes with a bunch of examples. GmplSwing.java demonstrates the use of callbacks and terminal output redirection.

GLPK for Java uses SWIG to generate code for its Java language binding. This binding is published under the GNU General Public License.

Installation

GLPK for Java is available through the Debian package libglpk-java, which can also be used with Ubuntu. Windows binaries are provided as part of the GLPK for Windows project.

Makefiles for Windows and POSIX-compliant systems (which includes all Linux distros) are available for manual builds on other systems. You will need to install GLPK and SWIG beforehand if you choose this option.

Documentation

The GLPK for Java file doc/glpk-java.pdf contains a short description. Practical examples can be found in the examples/java directory. For the usage of the individual methods refer to doc/glpk.pdf of the GLPK source distribution.

Compiling and running

Below is a minimal Java class. Save it as file Test.java. 

import org.gnu.glpk.GLPK;
public class Test {
  public static void main(String[] args) {
    System.out.println( GLPK.glp_version());
  }
}

Then compile this class under 64-bit Windows: 

"%JAVA_HOME%\bin\javac" -classpath "C:\Program Files\GLPK\glpk-4.47\w64\glpk-java.jar" Test.java

Or compile it under Linux: 

$JAVA_HOME/bin/javac -classpath /usr/local/share/java/glpk-java.jar Test.java

Run the resulting file on 64-bit Windows: 

java -Djava.library.path="C:\Program Files\GLPK\glpk-4.47\w64" -classpath "C:\Program Files\GLPK\glpk-4.47\w64\glpk-java.jar";. Test

Or run the file on Linux (the file paths may need adjustment to match your installation): 

java -Djava.library.path=/usr/local/lib/jni \
-classpath /usr/local/share/java/glpk-java.jar:. \
Test

The output will be your GLPK version number, for example: 4.47.

Usage with Eclipse

 
Project property settings needed in Eclipse

To use GLPK for Java with Eclipse the GLPK for Java jar library has to be added to the project properties. Furthermore the path to the native DLL library has to be set here. (See screenshot).

Linear Optimization Wrapper for Java

The Linear Optimization Wrapper for Java provides a more intuitive interface to the GLPK for Java API. Columns and rows can be directly accessed via names and indices.

Columns are created like this: 

Problem p = new Problem().
    setName("Cutting Stock");
// x(i,j) : x pieces of product j are cut from stock i
for (int i = 0; i < stock.length; i++) {
    for (int j = 0; j < product.length; j++) {
    p.column("x", i, j).
        type(Problem.ColumnType.INTEGER).
        bounds(0.0, null);
    }
}

Rows can be created and populated like this: 

// demand(j) = sum( x(i,j) )
for (int j = 0; j < product.length; j++) {
    p.row("demand", j).bounds(demand[j], demand[j]);
    for (int i = 0; i < stock.length; i++) {
        p.row("demand", j).
            add(1.0, "x", i, j);
    }
}

You may download the code using subversion: 

svn checkout http://www.xypron.de/svn/linopt/ linopt

For using this library in your Maven project enter the following repository and dependency in your pom.xml (adjust the version number as needed). 

    <repositories>
        <repository>
            <id>XypronRelease</id>
            <name>Xypron Release</name>
            <url>http://rsync.xypron.de/repository</url>
            <layout>default</layout>
        </repository>
    </repositories>
    <dependencies>
        <dependency>
            <groupId>de.xypron.linopt</groupId>
            <artifactId>linopt</artifactId>
            <version>1.10</version>
        </dependency>
    </dependencies>

When testing with Maven it may be necessary to indicate the installation path of the GLPK for Java shared library (.so or .dll). 

mvn clean install -DargLine='-Djava.library.path=/usr/local/lib/jni:/usr/lib/jni'

The exec:java target may require to indicate the installation path of the GLPK for Java shared library in MAVEN_OPTS, e.g. 

export MAVEN_OPTS="-Djava.library.path=/usr/local/lib/jni:/usr/lib/jni"
mvn exec:java

Java ILP

Java ILP provides a java interface to several linear programming solvers including GLPK. It is licences under the GNU Lesser General Public License (LGPL). The link to GLPK uses GLPK for Java.

The homepage http://javailp.sourceforge.net/ provides an example code. According to the homepage GLPK ≥ 4.43 is supported.

Development seems to have stopped. The last code update was on 2012-08-02.

OptimJ

OptimJ is a Java-based modeling language and optimization environment. OptimJ is available with several commercial and non-commercial solvers to select from, including GLPK, and is offered under a variety of licensing, free (of charge) download, and purchase arrangements. OptimJ originates from Ateji, a software company based in Paris, France.

Development seems to have stopped. The latest release dates back to 2011.

Java Native Access

Java Native Access (JNA) can be used to call shared native libraries from Java. The project home is https://github.com/twall/jna.

Using JNA has the following drawbacks:

  • Errors occurring in the GLPK library will terminate the main process.
  • Callbacks cannot be used.

The following example uses JNA to display the GLPK library version number. 

// file GlpkVersion.java

import com.sun.jna.Library;
import com.sun.jna.Native;

public class GlpkVersion {
        /**
         * Interface of the GLPK library.
         */
        public interface Glpk extends Library {
                Glpk INSTANCE = (Glpk) Native.loadLibrary("glpk", Glpk.class);
                String glp_version();
        }

        public static void main(String[] args) {
                System.out.println(Glpk.INSTANCE.glp_version());
        }
}

Compile and run with 

javac -classpath /usr/share/java/jna.jar GlpkVersion.java
java -classpath .:/usr/share/java/jna.jar GlpkVersion

Adjust the classpath according to your JNA installation path.

Obsolete interfaces

GLPK 3.3 offered a Java language binding, written by Yuri Victorovich. This binding was removed from official GLPK distribution in version 4.7, because, at that time, no GNU GPL-compliant Java implementation was available. Third party projects now provide Java bindings for GLPK.

The GLPK 4.8 Java Interface was published by Björn Frank. It is no longer maintained and cannot be used with current versions of GLPK. In particular, users have reported faulty floating point arithmetic when deployed on 64-bit Linux systems.


Python

There are several Python language bindings to choose from. Each provides a differing level of abstraction. All are open source software.

The Scripting plus MathProg page offers further information on the use of Python and GLPK.


PyGLPK

PyGLPK is an encapsulation of GLPK in Python objects (currently maintained 2021). In contrast to Python-GLPK, the language bindings are "handcrafted", thereby enabling a smoother integration within the Python language. PyGLPK is licensed under the GNU General Public License.

PyGLPK 0.3 has been provided 30 May 2010, but is based on the GLPK 4.31 API. Testing (make; make test) fails against GLPK 4.45.

PyMathProg

PyMathProg builds on PyGLPK. PyMathProg is also licensed under the GNU General Public License.

PyMathProg provides a domain-specific language that enables the formulation of linear problems in a form very much like GLPK MathProg (GMPL) or AMPL.

Pyomo

The Python Optimization Modeling Objects (Pyomo) package [1] from Sandia National Laboratories is an open source tool for modeling optimization applications in Python. Pyomo uses the GLPK solver by default, although other solvers can be selected. Pyomo is distributed under a BSD license.

GLPK is interfaced by creating a LP file and running it through GLPSOL via the command line interface and then interpreting the output files.

Strictly speaking Pyomo is not a set of low-level Python language bindings for GLPK — rather Pyomo offers high-level linear programming constructs (similar in expression to MathProg) as well as the normal features of the Python language.

Pyomo is less terse than GLPK MathProg or AMPL as it must be parsed as Python. For instance, the following MathProg statement: 

maximize f: 0.6 * x1 + 0.5 * x2;

equates to, in Pyomo: 

model.f = Objective( expr=0.6 * model.x + 0.5 * model.y, sense=maximize )

Python-GLPK

Python-GLPK by Rogério Reis is a Python language binding for GLPK created using SWIG and licensed under the GNU General Public License (unfortunatly this package is no longer maintained (2021)). It is also available through the Debian package python-glpk.

SWIG allows for easy maintenance as there is very little GLPK specific code present. SWIG also ensures that almost any GLPK library function is available. On the other hand, the client-side calling methods are somewhat clumsy.

The following dependencies (at least) are required for building Python-GLPK:

Usage

The following minimalistic program will show the GLPK version number: 

import glpk
print glpk.glp_version()

Build and install from source

If you cannot (or choose not to) use Debian package python-glpk, you can build and install Python-GLPK from source. Root privileges are required. Here are the steps:

  • Switch to a suitable subdirectory and download the source: 
    wget http://www.dcc.fc.up.pt/~jpp/code/python-glpk/python-glpk_0.4.43.orig.tar.gz
  • Unpack the archive: 
    tar -xzf python-glpk_0.4.43.orig.tar.gz
  • Change to the src directory: 
    cd python-glpk-0.4.43/src/
  • Build and install the software in one hit (note that make install first executes make all): 
    sudo make install
  • Change to the examples directory: 
    cd ../examples
  • Run the confirmation test: 
    python test.py

CVXOPT

CVXOPT is a package for convex optimization, based on the Python language. It provides interfaces to different linear (GLPK, Mosek) and quadratic (Mosek) programming solvers. CVXOPT is being developed by Joachim Dahl and Lieven Vandenberghe.

Sage

Sage is general mathematical software based on Python. While Sage is strictly more than Python, it is nonetheless listed on this page.

The user can elect to link to GLPK, COIN Branch-and-Cut, and CPLEX (as of November 2010, with SCIP support planned). But GLPK remains the default solver for reasons of licensing. Sage can be used for both mixed integer programming and for graph theory problems.

PuLP

PuLP is an LP modeling module for Python. It generates MPS or LP files and submits these to GLPK, COIN CLP/CBC, CPLEX, or XPRESS via the command-line. An MIT license is used. For GLPK, PuLP writes the problem to a CPLEX LP file and then executes a command like the following in a new process: 

glpsol --cpxlp %d-pulp.lp --o %d-pulp.sol [--nomip]

On completion, the solution file in analyzed. Both intermediate files are deleted.

PuLP also has a direct python binding to GLPK (the example above spawns a new process and issues a system command). As of August 2012, this feature was implemented with PyGLPK bindings, but the next version should make use of Python-GLPK bindings (the code has been written and is being evaluated).

yaposib

The Yet Another Python OSI Binding or yabosib project provides OSI bindings — in other words, yaposib wraps the OSI API in python classes. It is slated for official inclusion in COIN-OR suite. yaposib is also designed to work within PuLP.

ecyglpki

A Cython GLPK interface

While using an object-oriented style, these bindings stay relatively close to the GLPK C API. For example, most GLPK function names are essentially retained (dropping the glp_ prefix) and a few similar ones have been added. One of the added functionalities is that row and column names can be used as well as integer indices in most functions.

Some absurdly simple code to give a feel for the bindings: 

# set up the problem
lp = ecyglpki.Problem()
lp.add_named_rows('first', 'second')
lp.set_row_bnds('first', None, 0)
lp.add_named_cols('x', 'y')
lp.set_col_bnds('x', -1, None)
lp.set_mat_col('x', {'first': -1, 'second': 1})
lp.set_col_kind('y', 'binary')
lp.set_obj_coef('x', 1)
lp.set_obj_coef('y', -3)
lp.set_obj_dir('maximize')
# configure and solve
iocp = ecyglpki.IntOptControls() # (default) int. opt. control parameters
iocp.presolve = True
status = lp.intopt(iocp)
if status != 'optimal':
    raise RuntimeError('Error while solving...: ' + status)
# fix the binary variable to its computed value and find exact solution
yval = lp.mip_col_val('y')
lp.set_col_bnds('y', yval, yval)
smcp = ecyglpki.SimplexControls() # (default) simplex control parameters
smcp.presolve = True
status = lp.simplex(smcp)  # solve
if status != 'optimal':
    raise RuntimeError('Error while solving...: ' + status)
smcp.presolve = False
status = lp.exact(smcp)  # now solve exactly
if status != 'optimal':
    raise RuntimeError('Error while solving...: ' + status)

External resources:

The documentation consists of a description of the API, but also contains examples for which the source code is available and can be inspected to get a feel for how to use the package.

swiglpk

Simple swig bindings for the GNU Linear Programming Kit

A description, installation instructions, and an example are available on PyPI: https://pypi.python.org/pypi/swiglpk

The source is available on GitHub: https://github.com/biosustain/swiglpk

ctypes

The ctypes library allows to wrap native library calls.

This example displays the GLPK version number: 

#!/usr/bin/python
from ctypes import *

solver = cdll.LoadLibrary('libglpk.so')
solver.glp_version.restype = c_char_p

print solver.glp_version()

User recommendations

This thread in early-2011 discusses the merits of the various Python bindings:

  • one user reports being unable to build Python-GLPK under Mac OS X, despite several attempts
  • one user recommends PyMathProg and suggests compiling GLPK from scratch, rather than rely on third-party binaries

References

  1. ↑ Hart, William E. (2008). "Python optimization modeling objects (Pyomo)" (PDF). {{cite journal}}: Cite journal requires |journal= (help)


R

R is a free software environment for statistical computing and graphics. The R project is responsible for R. Packages for R are provided by the Comprehensive R Archive Network (CRAN). R is cross-platform and supported on Windows, MacOS X, and Linux.

In addition, R scripts (as can gnuplot scripts) can be use to process GLPK output directly, without the use of dedicated R packages.

Rglpk

Package Rglpk is provided by CRAN — which also contains the reference manual.

To install from repository within R: 

install.packages("Rglpk")

To install from local archive within R: 

install.packages("Rglpk_0.6-3.tar.gz", repos = NULL, type="source")

Debian-based Linux users can also install Rglpk via the Debian package r-cran-rglpk. But it would pay to check on currency.

Rglpk provides two functions:

  • Rglpk_read_file reads a linear problem from a file in either of the following formats: fixed MPS, free MPS, CPLEX, and GMPL.
  • Rglpk_solve_LP solves a linear and mixed linear problems.

The following commands solve a problem provided in GMPL file /home/user/test.mod 

library(Rglpk)
x <- Rglpk_read_file( "/home/user/test.mod", type = "MathProg", verbose = TRUE)
Rglpk_solve_LP(x$objective, x$constraints[[1]], x$constraints[[2]], x$constraints[[3]], x$bounds, x$types, x$maximum)

glpkAPI

The package glpkAPI has not been maintained since 2015.

glpk

The deprecated package glpk has been archived by CRAN. It was based on GLPK 4.8 and never updated since 2006.

Retrieved from "https://en.wikibooks.org/w/index.php?title=GLPK/Print_version&oldid=1844027"