GLPK/Python

From Wikibooks, open books for an open world
Jump to: navigation, search

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.


Python-GLPK[edit]

Python-GLPK by Rogério Reis is a Python language binding for GLPK created using SWIG and licensed under the GNU General Public License. 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[edit]

The following minimalistic program will show the GLPK version number:

import glpk
print glpk.glp_version()

Build and install from source[edit]

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
    

PyGLPK[edit]

PyGLPK is an encapsulation of GLPK in Python objects. 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[edit]

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[edit]

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 )

CVXOPT[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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

User recommendations[edit]

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[edit]