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.
      

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 )
      

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.

Source Code:

• toms431.f, the source code.
• toms431.sh, commands to compile the source code.

Examples and Tests:

• toms431_prb.inp, a sample input file.
• toms431_prb.sh, commands to run the program with the sample input.
• toms431_prb_output.txt, the output from a run of the sample program.

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.