# US 12,112,295 B2 · Domain-aware decomposition for supply chain master planning using linear programming

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,112,295 B2
- Document ID: US12112295B2
- Status: Granted
- Kind: B2
- Application number: 18/543,678
- Filed: 2023-12-18
- Published: 2024-04-11
- Granted: 2024-10-08
- Earliest claimed: 2019-06-03
- Assignees: Blue Yonder Group, Inc.
- Applicants: Blue Yonder Group, Inc.
- Inventors: Devanand R; Narayan Nandeda; Tushar Shekhar
- Web page: https://patentgrep.com/patent/US12112295B2

## CPC

- G06Q 10/087: Inventory or stock management, e.g. order filling, procurement or balancing against orders
- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 17/12: Simultaneous equations {, e.g. systems of linear equations}
- G06F 17/13: Differential equations (using digital differential analysers G06F7/64)
- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- G06Q 10/0877: {by inventory control or reporting using inventory tracking or counting}
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method are disclosed for solving a supply chain planning problem modeled as a linear programming (LP) problem. Embodiments include receiving an LP problem representing a supply chain planning problem for a supply chain network comprising material buffers and resource buffers, partitioning the supply chain network at a complicating node into at least two supply chains sharing the complicating node, formulating a decomposed subproblem for each of the supply chains, calculating an effective dual based, at least in part, on a mathematical difference of at least two dual values calculated by solving the functional-based decomposed subproblems, and generating a globally-optimal LP solution to the LP problem using subgradient descent with the effective dual.

## Claims

### Claim 1

A system of solving a supply chain planning problem modeled as a linear programming problem, comprising:
a computer, comprising a processor and memory, the computer configured to:
receive a current state of one or more items in a supply chain network by one or more imaging devices that generate a mapping of the one or more items in the supply chain network;
check for prior identification of one or more complicating nodes;
partition the supply chain network based on the one or more complicating nodes;
determine whether the partitioned supply chain network generates balanced subproblems;
in response to determining that the partitioned supply chain network generates balanced subproblems, identify a variable partition;
in response to determining that the partitioned supply chain network cannot generate balanced subproblems, partition the supply chain network based on determining that the supply chain network is convergent or divergent, wherein the supply chain network is partitioned as a generic supply chain network in response to determining that the supply chain network cannot be determined to be convergent or divergent;
partition variables of the balanced subproblems by removing variables from each of the balanced subproblems;
partition constraints by generating a list of constraints of the supply chain planning problem for each of the balanced subproblems;
formulate linear programming subproblems based on the partitioned variables and the partitioned constraints;
perform masterless iteration with subgradient descent to iteratively optimize the linear programming subproblems until one or more stopping criteria are reached to generate a solution for the linear programming problem; and
instruct automated machinery to adjust inventory of the one or more items based at least in part on the solution to the linear programming problem.

### Claim 2 (depends on 1)

The system of claim 1, wherein the linear programming problem further comprises a constraint-variable matrix.

### Claim 3 (depends on 1)

The system of claim 1, wherein the constraints comprise one or more of: one or more capacity constraints, one or more material constraints, one or more lead time constraints, one or more transportation constraints and one or more sourcing constraints.

### Claim 4 (depends on 1)

The system of claim 1, wherein the linear programming problem comprises one or more mathematical objective functions representing one or more business objectives, the one or more mathematical objective functions comprising one or more of:
minimizing a quantity of unmet demand, minimizing usage of one or more alternate resources, maximizing usage of one or more primary resources, planning one or more items as just-in-time as possible and minimizing an amount of one or more carried-over items.

### Claim 5 (depends on 4)

The system of claim 4, wherein the one or more business objectives are hierarchical and comprise one or more of: one or more business rules, one or more master planning requirements, one or more scheduling constraints and one or more discrete constraints.

### Claim 6 (depends on 1)

The system of claim 1, wherein the one or more complicating nodes are determined based on determining whether one or more material or one or more resource buffers for the supply chain network of the supply chain planning problem have been previously identified as one or more complicating constraints.

### Claim 7 (depends on 1)

The system of claim 1, wherein the determination of whether the partitioned supply chain network generates balanced subproblems is based on checking that a number of constraints corresponding to the subproblems have equal sizes.

### Claim 8

A computer-implemented method, comprising:
receiving a current state of one or more items in a supply chain network by one or more imaging devices that generate a mapping of the one or more items in the supply chain network;
receiving a current state of one or more items in a supply chain network by one or more imaging devices that generate a mapping of the one or more items in the supply chain network;
checking for prior identification of one or more complicating nodes;
partitioning the supply chain network based on the one or more complicating nodes;
determining whether the partitioned supply chain network generates balanced subproblems;
in response to determining that the partitioned supply chain network generates balanced subproblems, identifying a variable partition;
in response to determining that the partitioned supply chain network cannot generate balanced subproblems, partitioning the supply chain network based on determining whether that the supply chain network is convergent or divergent, wherein the supply chain network is partitioned as a generic supply chain network in response to determining that the supply chain network cannot be determined to be convergent or divergent;
partitioning variables of the balanced subproblems by removing variables from each of the balanced subproblems;
partitioning constraints by generating a list of constraints of the supply chain planning problem for each of the balanced subproblems;
formulating linear programming subproblems based on the partitioned variables and the partitioned constraints;
performing masterless iteration with subgradient descent to iteratively optimize the linear programming subproblems until one or more stopping criteria are reached to generate a solution for the linear programming problem; and
instructing automated machinery to adjust inventory of the one or more items based at least in part on the solution to the linear programming problem.

### Claim 9 (depends on 8)

The method of claim 8, wherein the linear programming (LP) problem further comprises a constraint-variable matrix.

### Claim 10 (depends on 8)

The method of claim 8, wherein the constraints comprise one or more of: one or more capacity constraints, one or more material constraints, one or more lead time constraints, one or more transportation constraints and one or more sourcing constraints.

### Claim 11 (depends on 8)

The method of claim 8, wherein the linear programming problem comprises one or more mathematical objective functions representing one or more business objectives, the one or more mathematical objective functions comprising one or more of:
minimizing a quantity of unmet demand, minimizing usage of one or more alternate resources, maximizing usage of one or more primary resources, planning one or more items as just-in-time as possible and minimizing an amount of one or more carried-over items.

### Claim 12 (depends on 11)

The method of claim 11, wherein the one or more business objectives are hierarchical and comprise one or more of: one or more business rules, one or more master planning requirements, one or more scheduling constraints and one or more discrete constraints.

### Claim 13 (depends on 8)

The method of claim 8, wherein the one or more complicating nodes are determined based on determining whether one or more material or one or more resource buffers for the supply chain network of the supply chain planning problem have been previously identified as one or more complicating constraints.

### Claim 14 (depends on 8)

The method of claim 8, wherein the determination of whether the partitioned supply chain network generates balanced subproblems is based on checking that a number of constraints corresponding to the subproblems have equal sizes.

### Claim 15

A non-transitory computer-readable medium embodied with software, the software when executed:
receives a current state of one or more items in a supply chain network by one or more imaging devices that generate a mapping of the one or more items in the supply chain network;
checks for prior identification of one or more complicating nodes;
partitions the supply chain network based on the one or more complicating nodes;
determines whether the partitioned supply chain network generates balanced subproblems;
in response to determining that the partitioned supply chain network generates balanced subproblems, identifies a variable partition;
in response to determining that the partitioned supply chain network cannot generate balanced subproblems, partitions the supply chain network based on determining that the supply chain network is convergent or divergent, wherein the supply chain network is partitioned as a generic supply chain network in response to determining that the supply chain network cannot be determined to be convergent or divergent;
partitions variables of the balanced subproblems by removing variables from each of the balanced subproblems;
partitions constraints by generating a list of constraints of the supply chain planning problem for each of the balanced subproblems;
formulates linear programming subproblems based on the partitioned variables and the partitioned constraints;
performs masterless iteration with subgradient descent to iteratively optimize the linear programming subproblems until one or more stopping criteria are reached to generate a solution for the linear programming problem; and
instructs automated machinery to adjust inventory of the one or more items based at least in part on the solution to the linear programming problem.

### Claim 16 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the linear programming problem further comprises a constraint-variable matrix.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein the constraints comprise one or more of: one or more capacity constraints, one or more material constraints, one or more lead time constraints, one or more transportation constraints and one or more sourcing constraints.

### Claim 18 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the linear programming problem comprises one or more mathematical objective functions representing one or more business objectives, the one or more mathematical objective functions comprising one or more of:
minimizing a quantity of unmet demand, minimizing usage of one or more alternate resources, maximizing usage of one or more primary resources, planning one or more items as just-in-time as possible and minimizing an amount of one or more carried-over items.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein the one or more business objectives are hierarchical and comprise one or more of: one or more business rules, one or more master planning requirements, one or more scheduling constraints and one or more discrete constraints.

### Claim 20 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the one or more complicating nodes are determined based on determining whether one or more material or one or more resource buffers for the supply chain network of the supply chain planning problem have been previously identified as one or more complicating constraints.