Systems and methods based on generalized multi-level search heuristic for production network models
Disclosed herein are methods and systems that construct an optimization capability that is able to solve optimization models of supply chain problems faster and with higher quality solutions than prior approaches.
1. A computer-implemented method comprising:
constructing, by a processor, a representation of a Mixed Integer Programming (MIP) problem by defining nodes and arcs that are parametrized independent of input data;
generating, by the processor, one or more flow nodes, one or more production nodes and one or more arcs in a production network model for specific instances of the MIP problem by mapping the input data to parameters, each production node incorporating variables that are in three or more constraints, with the production network model incorporating one or more directionality bits; and
determining, by the processor, a solution to the representation of the MIP problem based on feasible flows on the arcs in conjunction with a parametrized multi-level search heuristic.
2. The computer-implemented method of claim 1 , wherein input into the parametrized multi-level search heuristic comprises: a sequence of demands; a percentage of each demand to be satisfied in each pass; and a warm start solution.
3. The computer-implemented method of claim 2 , wherein the arcs can be sorted first by their respective flow quantities in the warm start solution, and second, by linear relaxation.
4. The computer-implemented method of claim 2 , wherein the parametrized multi-level search heuristic comprises bottom-up dynamic programming.
5. The computer-implemented method of claim 1 , wherein the three or more constraints are each annotated with a category; and a directionality of each constraint within the category is inferred.
6. A computing apparatus comprising:
a processor; and
a memory storing instructions that, when executed by the processor, configure the apparatus to:
construct, by the processor, a representation of a Mixed Integer Programming (MIP) problem by defining nodes and arcs that are parametrized independent of input data;
generate, by the processor, one or more flow nodes, one or more production nodes and one or more arcs in a production network model for specific instances of the MIP problem by mapping the input data to parameters, each production node incorporating variables that are in three or more constraints, with the production network model incorporating one or more directionality bits; and
determine, by the processor, a solution to the representation of the MIP problem based on feasible flows on the arcs in conjunction with a parametrized multi-level search heuristic.
7. The computing apparatus of claim 6 , wherein input into the parametrized multi-level search heuristic comprises: a sequence of demands; a percentage of each demand to be satisfied in each pass; and a warm start solution.
8. The computing apparatus of claim 7 , wherein the arcs can be sorted first by their respective flow quantities in the warm start solution, and second, by linear relaxation.
9. The computing apparatus of claim 7 , wherein the parametrized multi-level search heuristic comprises bottom-up dynamic programming.
10. The computing apparatus of claim 6 , wherein the three or more constraints are each annotated with a category; and a directionality of each constraint within the category is inferred.
11. A non-transitory computer-readable storage medium, the computer-readable storage medium including instructions that when executed by a computer, cause the computer to:
construct, by a processor, a representation of a Mixed Integer Programming (MIP) problem by defining nodes and arcs that are parametrized independent of input data;
generate, by the processor, one or more flow nodes, one or more production nodes and one or more arcs in a production network model for specific instances of the MIP problem by mapping the input data to parameters, each production node incorporating variables that are in three or more constraints, with the production network model incorporating one or more directionality bits; and
determine, by the processor, a solution to the representation of the MIP problem based on feasible flows on the arcs in conjunction with a parametrized multi-level search heuristic.
12. The non-transitory computer-readable storage medium of claim 11 , wherein input into the parametrized multi-level search heuristic comprises: a sequence of demands; a percentage of each demand to be satisfied in each pass; and a warm start solution.
13. The non-transitory computer-readable storage medium of claim 12 , wherein the arcs can be sorted first by their respective flow quantities in the warm start solution, and second, by linear relaxation.
14. The non-transitory computer-readable storage medium of claim 12 , wherein the parametrized multi-level search heuristic comprises bottom-up dynamic programming.
15. The non-transitory computer-readable storage medium of claim 11 , wherein the three or more constraints are each annotated with a category; and a directionality of each constraint within the category is inferred.