NEW PySimplex Mixed Integer Linear Programming

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.*-*-*.com/

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:

Quote:

>>> 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.

Quote:

>>> (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.*-*-*.com/

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.*-*-*.com/ ~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

--

-------- comp.lang.python.announce (moderated) --------

Python Language Home Page: http://www.*-*-*.com/

-------------------------------------------------------