Quadratic pseudo-Boolean optimization (unconstrained quadratic programming) format
The goal is to minimize or maximize the quadratic function:
X' * W * X = \sum_i=1 to N \sum_j=1 to N W_ij * X_i * X_j
where W is a symmetric squared N*N matrix expressed by all its non-zero half (i<=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: for two indices i != j, coefficient W_ij = W_ji (symmetric matrix) and appears twice in the previous sum.
Note: 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 -precision to modify it, default value is 7). Infinite coefficients are forbidden.
Note: 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.
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 <= j and W_ij != 0
--- suggestions send to:
simon.degivry@toulouse.inra.fr
INRA @ 2012