Back to results
US 8,566,267 B1Granted
Method, apparatus, and article of manufacture for solving linear optimization problems
AssigneeEuler Optimization, Inc.
InventorsCarl Scotius Ledbetter, Jr., Evar Dare Nering
Life of this patent
Estimating the term…
Abstract
In accordance with one embodiment, a method of reducing computer error in processing a linear programming problem can be accomplished by obtaining a first objective function, f, to be optimized; obtaining a second objective function, h; and optimizing first objective function f and optimizing second objective function h so as to reduce computer error.
Claims16
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 Y, 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;
- manipulating in the computer the [E] matrix relative to the [B] matrix as part of the process of optimizing first objective function f and optimizing second objective function h so as to reduce computer error.
13 more elements
An article of manufacture comprising:
- a non-transitory tangible computer usable medium comprising computer readable program code embodied therein for causing a reduction in computer error in processing a linear programming problem, the computer readable program code in said article of manufacture comprising:
- computer readable program code for causing a computer to effect obtaining a first objective function, f, to be optimized;
- computer readable program code for causing the computer to effect obtaining m constraints for the objective function;
- computer readable program code for causing the computer to effect 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;
- computer readable program code for causing the computer to effect 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;
- computer readable program code for causing the computer to effect storing the coefficients for matrix [A] in computer memory;
- computer readable program code for causing the computer to effect storing the values of matrix [B] in computer memory;
- computer readable program code for causing the computer to effect 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:
- computer readable program code for causing the computer to effect setting all entries of the row indexed −1 to be all zeros so as to represent coefficients for a second objective function, h;
- computer readable program code for causing the computer to effect associating the row indexed −1 with the second objective function, h;
- computer readable program code for causing the computer to effect associating the row indexed 0 with the first objective function, f;
- computer readable program code for causing the computer to effect setting the rows indexed 0 to m to the equivalent of an m+1 by m+1 identity matrix;
- computer readable program code for causing the computer to effect for i=1 to m, associating each row i with the basic variable associated with constraint i;
- computer readable program code for causing the computer to effect 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;
- computer readable program code for causing the computer to effect manipulating in the computer the [E] matrix relative to the [B] matrix as part of the process of optimizing first objective function f and optimizing second objective function h so as to reduce computer error.
14 more elements
Dependencies are inferred from the claim text.