Method, apparatus, and article of manufacture for performing a pivot-in-place operation for a linear programming problem

A method of reducing computer error in processing a linear programming problem, the method comprising:

• obtaining a first objective function, f, to be optimized;
• obtaining m constraints for the objective function;
• associating each constraint in the form of an equality with a basic artificial variable, wherein an artificial variable is a variable required to be zero;
• converting each constraint in a form of an inequality into a form of an equality by adding a slack variable Yi, wherein Yi is ≧0 and Yi is considered to be a basic variable;
• wherein the constraints can be configured in the format [A][X]+[I][Y]=[B], wherein [A] represents the coefficients for the variables in matrix [X], [Y] represents the variables Yi for i=1 to m and [B] represents a matrix of numbers and [I] represents the identity matrix;
• storing the coefficients for matrix [A] in computer memory;
• storing the values of matrix [B] in computer memory;
• initializing a matrix, [E], having m+2 rows and m+1 columns, wherein the columns are indexed from 0 to m and the rows are indexed from −1 to m, the initializing comprising:
• setting all entries of the row indexed −1 to be all zeros so as to represent coefficients for a second objective function, h;
• associating the row indexed −1 with the second objective function, h;
• associating the row indexed 0 with the first objective function, f;
• setting the rows indexed 0 to m to the equivalent of an m+1 by m+1 identity matrix;
• for i=1 to m, associating each row i with the basic variable associated with constraint i;
• for k=1 to m, associating each column k with the basic variable associated with constraint k;
• storing an initial representation of matrix [E] in computer memory;
• placing the [E] matrix and the [B] matrix in basic feasible form wherein basic feasible form satisfies the conditions that:
• each row of the [E] and the [B] matrix is associated with a basic variable;
• each entry in the [B] matrix associated with a canonical basic variable is non negative;
• and
• no row of the [E] matrix is associated with a basic artificial variable.