API Reference

URL

https://optigan.fixstars.com

Authentication

Add Authorization to the request header and set the Bearer scheme and token to the value.

Authorization: Bearer <TOKEN>

Request Parameters

End point : /solve

Method : POST

key

sub key

type

req.

min

max

default

description

polynomial

array

1

QUBO polynomial (Two-dimensional array with [integer, integer, number] as an array element)

matrix

array

1

QUBO matrix (Two-dimensional array with [double, double, …] as an array element)

constraints

array

1

Array of constraint object

constant

number

0

Constant term

num_unit_steps

integer

1

100

10

Number of unit steps for annealing

timeout

integer

0

600000 2

10000

Timeout period (milliseconds)

penalty_calibration

boolean

true

Whether to automatically calibrate the coefficients of the penalty functions of constraint objects

outputs

object

Output control parameters

spins

boolean

true

Whether to output spin array

energies

boolean

true

Whether to output energy value

feasibilities

boolean

true

Whether to output feasibility of solutions

sort

boolean

true

Whether to sort spin array and energy in ascending order by energy value

duplicate

boolean

false

Whether to output solutions with the same energy values

num_outputs

integer

1

Number of outputs of spin arrays and energy values (0: output all)

1(1,2,3)

At least, either one of polynomial, matrix, and constraints is required for input. constraints can be combined with either polynomial or matrix.

2

Depends on the contract plan

polynomial

The QUBO polynomial is defined by the two-dimensional array consisting of the tuples of variable indices and corresponding coefficients.

\[H \left( \mathbf{x} \right) = \sum_{i < j}{Q_{i,j} x_i x_j} + \sum_{i}{Q_{i,i} x_i} + c\]

For the above QUBO polynomial, give the coefficient \(Q_ {i, j}\) and the constant \(c\) as elements of the two-dimensional array as follows.

  • Quadratic term \(Q_{i,j}\) → Array \(\left[i, j, Q_{i,j} \right]\) (\(i \ge 0, j\ge 0\))

    Example: For the quadratic term \(x_1x_2\) with the coefficient \(Q_{1,2}=-4.0\), the corresponding element of the two-dimensional polynomial array is specified by the 3-element array [1, 2, -4.0].

  • Linear term \(Q_{i,j}\) → Array \(\left[i, i, Q_{i,i} \right]\) or \(\left[i, Q_{i,i} \right]\) (\(i \ge 0\))

    Example: For the linear term \(x_0\) with the coefficient \(Q_{0,0}=1.0\), the corresponding element of the two-dimensional polynomial array is specified by the 3-element array [0, 0, 1.0] or 2-element array [0, 1.0].

  • Constant term \(c\) → Array \(\left[c \right]\) or Numerical value \(c\)

    Example: For the constant term \(c=0.5\), the corresponding element of the two-dimensional polynomial array is specified by the single element array [0.5] or the number 0.5.

Note

polynomial and matrix cannot be specified simultaneously.

Note

If the QUBO polynomial is fully connected, it can work faster with matrix as the input.

matrix

The QUBO polynomial can be represented in the form of a row major matrix. The values are in two-dimensional array format.

The following QUBO polynomial expressed in terms of a matrix \(\mathbf{Q}\) and an array of variables \(\mathbf{x}\)

\[H \left( \mathbf{x} \right) = \mathbf{x}^{ \mathrm{ T } } \mathbf{Q} \mathbf{x}\]

is represented by one of the following three methods.

Note

polynomial and matrix cannot be specified simultaneously.

Note

If the QUBO polynomial has more than 1024 bits and is sparse, polynomial input can operate faster.

Square Matrix

Expressing the matrix element by \(Q_{i,j}\), each row of the two-dimensional matrix is given by \(\left[Q_{i,0}, Q_{i,1}, Q_{i,2}, \cdots \right]\).

The input QUBO matrix is interpreted as a polynomial as follows:

\[H \left( \mathbf{x} \right) = \sum_{i < j}{\left(Q_{i,j} + Q_{j,i} \right) x_i x_j} + \sum_{i}{Q_{i,i} x_i}\]

The sum of the off-diagonal elements of the QUBO matrix \(Q_{ij} + Q_{ji}\) corresponds to the coefficient of \(x_i x_j \left(i \ne j \right)\) term.

The number of rows in the two-dimensional array and the length of each row must coincide (the condition for a square matrix).

Upper Triangular Matrix

Expressing the matrix element by \(Q_{i,j}\), each row of the two-dimensional matrix is given by \(\left[Q_{i,i}, Q_{i,i+1}, Q_{i,i+2}, \cdots, \right]\).

The input QUBO matrix is interpreted as a polynomial as follows:

\[H \left( \mathbf{x} \right) = \sum_{i < j}{Q_{i,j} x_i x_j} + \sum_{i}{Q_{i,i} x_i}\]

The length of each row in the two-dimensional array must match the number of columns minus the row index. In other words, for the QUBO polynomial with \(N\) variables, the length of the array in \(i\)-th row is \(N-i\).

Lower Triangular Matrix

Expressing the matrix element by \(Q_{i,j}\), each row of the two-dimensional matrix is given by \(\left[Q_{i,0}, Q_{i,1}, Q_{i,2}, \cdots, Q_{i,i} \right]\).

The input QUBO matrix is interpreted as a polynomial as follows:

\[H \left( \mathbf{x} \right) = \sum_{i > j}{Q_{i,j} x_i x_j} + \sum_{i}{Q_{i,i} x_i}\]

The length of each row in the two-dimensional array must match the row index. In other words, for the QUBO polynomial with \(N\) variables, the length of the array in \(i\)-th row is \(i\).

constraints

The object representing the constraint conditions imposed on the variables of QUBO polynomials is given by the form of an array.

Note

It can be combined with polynomial or matrix.

The constraint condition object is defied as follows.

key

sub key

type

req.

default

description

penalty

array

penalty function (quadratic polynomial) 3

multiplier

number

1

coefficients of penalty functions

condition

object

constraint equation

left

array

penalty

left hand side of a (quadratic) constraint equation 3

op

string

=

operator relating the left and right hand sides of a constraint equation

right

number

0

right hand side of a constraint condition (numerical value)

3(1,2)

It should be in the same form as polynomial in the request parameter.

penalty is a penalty function corresponding to a constraint equation, and it is expressed in terms of a quadratic polynomial. The coefficient of a penalty function can be specified by multiplier. As parts of the optimization problem, the equations obtained by penalty functions multiplied by specified coefficients will be added to polynomial or matrix. If the auto-calibrating function for the coefficient is enabled, multiplier is treated as the initial value of the coefficient.

The equation to be satisfied by a constraint condition is represented by a condition object. If penalty is set without specifying any condition object, it is interpreted as penalty=0 by default. The left hand side of a constraint equation (quadratic polynomial) is specified by left, and its right hand side (numerical value) is specified by right. If right is omitted, the right hand side of the equation is set to \(0\) as default.

The operator relating the left and right hand sides of a constraint equation is specified by op in terms of a string. If op is omitted, it is interpreted as =, in other words, left = right. The list of strings available for the operator are the followings.

  • equality left = right

    • op: =, ==, eq, EQ

  • inequality left < right

    • op: <, lt, LT

  • inequality left <= right

    • op: <=, le, LE

  • inequality left > right

    • op: >, gt, GT

  • inequality left >= right

    • op: >=, ge, GE

constant

It specifies the constant term of a QUBO polynomial as a real number. If omitted \(0\) is set.

num_unit_steps

It specifies a variable that represents the smoothness of the annealing schedule (Monte Carlo step) as an integer greater than or equal to \(1\). If omitted, it will be set automatically. Increasing the value stabilizes the quality of solutions, but increasing it more than necessary tends to slow down the convergence of solutions.

timeout

It gives the annealing time. If omitted, it is set to \(10000\) (10 seconds). Since the adopted algorithm needs to generate at least one solution, it is not guaranteed that the calculation is finished after finding more than one solution within the specified time.

penalty_calibration

It specifies whether to enable the auto-calibration function for the penalty functions in constraint conditions. If omitted, it is enabled (set to true).

outputs

It specifies which outputs to be included in the response.

spins

It specifies whether to output the spin array in the annealing result.

energies

It specifies whether to output the energy values in the annealing result.

feasibilities

It specifies whether to output the array indicating the feasibilities of the solutions in the annealing result.

sort

The results of annealing (spin array, energies, feasibilities) can be sorted in terms of the number of satisfied constraint conditions and the values of energies. true is for ascending order, false is for descending order. In the case of ascending order, the priority of sorting is the followings:

  • in ascending order with the largest number of satisfied constraint conditions first

  • in ascending order with the smallest value of energy first if the number of satisfied constraint conditions are the same

duplicate

If solutions have the same energy values and feasibility but different variable combinations, they are output as different solutions.

num_outputs

It specifies the number of results to be output.

The solution is recorded when the energy value or the number of satisfied constraint conditions is updated. After all, it is sorted in the order specified by sort, and it outputs the number of results at most specified by num_outputs from the beginning to the results.

When duplicate = true, if a solution with the combinations of variables which has not been found to the point, even if the solutions with the same energy value or the same number of satisfied constraint conditions had been found, it will be output. Therefore, please note that the number of solutions actually output may not match num_outputs. num_outputs corresponds to the number of unique energy values.

Normal Execution Time Response

key

sub key

type

description

execution_time

object

Execution time(ms)

annealing_time

number

Annealing execution time

queue_time

number

Queue wait time

cpu_time

number

CPU processing time

time_stamps

array

Time when the solutions were obtained

energies

array

Energy value

spins

array

Spin array

feasibilities

array

Boolean array for showing feasibility

execution_parameters

object

num_unit_steps

integer

Number of execution annealing steps

execution_time

It returns the information about the execution time of the annealing calculations. The unit is given by milliseconds (ms).

annealing_time

It returns the annealing execution time.

time_stamps

It returns an array containing the time at which each solution was obtained, with the annealing start time as 0. Regardless of outputs.sort or num_outputs, all the times when the energy values were updated (including the same values if duplicate = true) will be output.

queue_time

It returns the waiting time of the queue.

cpu_time

It returns the total CPU processing time, including annealing pre-processing and post-processing, and memory transfer to GPU.

energies

It returns an array containing the energy values (number) of the annealing result. It should be noted that the values of penalty functions are not included.

spins

It returns an array containing the spin array (array: with 0 or 1 values (integer) as elements) of the annealing result.

feasibilities

It returns an array with boolean values, indicating whether each solution of the annealing result is feasible (all constraint conditions are satisfied).

execution_parameters

It returns information about parameters for annealing execution.

num_unit_steps

It returns the number of unit steps for annealing at runtime.

timeout

It returns the annealing execution time. The unit is given by milliseconds (ms).

num_iterations

It returns the number of iterations of the searching algorithm until the timeout. The returned value is always greater than 1. If the number of iterations is not enough, the timeout value may not be set large enough for the size of a given problem.

penalty_calibration

It returns a boolean value indicating whether or not the auto-calibration function for the coefficients of penalty functions in constraint condition objects is enabled. It is true if it matches with the following conditions:

  • Request parameter penalty_calibration = true

  • constraints parameter is given

  • Values other than 0 is given in polynomial or matrix

penalty_multipliers

It returns the coefficients of the penalty functions of the constraint objects, used for searching solutions, in the array form. If the auto-calibration of the coefficients of penalty functions is possible, the calibrated values will be stored.

Response on Error

key

sub key

type

description

error

string

Error message

error

It returns an error message.

Example

Here, the example of the request for \(H = - q_0 q_1\) in polynomial form is shown. The timeout is 50ms.

$ curl -H 'Authorization: Bearer XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' -H 'Content-Type: application/json; charset=UTF-8' -H 'X-Accept: application/json' -X POST -d '{"timeout": 50, "polynomial": [[0, 1, -1.0]]}' https://optigan.fixstars.com/solve
{"execution_parameters":{"num_unit_steps":10,"timeout":50.0,"num_iterations":1,"penalty_calibration":false,"penalty_multipliers":[]},"execution_time":{"annealing_time":33.24964799999999,"queue_time":0.494037000000022,"cpu_time":150.34307499999995,"time_stamps":[32.959393]},"feasibilities":[true],"energies":[-1.0],"spins":[[1,1]]}

Please add the Content-Encoding header if you want to compress the request data. The valid compression formats are gzip or deflate.

$ echo '{"timeout": 50, "polynomial": [[0, 1, -1.0]]}' | gzip | \
  curl -H 'Authorization: Bearer XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' -H "Content-Encoding: gzip" -H 'X-Accept: application/json' https://optigan.fixstars.com/solve -s -X POST --data-binary @-
  {"execution_parameters":{"num_unit_steps":10,"timeout":50.0,"num_iterations":1,"penalty_calibration":false,"penalty_multipliers":[]},"execution_time":{"annealing_time":33.764886999999998,"queue_time":0.4529419999999839,"cpu_time":150.00948299999997,"time_stamps":[33.429204]},"feasibilities":[true],"energies":[-1.0],"spins":[[1,1]]}

If the response data needs to be compressed, the Accept-Encoding header has to be added. The gzip or deflate compression formats are recommended.

$ echo '{"timeout": 50, "polynomial": [[0, 1, -1.0]]}' | gzip | \
  curl -H 'Authorization: Bearer XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' -H 'Content-Encoding: gzip' -H 'Accept-Encoding: gzip' -H 'X-Accept: application/json' https://optigan.fixstars.com/solve -s -X POST --data-binary @- | zcat
  {"execution_parameters":{"num_unit_steps":10,"timeout":50.0,"num_iterations":1,"penalty_calibration":false,"penalty_multipliers":[]},"execution_time":{"annealing_time":33.763845999999997,"queue_time":0.5169769999999939,"cpu_time":149.07931299999999,"time_stamps":[33.443633]},"feasibilities":[true],"energies":[-1.0],"spins":[[1,1]]}