toms431, a FORTRAN77 code which implements ACM toms algorithm 431, for solving linear and quadratic programming problems.
The program is set up to solve a complementary problem, and it is the user's responsibility to rearrange the data for the linear or quadratic programming problem into a form suitable for the complementary problem.
The linear programming problem is
Find an N vector x solving the problem:
Minimize Z = c' * x
subject to
b <= A * x,
0 < x.
where A is a given M x N matrix and
b is a given M vector.
The quadratic programming problem is
Find an N vector x solving the problem:
Minimize Z = c' * x + x' * Q * x
subject to
b <= A * x,
0 < x.
where A is a given M x N matrix, c
is a given N vector, Q is a given N by N matrix,
and b is a given M vector.
The complementary problem is
Find nonnegative N vectors w and z so that
w = M * z + q
w' * z = 0
where M is a given N x N matrix and q is a
given N vector.
An optimal solution to the quadratic programming problem may be obtained by solving a complementary problem of the form
( v ) = ( Q + Q' -A' ) ( x ) + ( c )
( u ) ( A 0 ) ( y ) ( -b )
with nonegative u, v, x, and y and
requiring (v,u)' * (x,y) = 0, where u denotes the
slack variables of the quadratic program and (y,v)
denotes the variables of the dual problem.
That is, the data for the quadratic programming problem can be rearranged for the complementary problem by setting
w = ( v, u )'
z = ( x, y )'
M = ( Q + Q' -A' )
( A 0 )
q = ( c, -b )'
The data for the linear programming problem can be rearranged for the complementary problem by setting
w = ( v, u )'
z = ( x, y )'
M = ( 0 -A' )
( A 0 )
q = ( c, -b )'
While the text of many ACM toms algorithms is available online through ACM: http://www.acm.org/pubs/calgo or NETLIB: http://www.netlib.org/toms/index.html, most of the early algorithms are not available. This is one of them. I typed it in.
XX <- IP, the number of problems to solve, in I2 format.
XX <- N1, the order of the matrix for problem #1, in I2 format.
AAAA.aaaaaBBBB.bbbbbCCCC.cccccDDDD.dddddEEEE.eeeeeFFFF.fffffGGGG.ggggg
<-- the first COLUMN of the matrix, using 7F10.5 format.
(if N1 is more than 7, use as many more
input lines as necessary.)
<-- followed by COLUMNS 2 through N1.
AAAA.aaaaaBBBB.bbbbbCCCC.cccccDDDD.dddddEEEE.eeeeeFFFF.fffffGGGG.ggggg
<-- the N1 entries of the Q vector. (For a linear programming
problem, set all entries of Q to 0.)
XX <- N2, the order of the matrix for problem #2, in I2 format.
More data for problem 2, 3, and so on.
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
toms431 is available in a FORTRAN77 version.