toms431


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.

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.
          

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

toms431 is available in a FORTRAN77 version.

Related Programs:

toms431_test

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:


Last revised on 15 November 2023.