Global equation solver and optimizer
AssigneeHoneywell Inc.
InventorDaniel P. Johnson
Life of this patent
Estimating the term…
Abstract
A method to determine global optimality/feasibility/infeasibility when solving a quadratic system of modeling equations for industrial problems includes a bound propagation process to refine bounds and improve linearization, a local linear bounding process to determine feasibility and find approximately feasible solutions, a local linearization process to determine feasibility and local optimality, and a global subdivision search to branch and prune. Applications include solving and optimizing scheduling, planning, operations, inventory, suppliers, ordering, customers, and production problems.
Claims20
A method of solving an operations problem, comprising:
- receiving variables, relationships, and constraints;
- forming a set of non-convex quadratic equations based on the variables, relationships, and constraints;
- solving the set of non-convex quadratic equations by applying a bound propagation process, a local linear bounding process, a local linearization process, and a global subdivision search;
- and
- determining whether a solution is optimal, feasible, or infeasible.
A machine-accessible medium having associated content capable of directing the machine to perform a method of solving a set of non-convex quadratic equations, the method comprising:
- selecting a region bounding all variables;
- applying a bound propagation process to the region to refine the bounds and improve linearization;
- applying a local linear bounding process to the region to determine feasibility and to find approximately feasible solutions;
- applying a local linearization process to the region to determine feasibility and local optimality;
- upon finding an optimal global solution, providing the optimal global solution and information indicating optimality;
- upon finding a feasible global solution, providing the feasible global solution and information indicating feasibility;
- upon determining local infeasibility, eliminating the region from consideration;
- upon determining global infeasibility, providing information indicating infeasibility;
- and
- upon not finding a solution, applying a global subdivision search to the region to produce two or more regions and iteratively applying the bound propagation, local linear bounding, and local linearization processes to each of the two or more regions, until determining the solution is optimal, feasible, or infeasible.
A process of solving a set of non-convex quadratic equations, comprising:
- selecting a region bounding all variables;
- applying a bound propagation process to the region to refine the bounds and improve linearization;
- applying a local linear bounding process to the region to determine feasibility and to find approximately feasible solutions;
- applying a local linearization process to the region to determine feasibility and local optimality;
- upon finding a solution after the local linearization process, providing the solution;
- upon determining infeasibility, eliminating the region from consideration;
- and
- upon not finding the solution after the local linearization process, applying a global subdivision search to the region to produce two or more regions and iteratively applying the bound propagation, local linear bounding, and local linearization processes to each of the two or more regions, until determining the solution is optimal, feasible, or infeasible.
Dependencies are inferred from the claim text.