From bug-octave-request at bevo dot che dot wisc dot edu Thu Dec  4 11:31:33 2003
Subject: LP contribution to octave?
From: Vic Norton <vic at norton dot name>
To: bug-octave at bevo dot che dot wisc dot edu, cgijobs@users.sourceforge.net
Date: Thu, 4 Dec 2003 11:15:00 -0600

Hello cgijobs and bug-octave,

For my own purposes I am writing octave code for phase 2 of the simplex
method via triangular decompositions. This is procedure is described in
         J. Stoer & R. Bulirsch
         Introduction to Numerical Analysis
         Springer-Verlag, New York, 1980
         Section 4.10 The Simplex Method

Here it is assumed that the linear programming problem has been reduced
to
               maximize x(p)
         subject to the constraints
               A * x = b
               x(i) >= 0  for all i in I
         where A is m x n of rank m, b is m x 1, and I is a vector of
         indices in N = [1:n] that does not contain p

and that a feasible basis J containing p is known.

Our function will look something like this:

    function  x = simp2(A, b, I, J, jp)
    #----------------------------------------------------------------
    #
    #  Input
    #     A     - m x n coefficient matrix of rank m
    #     b     - m x 1 vector
    #     I     - vector of indices in N = [1:n] not containing p
    #     J     - m-vector of indices containing p. J represents
    #             a feasible basis. Thus
    #                  A(:, J) is nonsingular and all the
    #                  I-coefficients of
    #                     xJ = (A(:, J)**(-1)) * b
    #                  are nonnegative.
    #     jp    - the index of p in J: J(jp) = p
    #
    #  Output
    #     x     - n x 0 or n x 1 vector
    #             if not n x 0, x is an optimal basic-feasible-solution
    #             of the problem
    #                       maximize x(p)
    #                  subject to the constraints
    #                       A * x = b
    #                       x(i) >= 0  for all i in I
    #
    #----------------------------------------------------------------



I wonder if this routine might be a reasonable contribution to octave.
If it would, I would appreciate any guidelines you could send me. On the
other hand, if good a good linear programming routine is already
available in octave, I would appreciate knowing that too.


Regards,

Vic

-- 
*---* mailto:vic at norton dot name
|     Victor Thane Norton, Jr.
|     Mathematician and Motorcyclist
|     phone: 419-353-3399
*---* http://vic.norton.name



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------