# US 12,602,627 B2 · Solving supply networks with discrete decisions

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

- Number: US 12,602,627 B2
- Document ID: US12602627B2
- Status: Granted
- Kind: B2
- Application number: 18/105,281
- Filed: 2023-02-03
- Published: 2024-08-08
- Granted: 2026-04-14
- Earliest claimed: 2023-02-03
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Jakob Witzig; Anna Walter; Christoph Eckert; Dimitri Kniasew; Maximilian Pfister; Carsten Schumm; Claudia Volke
- Web page: https://patentgrep.com/patent/US12602627B2

## CPC

- 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)
- G06F 8/34: Graphical or visual programming
- G06F 9/44521: {Dynamic linking or loading; Link editing at or after load time, e.g. Java class loading}
- G06Q 10/063: Operations research, analysis or management
- G06Q 10/087: Inventory or stock management, e.g. order filling, procurement or balancing against orders
- G06Q 10/0872: {using inventory planning}
- 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

The example embodiments are directed to methods and systems for generating a model of an optimum flow of materials within a supply network based on a relax mixed integer programming model. For example, the method may include generating, via a software application, a model of the supply network based on the data stored in the storage device, executing a MIP optimizer on the model to generate a configuration of a flow of materials within the supply network, wherein the MIP optimizer is instructed to relax discrete constraints within the supply network when generating the configuration, generating a graphical user interface that includes a plurality of graphical objects corresponding to a plurality of locations included in the configuration and directional edges between the plurality of graphical objects corresponding to the flow of the materials between the plurality of locations, and displaying the graphical user interface.

## Claims

### Claim 1

A computing system comprising:
a storage device configured to store data of a supply network; and
a processor configured to:
install a dynamic link library within a software application;
call the dynamic link library at runtime of the software application to execute a mixed-integer programming (MIP) model of the supply network with discrete constraints based on the data stored in the storage device;
execute a mixed integer programming (MIP) optimizer from within the installed dynamic link library on the MIP model to generate a flow configuration within the supply network, by instructing the MIP optimizer to convert the discrete constraints within the supply network into linear constraints prior to generating the flow configuration, wherein the discrete constraints are converted to the linear constraints by removing specific discrete constraints corresponding to times necessary to find respective optimal solutions, locations within the supply network, and operations within the MIP model;
segment the supply network into a plurality of sequences of the flow configuration, each of the plurality of sequences being segmented individually by the MIP optimizer and corresponding to a particular location of the locations within the supply network;
identify, at a beginning of the supply network, a first removed discrete constraint as having a highest priority by having most dependent operations in the flow configuration of the supply network as compared to other discrete constraints on the supply network that have less dependent operations than the highest priority identified first removed discrete constraint;
incrementally remove the other discrete constraints on the supply network by relaxing binary variable values within the MIP model that correspond to the other discrete constraints, wherein the relaxed binary variable values become a linear requirement of greater than zero, resulting in shrinking the supply network and increasing flexibility for the MIP optimizer to find particular ones of the respective optimal solutions of the supply network in less time than the times necessary to find the respective optimal solutions;
re-introduce a subset of the particular ones of the discrete constraints into the MIP model with relaxed binary variable requirements, the re-introduction starting, at each iteration, with the identified first removed discrete constraint having the highest priority at the beginning of the supply network being re-introduced before incremental re-introduction of the less dependent operations, the incremental re-introduction proceeding forward from the beginning of the supply network until end of the supply network;
re-execute the MIP optimizer with the re-introduced subset of the particular ones of the discrete constraints to generate an updated flow configuration;
output, by the MIP optimizer in a case the MIP optimizer cannot reach a complete solution by a stop condition defined by a timeout limit, results of how far the MIP optimizer has reached in finding the optimal solution;
generate a graphical user interface that includes a plurality of graphical objects corresponding to a plurality of the locations included in the updated flow configuration and directional edges between the plurality of graphical objects corresponding to the updated flow configuration; and
display the graphical user interface of the updated flow configuration within a page of the software application.

### Claim 2 (depends on 1)

The computing system of claim 1, wherein the processor is further configured to identify an operation from among the operations within the supply network to impose a restriction based on an order of the operation with respect to other operations.

### Claim 3 (depends on 2)

The computing system of claim 2, wherein the processor is further configured to execute the MIP optimizer again on the MIP model to generate a second flow configuration within the supply network, wherein the processor instructs the MIP optimizer to enforce the restriction on the identified operation and permit linear constraints on the other operations when determining the second flow configuration.

### Claim 4 (depends on 3)

The computing system of claim 3, wherein the processor is further configured to select an optimum configuration from among the flow configuration and the second flow configuration based on a comparison of properties of the flow configuration to the second flow configuration, and display the graphical user interface of the selected optimum configuration via the graphical user interface.

### Claim 5 (depends on 1)

The computing system of claim 1, wherein the processor is configured to call the MIP optimizer via a predefined command that is issued via the software application to the installed dynamic link library.

### Claim 6 (depends on 1)

The computing system of claim 1, wherein the processor is configured to iteratively execute the MIP optimizer to iteratively select optimal sub-sequences of the flow configuration within the supply network until all sub-sequences of the flow configuration are generated or an optimal solution cannot be found for a sub-sequence by the optimizer.

### Claim 7 (depends on 6)

The computing system of claim 6, wherein the processor is further configured to shrink the supply network during an iteration of the MIP optimizer, and execute the MIP optimizer on the shrunken supply network during a next iteration of the MIP optimizer.

### Claim 8

A method comprising:
installing a dynamic library within a software application;
calling the dynamic link library at runtime of the software application to execute a mixed-integer programming (MIP) model of a supply network with discrete constraints based on data stored in a storage device;
executing a mixed integer programming (MIP) optimizer from within the installed dynamic link library on the model to generate a flow configuration within the supply network, by instructing the MIP optimizer to convert the discrete constraints within the supply network into linear constraints prior to generating the configuration, wherein the discrete constraints are converted to the linear constraints by removing specific discrete constraints corresponding to times necessary to find respective optimal solutions, locations within the supply network, and operations within the MIP model;
segmenting the supply network into a plurality of sequences of the flow configuration, each of the plurality of sequences being segmented individually by the MIP optimizer and corresponding to a particular location of the locations within the supply network;
identifying, at a beginning of the supply network, a first removed discrete constraint as having a highest priority by having most dependent operations in the flow configuration of the supply network as compared to other discrete constraints on the supply network that have less dependent operations than the highest priority identified first removed discrete constraint;
incrementally removing the other discrete constraints on the supply network by relaxing binary variable values within the MIP model that correspond to the other discrete constraints, wherein the relaxed binary variable values become a linear requirement of greater than zero, resulting in shrinking the supply network and increasing flexibility for the MIP optimizer to find particular ones of the respective optimal solutions of the supply network in less time than the times necessary to find the respective optimal solutions;
re-introducing a subset of the particular ones of the discrete constraints into the MIP model with relaxed binary variable requirements, the re-introduction starting, at each iteration, with the identified first removed discrete constraint having the highest priority at the beginning of the supply network being re-introduced before incremental re-introduction of the less dependent operations, the incremental re-introduction proceeding forward from the beginning of the supply network until end of the supply network;
re-executing the MIP optimizer with the re-introduced subset of the particular ones of the discrete constraints to generate an updated flow configuration;
outputting, by the MIP optimizer in a case the MIP optimizer cannot reach a complete solution by a stop condition defined by a timeout limit, results of how far the MIP optimizer has reached in finding the optimal solution;
generating a graphical user interface that includes a plurality of graphical objects corresponding to a plurality of the locations included in the updated flow configuration and directional edges between the plurality of graphical objects corresponding to the updated flow configuration; and
displaying the graphical user interface of the updated flow configuration within a page of the software application.

### Claim 9 (depends on 8)

The method of claim 8, wherein the method further comprises identifying an operation from among the operations within the supply network to impose a restriction based on an order of the operation with respect to other operations.

### Claim 10 (depends on 9)

The method of claim 9, wherein the method further comprises executing the MIP optimizer again on the MIP model to generate a second flow configuration within the supply network, wherein the executing again comprises instructing the MIP optimizer to enforce the restriction on the identified operation and permitting linear constraints on the other operations when determining the second flow configuration.

### Claim 11 (depends on 10)

The method of claim 10, wherein the method further comprises selecting an optimum configuration from among the flow configuration and the second flow configuration based on a comparison of properties of the flow configuration to the second flow configuration, and displaying the graphical user interface of the selected optimum configuration via the graphical user interface.

### Claim 12 (depends on 8)

The method of claim 8, wherein the executing comprises calling the MIP optimizer via a predefined command that is issued via the software application to the installed dynamic link library.

### Claim 13 (depends on 8)

The method of claim 8, wherein the executing comprises iteratively executing the MIP optimizer to iteratively select optimal sub-sequences of the flow configuration within the supply network until all sub-sequences of the configuration flow are generated or an optimal solution cannot be found for a sub-sequence by the optimizer.

### Claim 14 (depends on 13)

The method of claim 13, wherein the executing further comprises shrinking the supply network during an iteration of the MIP optimizer, and executing the MIP optimizer on the shrunken supply network during a next iteration of the MIP optimizer.

### Claim 15

A computer-readable medium comprising instructions which when executed by a processor cause a computer to perform a method comprising:
installing a dynamic library within a software application;
calling the dynamic link library at runtime of the software application to execute a mixed-integer programming (MIP) model of a supply network with discrete constraints based on data stored in a storage device;
executing a mixed integer programming (MIP) optimizer from within the installed dynamic link library on the model to generate a flow configuration within the supply network, by instructing the MIP optimizer to convert the discrete constraints within the supply network into linear constraints prior to generating the configuration, wherein the discrete constraints are converted to the linear constraints by removing specific discrete constraints corresponding to times necessary to find respective optimal solutions, locations within the supply network, and operations within the MIP model;
segmenting the supply network into a plurality of sequences of the flow configuration, each of the plurality of sequences being segmented individually by the MIP optimizer and corresponding to a particular location of the locations within the supply network;
identifying, at a beginning of the supply network, a first removed discrete constraint as having a highest priority by having most dependent operations in the flow configuration of the supply network as compared to other discrete constraints on the supply network that have less dependent operations than the highest priority identified first removed discrete constraint;
incrementally remove the other discrete constraints on the supply network by relaxing binary variable values within the MIP model that correspond to the other discrete constraints, wherein the relaxed binary variable values become a linear requirement of greater than zero, resulting in shrinking the supply network and increasing flexibility for the MIP optimizer to find particular ones of the respective optimal solutions of the supply network in less time than the times necessary to find the respective optimal solutions;
re-introducing a subset of the particular ones of the discrete constraints into the MIP model with relaxed binary variable requirements, the re-introduction starting, at each iteration, with the identified first removed discrete constraint having the highest priority at the beginning of the supply network being re-introduced before incremental re-introduction of the less dependent operations, the incremental re-introduction proceeding forward from the beginning of the supply network until end of the supply network;
re-executing the MIP optimizer with the re-introduced subset of the particular ones of the discrete constraints to generate an updated flow configuration;
outputting, by the MIP optimizer in a case the MIP optimizer cannot reach a complete solution by a stop condition defined by a timeout limit, results of how far the MIP optimizer has reached in finding the optimal solution;
generating a graphical user interface that includes a plurality of graphical objects corresponding to a plurality of the locations included in the updated flow configuration and directional edges between the plurality of graphical objects corresponding to the updated flow configuration; and
displaying the graphical user interface of the updated flow configuration within a page of the software application.

### Claim 16 (depends on 15)

The computer-readable medium of claim 15, wherein the method further comprises identifying an operation from among the operations within the optimized model to impose a restriction based on an order of the operation with respect to other operations and the optimized model.

### Claim 17 (depends on 16)

The computer-readable medium of claim 16, wherein the method further comprises executing the MIP optimizer again on the MIP model to generate a second flow configuration within the supply network, wherein the executing again comprises instructing the MIP optimizer to enforce the restriction on the identified operation and permitting linear constraints on the other operations when determining the second flow configuration.

### Claim 18 (depends on 17)

The computer-readable medium of claim 17, wherein the executing further comprises shrinking the supply network during an iteration of the MIP optimizer, and executing the MIP optimizer on the shrunken supply network during a next iteration of the MIP optimizer.