Back to results
US 8,359,286 B1Granted
Method, apparatus, and article of manufacture for solving linear optimization problems including linear programming problems and systems of linear equations
AssigneeEuler Optimization, Inc.
InventorsEvar Dare Nering, Carl Scotius Ledbetter, Jr.
Life of this patent
Estimating the term…
Abstract
In accordance with one embodiment of the invention, a method of optimizing a linear equation optimality problem subject to a change of conditions can be accomplished. The method can include determining a first set of conditions for the linear equation optimality problem; initiating processing by a computer to optimize the optimality problem in accordance with the first set of conditions; determining a second set of conditions different from the first set of conditions; continuing processing with the computer to optimize the optimality problem by using the second set of conditions without having to re-initialize the computer.
Claims16
A method of optimizing a linear optimization problem subject to a change of constraints, said method comprising:
- determining a first set of constraints for said linear optimization problem;
- initializing the optimization problem into an initial feasible format to be operated on by the computer;
- initiating processing by a computer to optimize said optimization problem in accordance with said first set of constraints;
- determining a second set of constraints different from said first set of constraints;
- continuing processing with said computer to optimize said optimization problem by using said second set of constraints in place of said first set of constraints without having to re-initialize the optimization problem into another initial feasible format;
- wherein said optimization problem has “m” constraints and wherein said determining said first set of constraints for said linear optimization problem comprises:
- determining if said constraint(s) contain any inequalities;
- determining if said constraint(s) contain any equalities;
- modifying each of said equality constraint(s) by adding a different artificial variable to each of said equality constraint(s);
- converting each of said inequality constraint(s) by adding a different canonical variable to each of said inequality constraint(s) so as to make each inequality constraint an equality;
- wherein the constraints j=1naijxj+yi=bi with yi 0 for i=1, . . . , m and with each yi being a slack variable satisfy the relationship [A][X]+[I][Y]=[B],
- wherein [A] is a matrix having m rows and n columns and contains the values aij for i=1, . . . , m and for j=1, . . . , n and represents the coefficients for the variables in matrix [X],
- wherein [X] is a matrix having n rows and one column and storing the values xj for j=1, . . . , n,
- wherein [Y] is a matrix having m rows and one column and represents the variables yi for i=1 to m and
- wherein [B] is a matrix having m rows and one column and represents a matrix of numbers bj for i=1, . . . , m, and
- wherein [I] is an identity matrix having m rows and m columns.
13 more elements
An article of manufacture comprising:
- a non-transitory computer usable medium having computer readable program code means embodied therein for causing optimization of a linear optimization problem subject to a change of constraints, the computer readable program code means in said article of manufacture comprising:
- computer readable program code for causing a computer to effect determining a first set of constraints for said linear optimization problem;
- computer readable program code for causing said computer to effect initiating processing by a computer to optimize said optimization problem in accordance with said first set of constraints;
- computer readable program code for causing said computer to effect determining a second set of constraints different from said first set of constraints;
- computer readable program code for causing said computer to effect continuing processing with said computer to optimize said optimization problem by using said second set of constraints in place of said first set of constraints without having to re-initialize the optimization problem into the initial format;
- wherein said optimization problem has “m” constraints and wherein said computer readable program code for causing said computer to effect determining said first set of constraints for said optimization problem comprises:
- computer readable program code for causing said computer to effect determining if said constraint(s) contain any inequalities;
- computer readable program code for causing said computer to effect determining if said constraint(s) contain any equalities;
- computer readable program code for causing said computer to effect modifying each of said equality constraint(s) by adding a different artificial variable to each of said equality constraint(s);
- computer readable program code for causing said computer to effect converting each of said inequality constraint(s) by adding a different canonical variable to each of said inequality constraint(s) so as to make each inequality constraint an equality;
- computer readable program code for causing said computer to effect representing the constraints as matrices in accordance with the relationship:
- [A][X]+[I][Y]=[B]
- wherein for the constraints j=1naijxj+yi=bi with yi 0 for i=1, . . . , m and with each yi being a slack variable:
- [A] is a matrix having m rows and n columns and contains the values aij for i=1, . . . , m and for j=1, . . . , n and represents the coefficients for the variables in matrix [X],
- [X] is a matrix having n rows and one column and storing the values x for j=1, . . . , n,
- [Y] is a matrix having m rows and one column and represents the variables yi for i=1 to m,
- [B] is a matrix having m rows and one column and represents a matrix of numbers bi for i=1, . . . , m, and
- [I] is an identity matrix having m rows and m columns.
15 more elements
Dependencies are inferred from the claim text.