Domain-aware decomposition for supply chain master planning using linear programming

A computer-implemented method for supply chain network partitioning, comprising:

• modelling, by a computer comprising a processor and a memory, the supply chain network as a graph;
• traversing, by the computer, the graph to apply a maxflow-mincut process to the graph;
• in response to detecting that one or more subproblems are balanced, generating, by the computer, a first connected components list and one or more first complicating links;
• in response to detecting that the one or more subproblems are not balanced, partitioning, by the computer, the supply chain network by:
• applying, by the computer, a decomposition process according to a classification of the supply chain network;
• assigning, by the computer, one or more levels to each resource and material buffer according to corresponding placement in the supply chain network;
• determining, by the computer, which of one or more buffers has two or more flows or operations;
• determining, by the computer, a complicating connecting entity having a lowest assigned level, and removing a resource load or material flow from each complicating entity;
• searching, by the computer, for one or more connected entities using a depth-first-search for one or more connected nodes for each operation in each of the removed resource loads and the removed material flows;
• iteratively processing, by the computer, each common connected node as a complicating entity;
• and
• providing, by the computer, a second connected component list and one or more second complicating links of the supply chain network;
• and
• generating, by the computer, one or more decomposed supply chain subproblems for solving, by the computer, the one or more decomposed supply chain subproblems using masterless iteration with subgradient descent to generate a globally-optimal linear-programming solution for the supply chain network, and causing at least one automated supply-chain operation comprising production, transportation, or inventory movement according to the globally-optimal linear-programming solution.

A non-transitory computer-readable storage medium embodied with software for supply chain network partitioning, the software when executed:

• models the supply chain network as a graph;
• traverses the graph to apply a maxflow-mincut process to the graph;
• in response to detecting that one or more subproblems are balanced, generates a first connected components list and one or more first complicating links;
• in response to detecting that the one or more subproblems are not balanced, partitions the supply chain network by:
• applying a decomposition process according to a classification of the supply chain network;
• assigning one or more levels to each resource and material buffer according to corresponding placement in the supply chain network;
• determining which of one or more buffers has two or more flows or operations;
• determining a complicating connecting entity having a lowest assigned level, and removing a resource load or material flow from each complicating entity;
• searching for one or more connected entities using a depth-first-search for one or more connected nodes for each operation in each of the removed resource loads and the removed material flows;
• iteratively processing each common connected node as a complicating entity;
• and
• providing a second connected component list and one or more second complicating links of the supply chain network;
• and
• generates one or more decomposed supply chain subproblems for solving the one or more decomposed supply chain subproblems using masterless iteration with subgradient descent to generate a globally-optimal linear-programming solution for the supply chain network, and causing at least one automated supply-chain operation comprising production, transportation, or inventory movement according to the globally-optimal linear-programming solution.