[Matrix-SIG] reAnnounce PySimplex Mixed Integer Linear Programming

[Aaron Watters]

This is a major bugfix and enhancement announcement.
Many thanks to those who commented especially
Hans D. Mittelmann of ASU who helped me flush out several
MPS interpretation errors.  Now I get the results advertised
by netlib (they weren't wrong after all!).

ANNOUNCE PySimplex Mixed Integer Linear Programming 0.1
===================================================

Readers are asked to take a look at and maybe try out
my newly released PySimplex beta Python modules
for Linear Programming.  This software is available
for any purpose, provided as is with no warrantee.
Please see the COPYRIGHT for details.

http://www.pythonpros.com/arw/pysimplex

Pysimplex provides some basic symbolic programming
tools for constructing, solving and optimizing
systems of linear equations and inequalities.
It includes an implementation of the classical
SIMPLEX linear optimization algorithm as well as a filter for parsing
and
optimizing linear models encoded using the standard MPS format.

Perhaps the most compelling aspect of these modules is the way they
allow the user or programmer to construct models in a straightforward
symbolic manner.  For example the following constraint model

  x>=1 and y>=1 and
  x+2*y-1.5 >= 0 and
  y-3*x-0.9 >= 0

may be constructed at the python command line as follows:

>>> v = VariableNamer()
>>> x,y = v.x, v.y
>>> constraints = all_positive(v, x-1, y-1, x+2*y-1.5, y-3*x-0.9)

and the following interaction computes the maximal value for the
objective
function -x-y within this system of constraints.

>>> (sys, ob) = constraints.rsimplex(-x-y)
>>>
>>> sys({})
{'_free20': 7.3, 'x': 1.0, 'y': 3.9, '_free19': 2.9}

Thus the maximum value for -x-y is achieved at x=1.0 and y=3.9.

More interestingly these modules also allow the optimization of
an objective function subject to linear constraints and additional
constraints that some of the variables must have integer or binary
(0 or 1) values.  The function below finds the smallest number of
whole currency units whose value sum to within 3 cents less than 1199.03

dollars.
<pre>
def currencytest():
    """find the smallest number of whole currency units no more
       than 3 cents less than $1199.03 (within 1% of optimal)"""
    # set the goal in dollars, and discrepancy allowed
    goalamount = 1199.03
    error_dollars = 0.03
    # create variables for the model
    v = VariableNamer()
    dollar = v.dollar; franc = v.franc;  yen = v.yen
    pound = v.pound; mark = v.mark; peseta = v.peseta
    yuan = v.yuan;  ruble = v.ruble; candollar = v.candollar
    diff = v.diff; currencyvalue = v.currencyvalue
    # jun 5 1998, conversion rates
    yendollar = 1/138.0; poundollar = 1/0.61; francdollar = 1/5.74
    markdollar = 1/1.78; pesetadollar = 1/151.0
    yuandollar = 1/8.28; rubledollar = 1/6.0; candollardollar = 1/1.46
    # define equalities for amount and discrepancy
    amount = NamedTransform(v,
      diff =          goalamount - currencyvalue,
      currencyvalue = +dollar +yendollar*yen +poundollar*pound
                      +francdollar* +markdollar*mark
+pesetadollar*peseta
                      +yuandollar*yuan +rubledollar*ruble
                      +candollardollar*candollar )
    # define error tolerance
    error_allowed = all_positive(v, error_dollars-diff)
    constraints = amount & error_allowed
    print "constraints"
    print constraints
    # define the objective: minimize number of whole units
    units = dollar+yen+pound+franc+mark+peseta+yuan+ruble+candollar
    # minimize
    (s,o) = constraints.nsimplex(
              -units,
              integervars= [franc, pound, yen, dollar, mark, peseta,
yuan,
                            ruble,  candollar],
              near=0.01)
    # print a report on minimization
    sub = s({})
    items = sub.items()
    items.sort()
    for (a,b) in items:
        if b>0.01:
            print "hand the customer %s %s's" % (b,a)
    total = sub["currencyvalue"]
    print "total is worth %s dollars" % total
    print "units", units.evalconst(sub)
</pre>
When evaluated this function prints
<pre>
hand the customer 1199.00875109 currencyvalue's
hand the customer 0.0212489110635 diff's
hand the customer 2.0 dollar's
hand the customer 730.0 pound's
hand the customer 1.0 ruble's
hand the customer 1.0 yuan's
total is worth 1199.00875109 dollars
units 734.0
</pre>
Thus 2 dollars and 730 pounds and 1 ruble and 1 yuan sum to value
1199.0087 which is within 3 cents of 1199.03, and these 734 currency
units are within 7 units of the least number of currency units
with value within 3 cents
less than 1199.03. (In fact rerunning the function with near=0
shows that this is the optimal such number of units.  Note that reducing

the error tolerance to 1 cent makes it a noticably harder,
i.e., slower, problem.)

Requirements
============

This software requires Python and the Python Numeric extensions.
Easy installations for Python and the Numeric extensions may be obtained

via links starting at http://www.python.org
for Windows 95, NT and many other platforms.

Thanks
======

Many thanks to Guido van Rossum, Jim Hugunin (the primary developers of
Python
and Numpy respectively) as well as the other contributors to Numpy,
especially Dave Ascher and Paul F. Dubois, and to
John W. Gregory and Robert Fourer of the Linear Programming FAQ, as well
as to
<a href="http://www-leland.stanford.edu/~digenova/dantzig/">George
Dantzig</a>
pioneer of the simplex method.

   -- Aaron Watters
===
Yet what are such gaieties to me
Whose thoughts are full of indices and surds?
x**2 + 7*x + 53
= 11/3
 -- Lewis Carroll