# US 12,008,678 B2 · Discrete optimisation

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

- Number: US 12,008,678 B2
- Document ID: US12008678B2
- Status: Granted
- Kind: B2
- Application number: 17/785,836
- Filed: 2020-12-15
- Published: 2023-03-02
- Granted: 2024-06-11
- Earliest claimed: 2019-12-18
- Assignees: Kalibrate Technologies Limited
- Applicants: Kalibrate Technologies Limited
- Inventors: Benjamin Pickering; Gareth Owen; David Leedal; Mark Pearce; Rebecca Wilson
- Web page: https://patentgrep.com/patent/US12008678B2

## CPC

- 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)}
- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06T 1/60: Memory management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

There is provided a method of discrete optimisation comprising: receiving an optimisation objective function; performing a continuous optimisation based upon the optimisation objective function to generate an initial continuous value; generating a plurality of candidate discrete values based upon the initial continuous value; evaluating the plurality of candidate discrete values based upon the optimisation objective function, wherein the evaluation of the plurality of candidate discrete values is carried out in parallel; and outputting a candidate discrete value based upon the evaluation.

## Claims

### Claim 1

A computer-implemented method of discrete optimisation comprising:
receiving an optimisation objective function;
performing a continuous optimisation based upon the optimisation objective function to generate an initial continuous value;
generating a plurality of candidate discrete values based upon the initial continuous value and limiting a size of a search space by centering the plurality of candidate discrete values on the initial continuous value;
evaluating the plurality of candidate discrete values based upon the optimisation objective function, wherein the evaluation of the plurality of candidate discrete values is carried out in parallel; and
outputting a candidate discrete value based upon the evaluation.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
determining that at least one of the plurality of candidate discrete values has an optimisation objective function value that is an improvement on the optimisation objective function value of the initial continuous value;
repeatedly performing the steps of generating and evaluating a plurality of candidate discrete values until it is determined that none of the plurality of candidate discrete values for a current iteration has an optimisation objective function value that is an improvement on a best optimisation objective function value of the previous iteration.

### Claim 3 (depends on 1)

The method of claim 1, wherein the initial continuous value is an n-dimensional vector and the plurality of candidate discrete values are generated based upon the discrete values that lie within an n-dimensional hypercube centred on the initial continuous value.

### Claim 4 (depends on 3)

The method of claim 3, wherein the n-dimensional hypercube is arranged into a plurality of layers and the plurality of candidate discrete values are generated based upon the discrete values lying within one or more layers.

### Claim 5 (depends on 4)

The method of claim 4, wherein the plurality of candidate discrete values are generated based upon an index value of a respective layer.

### Claim 6 (depends on 5)

The method of claim 5, wherein the plurality of candidate discrete values comprises the discrete values in a layer that fulfil the following condition:
max(┌|k1−p1|┐,┌|k2−p2|┐, . . . ,┌|kn−pn|┐)=i
where i is the ith layer of the hypercube, p=(p1, p2, . . . , pn) is the initial continuous value as an n-dimensional vector, k∈0n is the set of all possible n-dimensional discrete values, ┌⋅┐ is the ceiling function, and |⋅| is the absolute value.

### Claim 7 (depends on 1)

The method of claim 1, wherein outputting a candidate discrete value based upon the evaluation comprises outputting the candidate discrete value having the best optimisation objective function value.

### Claim 8 (depends on 1)

The method of claim 1, wherein evaluating the plurality of candidate discrete values is carried out using a graphics processing unit or distributed computing system.

### Claim 9 (depends on 1)

A system comprising:
a plurality of processing units, wherein each processing unit is coupled to a memory; and
wherein the plurality of processing units are configured to carry out a method according to claim 1.

### Claim 10 (depends on 9)

The system of claim 9, wherein the plurality of processing units comprise a plurality of processing units of a GPU.

### Claim 11 (depends on 1)

A non-transitory computer readable storage medium comprising stored instructions that when executed by a plurality of processing units causes the plurality of processing units to carry out a method according to claim 1.