Automated decomposition for mixed integer linear programs with embedded networks requiring minimal syntax
US9213550B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | May 27, 2015 |
| Grant date | Dec 15, 2015 |
| Priority date | — |
| Expiry date | May 27, 2035 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/11
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An apparatus includes a communications component to receive computer-executable query instructions to solve a MILP problem, the query instructions including a first expression conveying an objective function and side constraint that define a master problem of the MILP problem, a second expression conveying a mapping of graph data to a graph, and a third expression conveying a selection of a graph-based algorithm to solve a subproblem of the MILP problem; a subproblem component to replace the third expression with a fourth expression during decomposition of the MILP problem, the fourth expression including instructions to implement the graph-based algorithm to solve the subproblem; and an execution control component to perform iterations of solving the MILP problem that include executing the first expression to derive a solution to the master problem; and executing the fourth expression to derive a solution to the subproblem based on the mapping and the master problem solution.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.