# US 6,731,998 B2 · Collaboratively solving an optimization problem using first and second optimization software each having at least partial information concerning the optimization problem

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

- Number: US 6,731,998 B2
- Document ID: US6731998B2
- Status: Granted
- Kind: B2
- Application number: 10/393,793
- Filed: 2003-03-20
- Published: 2003-09-04
- Granted: 2004-05-04
- Earliest claimed: 2000-03-07
- Assignees: i2 Technologies US, Inc.
- Inventors: Joachim Paul Walser; David E. Joslin; Craig W. Schmidt
- Web page: https://patentgrep.com/patent/US6731998B2

## CPC

- G06F 9/4887: {involving deadlines, e.g. rate based, periodic}
- 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: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- 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

## Abstract

In one embodiment, a method is provided for collaboratively solving an optimization problem using at least first optimization software and second optimization software each having at least partial information concerning the optimization problem. The method includes: (1) determining a solution to a first sub-problem of the optimization problem using the first optimization software based on the at least partial information concerning the optimization problem known to the first optimization software; (2) communicating from the first optimization software to the second optimization software the solution to the first sub-problem and information concerning one or more penalties for deviating from the solution to the first sub-problem; and (3) determining a solution to a second sub-problem using the second optimization software based on the at least partial information concerning the optimization problem known to the second optimization software, the communicated solution to the first sub-problem, and the communicated information concerning one or more penalties for deviating from the solution to the first sub-problem.

## Claims

### Claim 1

A method for collaboratively solving an optimization problem using at least first optimization software and second optimization software each having at least partial information concerning the optimization problem, comprising:
determining a solution to a first sub-problem of the optimization problem using the first optimization software based on the at least partial information concerning the optimization problem known to the first optimization software;
communicating from the first optimization software to the second optimization software the solution to the first sub-problem and information concerning one or more penalties for deviating from the solution to the first sub-problem; and
determining a solution to a second sub-problem of the optimization problem using the second optimization software based on the at least partial information concerning the optimization problem known to the second optimization software, the communicated solution to the first sub-problem, and the communicated information concerning one or more penalties for deviating from the solution to the first sub-problem.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
communicating from the second optimization software to third optimization software the solution to the second sub-problem and information concerning one or more penalties for deviating from the solution to the second sub-problem; and
determining a solution to a third sub-problem of the optimization problem using the third optimization software based on at least partial information concerning the optimization problem known to the third optimization software, the communicated solution to the second sub-problem, and the communicated information concerning one or more penalties for deviating from the solution to the second sub-problem.

### Claim 3 (depends on 2)

The method of claim 2, wherein:
the first and third optimization software are different optimization software; and
the first and third sub-problems are different sub-problems.

### Claim 4 (depends on 2)

The method of claim 2, wherein:
the first and third optimization software are the same optimization software;
the first and third sub-problems are the same sub-problem; and
solutions to sub-problems of the optimization problem are determined repeatedly in an iterative manner using the first, second, and third optimization software until a sufficiently optimal solution to the optimization problem is obtained.

### Claim 5 (depends on 2)

The method of claim 2, further comprising:
determining solutions to one or more successive sub-problems of the optimization problem using one or more successive optimization software until last optimization software has determined a solution to a last sub-problem;
communicating from the last optimization software to the first optimization software the solution to the last sub-problem and information concerning one or more penalties for deviating from the solution to the last sub-problem; and
repeating the preceding steps in an iterative manner until a sufficiently optimal solution to the optimization problem is obtained.

### Claim 6 (depends on 1)

The method of claim 1, wherein:
the first optimization software comprises batch aggregation software operable to aggregate product batches according to one or more aggregation criteria; and
the second optimization software comprises scheduling software operable to schedule the aggregated product batches according to one or more scheduling criteria.

### Claim 7 (depends on 1)

The method of claim 1, wherein:
the first optimization software comprises batch aggregation software operable to allocate one or more product demands to one or more product batches having suggested sizes and suggested starting times, the solution to the first-sub problem comprising suggested sizes and suggested starting times;
the second optimization software comprises scheduling software operable to schedule starting times for one or more of the product batches, the solution to the second-sub problem comprising the starting times for the one or more product batches; and
the one or more penalties comprise penalties for deviating from at least one of the suggested sizes or at least one of the suggested starting times.

### Claim 8

A system for collaboratively solving an optimization problem, comprising:
first optimization software operable to:
determine a solution to a first sub-problem of the optimization problem based on at least partial information concerning the optimization problem known to the first optimization software; and
communicate the solution to the first sub-problem and information concerning one or more penalties for deviating from the solution to the first sub-problem; and
second optimization software operable to:
determine a solution to a second sub-problem of the optimization problem based on at least partial information concerning the optimization problem known to the second optimization software, the communicated solution to the first sub-problem, and the communicated information concerning one or more penalties for deviating from the solution to the first sub-problem.

### Claim 9 (depends on 8)

The system of claim 8, wherein:
the second optimization software is further operable to communicate the solution to the second sub-problem and information concerning one or more penalties for deviating from the solution to the second sub-problem; and
the system further comprises third optimization software operable to determine a solution to a third sub-problem of the optimization problem based on at least partial information concerning the optimization problem known to the third optimization software, the communicated solution to the second sub-problem, and the communicated information concerning one or more penalties for deviating from the solution to the second sub-problem.

### Claim 10 (depends on 9)

The system of claim 9, wherein:
the first and third optimization software are different optimization software; and
the first and third sub-problems are different sub-problems.

### Claim 11 (depends on 9)

The system of claim 9, wherein:
the first and third optimization software are the same optimization software;
the first and third sub-problems are the same sub-problem; and
solutions to sub-problems of the optimization problem are determined repeatedly in an iterative manner using the first, second, and third optimization software until a sufficiently optimal solution to the optimization problem is obtained.

### Claim 12 (depends on 9)

The system of claim 9, further comprising one or more successive optimization software including at least last optimization software wherein:
solutions are determined to one or more successive sub-problems of the optimization problem using the one or more successive optimization software until the last optimization software has determined a solution to a last sub-problem;
the solution to the last sub-problem and information concerning one or more penalties for deviating from the solution to the last sub-problem are communicated from the last optimization software to the first optimization software; and
the preceding operations are repeated in an iterative manner until a sufficiently optimal solution to the optimization problem is obtained.

### Claim 13 (depends on 8)

The system of claim 8, wherein:
the first optimization software comprises batch aggregation software that aggregates product batches according to one or more aggregation criteria; and
the second optimization software comprises scheduling software that schedules the aggregated product batches according to one or more scheduling criteria.

### Claim 14 (depends on 8)

The system of claim 8, wherein:
the first optimization software comprises batch aggregation software that allocates one or more product demands to one or more product batches having suggested sizes and suggested starting times, the solution to the first-sub problem comprising suggested sizes and suggested starting times;
the second optimization software comprises scheduling software that schedules starting times for one or more of the product batches, the solution to the second-sub problem comprising the starting times for the one or more product batches; and
the one or more penalties comprise penalties for deviating from at least one of the suggested sizes or at least one of the suggested starting times.

### Claim 15

Software for collaboratively solving an optimization problem, the software comprising at least first optimization software and second optimization software each having at least partial information concerning the optimization problem, the software embodied in computer-readable media and when executed operable to:
determine a solution to a first sub-problem of the optimization problem using the first optimization software based on at least partial information concerning the optimization problem known to the first optimization software;
communicate from the first optimization software to the second optimization software the solution to the first sub-problem and information concerning one or more penalties for deviating from the solution to the first sub-problem; and
determine a solution to a second sub-problem of the optimization problem using the second optimization software based on at least partial information concerning the optimization problem known to the second optimization software, the communicated solution to the first sub-problem, and the communicated information concerning one or more penalties for deviating from the solution to the first sub-problem.

### Claim 16 (depends on 15)

The software of claim 15, further operable to:
communicate from the second optimization software to third optimization software the solution to the second sub-problem and information concerning one or more penalties for deviating from the solution to the second sub-problem; and
determine a solution to a third sub-problem of the optimization problem using the third optimization software based on at least partial information concerning the optimization problem known to the third optimization software, the communicated solution to the second sub-problem, and the communicated information concerning one or more penalties for deviating from the solution to the second sub-problem.

### Claim 17 (depends on 16)

The software of claim 16, wherein:
the first and third optimization software are different optimization software; and
the first and third sub-problems are different sub-problems.

### Claim 18 (depends on 16)

The software of claim 16, wherein:
the first and third optimization software are the same optimization software;
the first and third sub-problems are the same sub-problem; and
solutions to sub-problems of the optimization problem are determined repeatedly in an iterative manner using the first, second, and third optimization software until a sufficiently optimal solution to the optimization problem is obtained.

### Claim 19 (depends on 16)

The software of claim 16, further comprising one or more successive optimization software including at least last optimization software and operable to:
determine solutions to one or more successive sub-problems of the optimization problem using the one or more successive optimization software until the last optimization software has determined a solution to a last sub-problem;
communicate from the last optimization software to the first optimization software the solution to the last sub-problem and information concerning one or more penalties for deviating from the solution to the last sub-problem; and
repeat the preceding steps in an iterative manner until a sufficiently optimal solution to the optimization problem is obtained.

### Claim 20 (depends on 15)

The software of claim 15, wherein:
the first optimization software comprises batch aggregation software operable to aggregate product batches according to one or more aggregation criteria; and
the second optimization software comprises scheduling software operable to schedule the aggregated product batches according to one or more scheduling criteria.

### Claim 21 (depends on 15)

The software of claim 15, wherein:
the first optimization software comprises batch aggregation software operable to allocate one or more product demands to one or more product batches having suggested sizes and suggested starting times, the solution to the first-sub problem comprising suggested sizes and suggested starting times;
the second optimization software comprises scheduling software operable to schedule starting times for one or more of the product batches, the solution to the second-sub problem comprising the starting times for the one or more product batches; and
the one or more penalties comprise penalties for deviating from at least one of the suggested sizes or at least one of the suggested starting times.
