# TOMS431 A Computer Routine for Quadratic and Linear Programming Problems

TOMS431 is a FORTRAN77 library 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.
```

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

### Usage:

toms431 < input_file
where input_file contains the following records:
```            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.
```

### Languages:

TOMS431 is available in a FORTRAN77 version.

### Reference:

1. Arunachalam Ravindran,
Algorithm 431: A Computer Routine for Quadratic and Linear Programming Problems,
Communications of the ACM,
Volume 15, Number 9, September 1972, pages 818-820.

### List of Routines:

• MAIN controls the computation.
• MATRIX initializes data and reads in the matrix.
• INITIA finds an initial almost-complementary solution.
• NEWBAS chooses a new basis column to enter the basis.
• SORT chooses the pivot row.
• PIVOT performs the pivot operation.
• PPRINT prints the current solution.

You can go up one level to the FORTRAN77 source codes.

Last revised on 23 January 2006.