Linear and quadratic programming for small scale problems


Need to find some public domain code - C compatible

I've been searching for some public domain (GPL'd or similar) C-compatible code that will perform linear and/or quadratic programming. I'd appreciate any suggestions from the numerical community.

I did find algorithm 587 in the ACM archives that solves:
min || A x - b||
subject to
E x = f
G x >= h
It's given in single precision only, but gives instructions to edit it into double precision form.
It uses the older style Hollerith character constants that cause problems on some more recent compilers.

This is a bit different that what I'm looking for, which is

min x' Q x / 2 + c' x
subject to
E x = f
xlo <= x <= xhi

although it can be massaged into the proper form.

Update June 17
I got it figured out, I think. I first transformed to a dual problem that turned out to be a linear programming problem, and then solved the linear programming problem with a simple interior-point method approach. I'll post the code later.qp.pdf


Update June 20
You may also want to look at http://www.stanford.edu/~boyd/cvxbook.html .

Update June 22 Here's another reference http://www.princeton.edu/~rvdb/LPbook/ .
Gnu software for large scale LP problems is at http://www.gnu.org/software/glpk/glpk.html .

Posted: Sun - June 6, 2004 at 01:28 PM           | |

©