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 float, giving the offset: constant offset of the energy.

• Next the reader expects the triplets of the upper triangular part of the QUBO matrix. A triplet is given with 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\).

• Finally, the reader expects 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
# this is a comment
2.0 <--- constant energy offest
0 0 1.0 <-- entries
0 2 1.0
0 4 -1.0
1 1 1.0
2 2 1.0
2 4 1.0
3 3 1.0
4 4 1.0
5 5 1.0
f 0 0 <--- fix variable #0 to value of 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
2.0
0 0 1.0
0 2 1.0
0 4 -1.0
1 1 1.0
2 2 1.0
2 4 1.0
3 3 1.0
4 4 1.0
5 5 1.0
f 0 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& 1& 0& -1& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1 \end{bmatrix}, \quad c=2.\ x_0 = 0,\ x_2 = 1.\end{split}\]