Quantagonia QUBO File Format#

Here we describe the syntax of the QUBO file format used to model problems of the form \(x^TQx\) , where \(x\in\{0, 1\}^n\) is the sought solution vector, and \(Q \in \mathbb{R}^{n \times n}\) is a symmetric matrix.

For stored QUBOs, the file ending .qubo is used.

Description#

  • The file should have no header.

  • All in-line separators should be spaces.

  • The first line is a string that sets the optimization sense, which can be MINIMIZE or MAXIMIZE.

  • The second line needs to be a single integer: num_problems. This number specifies the number of the QUBO matrices in the file. Each of these can, in principle, be viewed as a separate optimization problem. When there is more than 1 matrix present in a file, the solver will accumulate all problems by summing them up and reporting the solution for the accumulated problem.

  • The following structure then recurses num_problems times. Each on a new line, we have:

    • one float: penalty.

    • one float: offset: constant offset of the energy

    • two integers: n nnz: n is the dimension of the problem (number of rows and columns of the QUBO matrix); nnz is the number of non-zero entries in the upper triangle matrix

    • for each non-zero entry in the matrix, the following is written in a new line of the file:

      • two integers and a float:i j q_{ij}: i is the row of the entry; j is the column of the entry; q_{ij} is the value at the position i. Because the matrix \(Q\) is symmetric, only the diagonal and upper-triangular entries of the matrix should be specified. The solver will automatically make the matrix symmetric. Formally, this means that \(i \le j\).

    • a number of variable fixings, i.e., variables whose assignment is set ahead of time. The format is f ix val where ix is the variable’s index and val sets the value of the variable to either 0 or 1

File syntax#

MAXIMIZE <--- optimization sense
1 <--- please set to 1 (a deprecated feature which will be removed soon)
# the QUBO matrix
1.0 <--- penalty
2.0 <--- constant energy offset
6 7 <--- first number: dimension, second number: number of entries
0 0 1.0 <-- entries
1 1 1.0
2 2 1.0
3 3 1.0
3 4 1.0
4 4 1.0
5 5 1.0
f 2 1 <--- fix variable #2 to value of 1

Here is the same problem from above, but without the comments, in a formally correct syntax:

MAXIMIZE
1
1.0
2.0
6 7
0 0 1.0
1 1 1.0
2 2 1.0
3 3 1.0
3 4 1.0
4 4 1.0
5 5 1.0
f 2 1

Example#

If we take the example from above, the solver would be solving the following problem:

\[\begin{split}Q = \begin{bmatrix} 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1 \end{bmatrix}, \quad x_2 = 1.\end{split}\]
On this page