项目作者: denis-bz

项目描述 :
numpy <--> GLPK Keywords: linear programming, python, numpy, scipy, GLPK 22 Oct
高级语言: Python
项目地址: git://github.com/denis-bz/glp.git
创建时间: 2019-10-22T08:37:32Z
项目社区:https://github.com/denis-bz/glp

开源协议:

下载


glp: numpy <—> GLPK, the gnu linear programming kit

Keywords, tags: linear programming, python, numpy, scipy, GLPK, GMPL, bridge

glp is a lightweight bridge between
the Gnu Linear Programming Kit GLPK
and the numpy-scipy-python world:

  1. numpy/scipy arrays <--> LP( A b c ... ) <--> LP files
  • numpy and scipy help construct large sparse LP models, and connect to dozens of specialized tools
  • GLPK reads and writes LP models in several formats: .mod, .lp (aka cplex), .mps

Requirements: GLPK and
PyGLPK — see “installing” below.

Example: file -> numpy —

  1. import glp
  2. lp = glp.load_lp( ".../my.mps" ) # an LP record with lp.A lp.b lp.c ..., see below

Example: numpy -> file -> solver —

  1. # make numpy/scipy arrays A b c ... that describe your problem
  2. # and put them in a Bag, see "LP standard form" and "LP()" below --
  3. lp = glp.LP( A= b= c= blo= lb= ub= )
  4. # save A b c ... in a text file --
  5. gnulp = glp.save_lp( "my.lp", lp ) # or my.mps or my.glp
  6. # run my.lp -> your solver in a shell or a python subprocess
  7. # read, plot the solution file

LP standard form: A b c blo lb ub

In glp, LP problems are described by a record (struct, Bag)
with 6 numpy arrays A, b, c, blo, lb, ub:

  1. minimize c . x
  2. subject to
  3. blo <= Ax <= b # row bounds, default Ax <= b
  4. lb <= x <= ub # column (variable) bounds, default 0 <= x

In this form, the row bounds b blo and column (variable) bounds lb ub
are nicely symmetric,
and cover all combinations of 1-sided and 2-sided bounds. For lb <= x <= ub:

  1. Lower only: lb .. inf -- no upper bound
  2. Upper only: -inf .. ub -- no lower bound
  3. Both: lb .. ub
  4. Equal: lb == ub
  5. no bounds: -inf .. inf

Row bounds blo <= Ax <= b have the same 5 cases.
(Rows with no bounds are irrelevant, so glpsol removes them, lp_to_linprog too.)

The main data structure: LP( A, b, c ... )

  1. lp = glp.LP( A, b, c, blo=-np.inf, lb=0, ub=np.inf, problemname="name" )

puts A b c ... into a Bag with fields lp.A lp.b ....
A is made sparse
if it isn’t already.
Bounds arrays b blo lb ub are expanded to numpy arrays of float64
of the appropriate size.
These may have +-inf, but no None, no NaN.
LP( ... blo=-np.inf ), the default, constrains all rows Ax <= b;
LP( ... blo=b ) constrains Ax = b.

(A Bag aka Dotdict aka flexible struct
is a dict with bag.key short for bag["key"]
easier to pass around than long arg lists,
and bag.<tab> in IPython shows you the fields.
See the 5-line class Bag( dict ) in zutil.py.)

File and function overview

  1. lprec.py
  2. def LP( A, b, c, blo=-inf, lb=0, ub=inf,
  3. def print_lp( lp, verbose=1, header="", footer="" ):
  4. load_lp.py
  5. def load_lp( lpfile, to="lp", verbose=1 ):
  6. """ GLPK file .mod .mps ... to= "lp" | "linprog" | "glpk"
  7. def save_lp( outfile, lp ):
  8. """ LP() or gnulp -> outfile .mod .mps ... """
  9. lp_gnu.py
  10. def gnulp_to_lp( gnulp, drop_uncon=True, verbose=1 ):
  11. """ gnulp .matrix .rows .cols .obj -> LP( A b c ... ) numpy/scipy arrays
  12. def lp_to_gnulp( lp, verbose=1 ):
  13. """ LP( A b c blo lb ub ... ) -> glpk .matrix .rows .cols ...
  14. # def gnulp_solve( gnulp, solver="interior", verbose=1 ):
  15. # better save_lp | glpsol | load_lp
  16. lp_linprog.py
  17. def lp_to_linprog( lp, verbose=1 ):
  18. """ LP( A b c ... ), see lprec.py
  19. def linprog_to_lp( linp, name="noname" ):
  20. """ test-loopback.py: lp_to_linprog, linprog_to_lp
  21. def rows_le( A, b, blo ):
  22. """ -inf <= Ax <= inf: drop these rows, unconstrained
  23. def split_Ab( A, b, blo ):
  24. """ -> Bag( A_ub b_ub A_eq b_eq )
  25. zutil.py
  26. class Bag( dict ):
  27. """ a dict with d.key short for d["key"], aka Dotdict """
  28. def scan_args( sysargv, globals_, locals_ ):
  29. """ run my.py [a=1 b=None 'c = expr' ...] [file* ...] in shell or IPython

Notes on GLPK and glpsol

GLPK reads and writes LP problems in various formats:

  • .lp aka CPLEX format
  • .mps, an old format used for e.g. Matlab <-> solvers
  • .glp, easy to parse in python or awk
  • .mod, the gnu MathProg language GMPL).
    This is roughly a subset of the AMPL language.

glp.save_lp( "my.mod", lp ) writes a .mod file similar to .lp aka cplex
which is readable in AMPL — in simple cases, mttiw.

GLPK’s solver glpsol has over 50 options, for simplex, interior-point, and mixed-integer (MIP).
It carries the user’s constraint names and variable names through to solution files;
this is essential for making solutions to big problems understandable —
splitting, sorting, plotting thousands of variables.
The simplex solver (not ip ?) does preprocessing to make problems smaller,
in some cases a good deal smaller.

To check a file, glpsol --check --format my.file.
To translate e.g. .mps to .lp, glpsol --check --freemps in.mps --wlp out.lp.
(in.mps.gz or out.lp.gz compress / uncompress with gzip on the fly.)

glp has a minimal glp_solve(), but I prefer to run glpsol with files, like this:

  1. ipython: ... save_lp( "my.glp", LP( A, b, c ... ))
  2. glpsol --options ... my.glp -w my.sol --log my.glpsollog # or whatever solver you like
  3. # see glpsol -h and bin/glpsols
  4. ipython: ... parse my.glp and my.sol, plot

Look at LP in the whole flow, input - optimize - output

For real-world optimization problems,
an LP solver (optimizer) is only part of a flow, a cycle, a process:

  • input: map a problem to a sea of numbers A b c ...
  • run the LP solver -> a sea of numbers x[...]
  • map back: make the solution x[...] understandable, with plots and talks
  • (sotto voce) check that there are no mistakes along the way.

Experts say that commercial solvers are much faster than GLPK,
but GLPK may be fast enough for your problem.

Installing glpk and pyglpk

  1. # first glpk:
  2. download and unpack https://www.gnu.org/software/glpk/.../glpk-4.65.tar.gz
  3. configure --prefix=/opt/local; make; make install
  4. # pyglpk:
  5. pip install --user git+https://github.com/bradfordboyle/pyglpk
  6. # (git clone gets examples/*.py too)
  7. # test:
  8. ipython
  9. import glpk # i.e. pyglpk
  10. print glpk.__file__ # .../glpk.so
  11. gnulp = glpk.LPX() # empty
  12. gnulp = glpk.LPX( gmp="xx.mod" ) # Reading ... Generating ...

GLPK
PyGLPK on github
PyGLPK brief reference
scipy.sparse
LPsolve FAQ
LPsolve doc on file formats
Numerical Recipes p. 537-549: Linear Programming Interior-Point Methods
GLPK runtimes for Netlib and other test cases are under my gists

Comments welcome, test cases welcome.

cheers
— denis 29 October 2019