=======================
Discussion About PyGLPK
=======================
-------------
Existing Work
-------------
A Python binding to GLPK `already exists
`_ in the form of Python-GLPK, but
as it is automatically created through `SWIG `_ it is not
very `Pythonic `_.
-----------------------
Building and Installing
-----------------------
Building this module requires that the user have installed the `GLPK
`_ and `GMP `_
libraries. The module builds and appears to work on my simple test files in
Python 2.3, 2.4, and 2.5. Earlier versions of Python will not work.
In the ideal case (e.g., you have GLPK and GMP libraries and headers installed
in default search paths), one would install this through ``make`` and ``make
install``, and be done.
The section on :doc:`Building and Installing <./building-installing>` has more
information.
-------------------------------------
High Level Comparison of C and PyGLPK
-------------------------------------
To use the C API, one would first ``#include "glpk.h"``, create an LPX
structure through ``lpx_create_prob()``, and thence manipulate this structure
with ``lpx_*`` functions to set the data, run the optimization, and retrieve
the desired values.
To use this Python module, one would import the ``glpk`` module, create an LPX
Python object through ``glpk.LPX()``, and thence manipulate this object and the
objects it contains to set the data, run the optimization, and retrieve the
desired values. The Python module calls the C API to support these operations.
-----------------
Design Philosophy
-----------------
PyGLPK has objects floating around everywhere, and very few actual methods.
Wherever possible and sensible, one gets and sets traits of the problem by
accessing a method and directly assigning those traits. An example of this
showing how PyGPLK works and how it does not work might be interesting.
PyGLPK is like this
.. code:: python
lp.maximize = True
lp.cols.add(10)
for col in lp.cols:
col.name = 'x%d' % col.index
col.bounds = 0.0, None
lp.obj[col.index] = 1.0
del lp.cols[2,4,5]
It isn't like this
.. code:: python
lp.set_maximize()
lp.add_cols(10)
for cnum in xrange(lp.num_cols()):
lp.set_col_name(cnum, 'x%d' % cnum)
lp.set_col_bounds(cnum, 0.0, None)
lp.set_obj_coef(cnum, 1.0)
lp.del_cols([2,4,5])
Both design strategies would accomplish the same thing, but there are
advantages in the first way. For example, if I tell you only that columns of an
LP are stored in a sequence ``cols``, for free you already know a lot (assuming
you're familiar with Python):
* You know how to get the number of columns in the LP.
* You know how to get a particular column or a range of columns.
* You know they're indexed from 0.
* You know how to delete them.
-----------------------------------------
Differences Between C GLPK API and PyGLPK
-----------------------------------------
^^^^^^^^
Indexing
^^^^^^^^
Unlike the C API, everything is indexed from 0, not 1: the user does not pass
in arrays (or lists!) where the first element is ignored. Further, one indexes
(for example) the first row by asking for row 0, not 1.
In the comparative examples of parallel C and Python code, wherever possible
and appropriate I sprinkle ``+1`` in the C code. Of course, only a lunatic
would really write code that way, but I do this to highlight this difference,
and second, make it more obvious which portions of C and Python correspond to
each other: it's far easier to see the relation between ``[7, 3, 1, 8, 6]`` and
``[7+1, 3+1, 1+1, 8+1, 6+1]``, versus ``[8, 4, 2, 9, 7]``.
PyGLPK also honors Python's quirk of "negative indexing" used to count from the
end of a sequence, e.g., where index -1 refers to the last item, -2 second to
last item, and so forth. This can be convenient. For example, after adding a
row, you can refer to this row by ``lp.rows[-1]`` rather than having to be
aware of its absolute index.
^^^^^^^^^^^^^^
Error Handling
^^^^^^^^^^^^^^
The GLPK's approach to errors in arguments is deeply peculiar. It writes an
error message and terminate the process, in contrast with many APIs that
instead set or return an error code which can be checked. The PyGLPK takes the
more Pythonic approach of throwing catchable exceptions for illegal arguments.
Unfortunately, to avoid the process being terminated, this requires that
absolutely every argument be vetted, requiring that PyGLPK have the additional
overhead of doing sometimes rather detailed checks of arguments (which are, of
course, checked yet again when the GLPK has access to them). It seems unlikely
that GLPK's design will be improved in this area.
==============
Simple Example
==============
To ground you, we show an example of the module's workings. (This example is
covered in more detail in the examples section.) Taking the introductory
example from the GLPK C API reference manual, we start with the following
example linear program:
.. math::
\begin{aligned}
& \underset{\mathbf{x}}{\text{maximize}} & & Z = 10 x_0 + 6 x_1 + 4 x_2 & \\
& \text{subject to} & & p = x_0 + x_1 + x_2 & \\
& & & q = 10 x_0 + 4 x_1 + 5 x_2 & \\
& & & r = 2 x_0 + 2 x_1 + 6 x_2 & \\
& \text{and bounds of variables} & & - \infty \lt p \leq 100 & 0 \leq x_0 \lt \infty \\
& & & - \infty \lt q \leq 600 & 0 \leq x_1 \lt \infty \\
& & & - \infty \lt r \leq 300 & 0 \leq x_2 \lt \infty \\
\end{aligned}
In the following, we show Python code to define and solve this problem, and
subsequently print out the objective function value as well as the primal
values of the structural variables.
.. code:: python
import glpk # Import the GLPK module
lp = glpk.LPX() # Create empty problem instance
lp.name = 'sample' # Assign symbolic name to problem
lp.obj.maximize = True # Set this as a maximization problem
lp.rows.add(3) # Append three rows to this instance
for r in lp.rows: # Iterate over all rows
r.name = chr(ord('p')+r.index) # Name them p, q, and r
lp.rows[0].bounds = None, 100.0 # Set bound -inf < p <= 100
lp.rows[1].bounds = None, 600.0 # Set bound -inf < q <= 600
lp.rows[2].bounds = None, 300.0 # Set bound -inf < r <= 300
lp.cols.add(3) # Append three columns to this instance
for c in lp.cols: # Iterate over all columns
c.name = 'x%d' % c.index # Name them x0, x1, and x2
c.bounds = 0.0, None # Set bound 0 <= xi < inf
lp.obj[:] = [10.0, 6.0, 4.0] # Set objective coefficients
lp.matrix = [
1.0, 1.0, 1.0, # Set nonzero entries of the
10.0, 4.0, 5.0, # constraint matrix. (In this
2.0, 2.0, 6.0 # case, all are non-zero.)
]
lp.simplex() # Solve this LP with the simplex method
print 'Z = %g;' % lp.obj.value, # Retrieve and print obj func value
print '; '.join( # Print struct variable names and primal values
'%s = %g' % (c.name, c.primal) for c in lp.cols
)
This may produce this output.
.. code::
Z = 733.333; x0 = 33.3333; x1 = 66.6667; x2 = 0