Systems and methods based on generalized multi-level search heuristic for production network models

Patent metadata

Field	Value
Publication number	US-12354061-B2
Application number	US-202318478142-A
Country	US
Kind code	B2
Filing date	Sep 29, 2023
Priority date	Jun 28, 2022
Publication date	Jul 8, 2025
Grant date	Jul 8, 2025

Abstract

Disclosed herein are methods and systems for solving a production network model by iteratively cascading supply decisions. Upstream supply decisions are fixed iteratively, and cascaded down the network in a general way that is independent of any particular use case.

First claim

What is claimed is:

1. Computer-implemented method for iterative supply cascading, the method comprising:
receiving, by a processor, a production network model, a first Boolean parameter, and a second Boolean parameter;
converting, by the processor, the production network model to a linear program;
determining, by the processor, a first optimal solution of the linear program;
performing, by the processor, a topological sort of the production network model;
addressing, by the processor, one or more cycles present in the production network model;
in a first iteration:
receiving, by the processor, a set of multi-level search parameters;
executing, by the processor, a multi-level search in parallel;
receiving, by the processor, a limit parameter;
determining, by the processor, a total number of iterations;
in the first iteration and subsequent iterations:
determining, by the processor, a second optimal solution across all iterations;
fixing, by the processor, one or more node flows for a current iteration for a subset of production nodes in the production network model;
iteratively:
executing, by the processor, the multi-level search in parallel, using the fixed one or more node flows; and
increasing, by the processor, an iteration number;
until either:
an objective value is less than a threshold; or
the total number of iterations is reached; or a time limit is reached; and
selecting, by the processor, a third optimal solution.

2. The computer-implemented method of claim 1 , wherein:
the first Boolean parameter specifies whether to fix supply quantities in an output solution, or fix the supply quantities in a warm start; and
the second Boolean parameter specifies whether to use an optimal solution of a linear relaxation as an initial warm start.

3. The computer-implemented method of claim 1 , wherein addressing the one or more cycles comprises:
applying, by the processor, a cycle-breaking transformation to the production network model.

4. The computer-implemented method of claim 1 , wherein the total number of iterations is equal to either:
a number of iterations to perform provided in the limit parameter; or
the time limit divided by a time taken to perform the first iteration.

5. The computer-implemented method of claim 1 , wherein after the first iteration, fixing the one or more node flows comprises:
re-evaluating, by the processor, a linear relaxation using the one or more node flows that are fixed to a respective value in a most recent optimal solution.

6. The computer-implemented method of claim 1 , wherein after the first iteration, fixing the one or more node flows comprises:
creating, by the processor, a new production network model;
eliminating, by the processor, fixed nodes that have a flow of zero; and
adding, by the processor, one or more supply nodes to replace nodes that are fixed to a positive flow.

7. The computer-implemented method of claim 1 , where the subset of production nodes is a percentage of iterations completed multiplied by a total number of nodes in the production network model.

8. The computer-implemented method of claim 1 , wherein parametrization of the multi-level search comprises at least one of: a warm start solution, a demand sequence, and a pass count.

9. The computer-implemented method of claim 1 , wherein the production network model is generated by:
constructing, by the processor, a representation of a Mixed Integer Programming (MIP) problem by defining nodes and arcs that are parametrized independent of input data; and
generating, by the processor, one or more flow nodes, one or more production nodes and one or more arcs in the 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.

10. Computing apparatus comprising:
a processor; and
a memory storing instructions that, when executed by the processor, configure the apparatus to:
receive, by the processor, a production network model, a first Boolean parameter, and a second Boolean parameter;
convert, by the processor, the production network model to a linear program;
determine, by the processor, a first optimal solution of the linear program;
perform, by the processor, a topological sort of the production network model;
address, by the processor, one or more cycles present in the production network model;
in a first iteration:
receive, by the processor, a set of multi-level search parameters;
execute, by the processor, a multi-level search in parallel;
receive, by the processor, a limit parameter;
determine, by the processor, a total number of iterations;
in the first iteration and subsequent iterations:
determine, by the processor, a second optimal solution across all iterations;
fix, by the processor, one or more node flows for a current iteration for a subset of production nodes in the production network model;
iteratively:
execute, by the processor, the multi-level search in parallel, using the fixed one or more node flows; and
increase, by the processor, an iteration number;
until either:
an objective value is less than a threshold; or
the total number of iterations is reached; or
a time limit is reached;
and
select, by the processor, a third optimal solution.

11. He computing apparatus of claim 10 , wherein:
the first Boolean parameter specifies whether to fix supply quantities in an output solution, or fix the supply quantities in a warm start; and
the second Boolean parameter specifies whether to use an optimal solution of a linear relaxation as an initial warm start.

12. He computing apparatus of claim 10 , wherein when addressing the one or more cycles, the apparatus is further configured to:
apply, by the processor, a cycle-breaking transformation to the production network model.

13. He computing apparatus of claim 10 , where the subset of production nodes is a percentage of iterations completed multiplied by a total number of nodes in the production network model.

14. He computing apparatus of claim 10 , wherein the total number of iterations is equal to either:
a number of iterations to perform provided in the limit parameter; or the time limit divided by a time taken to perform the first iteration.

15. The computing apparatus of claim 10 , wherein after the first iteration, when fixing the one or more node flows, the apparatus is further configured to:
re-evaluate, by the processor, a linear relaxation using the one or more node flows that are fixed to a respective value in a most recent optimal solution.

16. The computing apparatus of claim 10 , wherein after the first iteration, when fixing the one or more node flows, the apparatus is further configured to:
create, by the processor, a new production network model;
eliminate, by the processor, fixed nodes that have a flow of zero; and
add, by the processor, one or more supply nodes to replace nodes that are fixed to a positive flow.

17. He computing apparatus of claim 10 , wherein parametrization of the multi-level search comprises at least one of: a warm start solution, a demand sequence, and a pass count.

18. The computing apparatus of claim 10 , wherein the apparatus is further configured 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; and
generate, by the pr

Assignees

• Kinaxis Inc

Inventors

• Henshall Dane

Classifications

• G06F17/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)} · CPC title

• G06Q10/087 Primary

  Inventory or stock management, e.g. order filling, procurement or balancing against orders · CPC title