QPBO format (.qpbo)

In the quadratic pseudo-Boolean optimization (unconstrained quadratic programming) format, the goal is to minimize or maximize the quadratic function:

\(X' * W * X = \sum_{i=1}^N \sum_{j=1}^N W_{ij} * X_i * X_j\)

where \(W\) is a symmetric squared \(N \times N\) matrix expressed by all its non-zero half (\(i \leq j\)) squared matrix coefficients, \(X\) is a vector of \(N\) binary variables with domain values in \(\{0,1\}\) or \(\{1,-1\}\), and \(X'\) is the transposed vector of \(X\).

Note that for two indices \(i \neq j\), coefficient \(W_{ij} = W_{ji}\) (symmetric matrix) and it appears twice in the previous sum. It can be controled by the option {tt -qpmult=[double]} which defines a coefficient multiplier for quadratic terms (default value is 2).

Note also that coefficients can be positive or negative and are real float numbers. They are converted to fixed-point real numbers by multiplying them by \(10^{precision}\) (see option {em -precision} to modify it, default value is 7). Infinite coefficients are forbidden.

Notice that depending on the sign of the number of variables in the first text line, the domain of all variables is either \(\{0,1\}\) or \(\{1,-1\}\).

Warning! The encoding in Weighted CSP of variable domain \(\{1,-1\}\) associates for each variable value the following index: value 1 has index 0 and value -1 has index 1 in the solutions found by toulbar2. The encoding of variable domain \(\{0,1\}\) is direct.

Qpbo is a file text format:

  • First line contains the number of variables \(N\) and the number of non-zero coefficients \(M\).

    If \(N\) is negative then domain values are in \(\{1, -1\}\), otherwise \(\{0, 1\}\). If \(M\) is negative then it will maximize the quadratic function, otherwise it will minimize it.

  • Followed by \(|M|\) lines where each text line contains three values separated by spaces: position index \(i\) (integer belonging to \([1,|N|]\)), position index \(j\) (integer belonging to \([1,|N|]\)), coefficient \(W_{ij}\) (float number) such that \(i \leq j\) and \(W_{ij} \neq 0\).