AUTOMATED DECOMPOSITION FOR MIXED INTEGER LINEAR PROGRAMS WITH EMBEDDED NETWORKS REQUIRING MINIMAL SYNTAX

摘要

Embodiments include techniques 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.

主权项

1. A computer-implemented method, comprising:
receiving, by a processing component, computer-executable query instructions to solve a mixed-integer linear programming (MILP) problem, wherein the query instructions comprise:
a first expression conveying an objective function and at least one side constraint of the MILP problem, wherein the objective function and the at least one side constraint define a master problem of the MILP problem;a second expression conveying a first mapping of data values of graph data associated with the MILP problem to a first graph; anda third expression conveying a selection of a first graph-based algorithm to solve a first subproblem of the MILP problem based on the first graph; replacing, by the processing component, the third expression in the query instructions with a fourth expression as part of a decomposition of the MILP problem, the fourth expression comprising instructions to implement the first graph-based algorithm to solve the first subproblem; and performing, by the processing component, operations of an iteration to solve the MILP problem, wherein the operations of the iteration comprise:
executing the first expression to derive a solution to the master problem; andexecuting the fourth expression to derive a solution to the first subproblem based on the first mapping and the solution to the master problem.