Problem Setting

Create an algorithm which provides quadratizations for higher order pseudo-Boolean functions.

Definitions: Higher order and quadratic pseudo-Boolean function

Let f(X) be a pseudo-Boolean function of N binary variables X = \left[ x_1, \ldots, x_{N} \right] (x_i \in \left\{ 0, 1 \right\}) and g(Y) be a pseudo-Boolean function of S binary variables Y = \left[ y_1, \ldots, y_{S} \right] (y_i \in \left\{ 0, 1 \right\}). For the scope of this contest let f(X) and g(Y) be polynomials

• f(X) = f(x_1, \ldots, x_{N}) = H + \sum_{i=1}^{N} p_i x_i + \sum_{1 \leq i < j \leq N} q_{ij} x_i x_j + \sum_{1 \leq i < j < k \leq N} r_{ijk} x_i x_j x_k + \cdots,
• g(Y) = g(y_1, \ldots, y_{S}) = H' + \sum_{i=1}^{S} p_i' y_i + \sum_{1 \leq i < j \leq N+M} q_{ij}' y_i y_j,

Task: Algorithm for quadratization of higher order Boolean functions

Given a higher order pseudo-Boolean function f(X) as an input, create an algorithm which provides a quadratic pseudo-Boolean function g(Y)=g(X,W) of degree at most 2, such that:

f(X) = \min_{W \in \left\{0, 1\right\}^M} g(X, W) for all X \in \left\{0, 1\right\}^N.

A function g(Y)=g(X,W) which fulfills the above condition is referred to as a quadratization of f(X). A quadratization g(Y)=g(X,W) shares a common set of variables \left[ y_1, \ldots, y_{N} \right]=\left[ x_1, \ldots, x_{N} \right]=X \in \left\{0, 1\right\}^N with f(X), while maintaining a set of additional ancillary variables \left[ y_{N+1}, \ldots, y_{N+M} \right]=\left[ w_1, \ldots, w_{M} \right]=W \in \left\{0, 1\right\}^M.

Side Remark:

Checking whether a submitted algorithm provides an appropriate quadratization according to the aforementioned definition is impossible within the given limits of computing time. For this reason we accept algorithms which provide a quadratic pseudo-Boolean function that provides an upper bound on the true quadratization according to:

f(X) \le \min_{W \in \left\{0, 1\right\}^M} g(X, W) for all X \in \left\{0, 1\right\}^N.

This being said, it is worth to keep in mind that successful submissions will provide a quadratic pseudo-Boolean function which keeps the gap

e(X):= \min_{W \in \left\{0, 1\right\}^M} g(X, W)-f(X)\ge 0

Scoring:

The award-winning algorithm will provide quadratizations g(X,W) of pseudo-Boolean functions f(X) such that

• g(X,W) has as few ancillary variables W=[w_1, \ldots, w_M] as possible,
• g(X,W) has as few terms as possible,
• the coefficients of g(X,W) are as small as possible.
• Additional score is awarded, if the algorithm provides quadratizations g(X,W), which can be easily minimized with respect to the ancillary variables W by means of simulated annealing.

On the Differences of Problem Setting A, B, and C

Note that the thought after algorithms in problem statement A, B, and C are basically identical. In particular, it is admissible to submit the identical algorithm to all three problems and obtain score for it. On the other hand, the main difference between Problem settings A, B, and C is the structure of the higher order pseudo-Boolean f(X) which will be provided to your algorithm as an input.

All input problems will take the structure of a higher order pseudo-Boolean polynomial f(X) as specified by the equation above. For all input cases we will chose random coefficients H, p_i, q_{ij}, r_{ijk}, \cdots \in \mathbb{Z} uniformly sampled in a range to be specified below. The input samples will vary with respect to the structure of the non-zero coefficients.

• Problem A: In problem A we consider higher-order pseudo-Boolean input functions with large degrees d, i.e., degree's up to the full size of available variables d\le N. The number of terms with non-zero coefficients will however be very low, such that the input becomes "sparse".
• Problem B: In problem B we consider higher-order pseudo-Boolean input functions with low degree. In particular, no input function will have degree larger than 6 (d\le 6). Furthermore, only some of the potential polynomial terms will have non-zero coefficients, thus, resulting in another sparse input.
• Problem C: In problem C we will provide input problems of degree 6 with coefficients of all available terms chosen as random inputs, thus, resulting in a "dense" input problem.

The purpose of providing three different classes of input problems lies in giving the algorithms the chance to allow for different tuning strategies with respect to different input targets. A comprehensive summary of the input problems in problem statements A, B, and C is given in the table below.

Scoring

Your algorithm will be scored by running it on several input problems f(X). For each input problem the resulting quadratization g(X,W) will be scored as described below. Your total score will be the sum of the score obtained for each input problem.

Number of input problems during and after the contest:

During the contest we will estimate your score by running your algorithm on a preliminary set of 15 input problems for each of the sub-problems A, B, and C. This will allow for estimating your rank. After the contest finishes we will evaluate your final score by running your algorithm on a set of 100 previously undisclosed input problems (created with the exact same statistical properties) for each of the sub-problems A, B, and C. This measure is taken to avoid tuning of algorithms to a particular statistical fluctuations on the set of input problems.

Scoring of input problems:

For each input problem your algorithm will be awarded the following score:

A \times PX \times PY \times PZ,

where A=10000 is a constant and factors are defined as follows

• PX = E \left(1 - \frac{\min(e_{SA}, T)}{T} \right),
• PY = \frac{1000}{BM + L + 1000},
• PZ = \frac{1000}{\max_i |c_i'| + 1000},

The scoring is based on the following logic:

• PX measures the ability of your algorithm to provide quadratizations from which the true value of the original function f(X) can approximately be recovered based on simulated annealing. In particular, if your algorithm provides quadratizations for which e_{SA} is zero, the first factor will take its maximal value E. In addition, a partial score is awarded, if e_{SA} < T=100, i.e., if your algorithm at least allows to approximate the original value of f(X) with some accuracy. Finally, should e_{SA} < 0 your algorithm provides a wrong submission and your total score becomes zero. For further details on e_{SA}, see the section below.
• PY introduces a fine for quadratizations which use too many ancillary variables M or else produce quadratizations with many terms L. It shall encourage algorithms which create quadratizations with as few ancillary variables and few terms.
• PY introduces a fine for algorithms which produce coefficients with large modulus \max_{i}|c_i'|. This shall encourage algorithms for which the bit width of the required coefficients shall not grow too severely.

SCORE = \lfloor \frac{PA + PB}{2} \rfloor.

Determination of e_{SA}

In order to determine e_{SA} we proceed using the following steps:

• We fix the set of input variables x_1, \dots ,x_N either in a random configuration X \in \left\{ 0, 1 \right\}^N or in the configuration where all bits are selected, i.e., [x_1, x_2, ..., x_N]=[1, 1, ..., 1] .
• For this set of variables X we minimize g(X,W) with respect to the remaining new variables W \in \left\{ 0, 1 \right\}^M by running a version of simulated annealing (SA) with five repetitions. [See provided software toolkit for details.] The five repititions of SA will result in a configuration of variables w_{1,SA}, \dots ,w_{M,SA} for which we obtain the minimal gap

e_{SA} :=g(x_1, \dots ,x_N, w_{1,SA}, \dots ,w_{M,SA})-f(x_1, \dots ,x_N).

• e_{SA} will be zero, if simulated annealing finds the true minimum with respect to W. If simulated annealing finds an approximate local minimum, e_{SA} will be larger than zero. If e_{SA} is smaller than zero, the submitted algorithm has a bug and the total score will be set to zero.

Please note that the seed for choosing the random configuration x_1, \dots ,x_N as well as the random elements of the simulated annealing procedure cannot be disclosed. In contrast to the contest ranking, where x_1, \dots ,x_N was identical for each of the 15 cases, the final test will use distinct configurations x_1, \dots ,x_N for all 100 cases.

Invalid submissions

Note that a submitted algorithm might be invalid for several reasons, e.g., if the gap between the true function value and the minimum of the quadratization with respect to the true minimum becomes smaller than zero. Another case in which a given submission gets zero score occurs, if the output violates the output format described above. In all these cases the given submission will be marked with the signal WA in the AtCoder standings section.

Input Format Example 1

3 1
3 1 1 2 3

This input file represents the function f(x_1, x_2, x_3) = x_{1}x_{2}x_{3}.

Output Format Example 1

4 5
2 1 1 2
1 1 4
2 -1 1 4
2 -1 2 4
2 1 3 4

This output example provides a quadratization of the input example with a total of S=4 binary variables and L=5 terms, i.e., the quadratization uses a single ancillary variable W = \left[ w_1 \right] and M=1. Alltogether the output format example decodes the following cost function g(x_1, x_2, x_3, w_1) = x_{1}x_{2} +w_1 -x_{1}w_1 -x_{2}w_1 +x_{3}w_1 = x_{1}x_{2} +w_1(1 -x_1 -x_2 +x_3).

The output provides a valid quadratization of the input problem, because for any combination x_1, x_2, x_3 it can be shown that f(x_1, x_2, x_3) = \min_{W} g(x_1, x_2, x_3, W). The maximal coefficient of the quadratization is \max|c_i'|=1.

Finally, assuming that e_{SA} = 0 becomes zero both for a random configuration of [x_1, x_2, x_3] as well as the configuration [x_1, x_2, x_3]=[1,1,1] the above output has

• M=1 ancillary variables,
• L=5 terms,
• the maximal coefficient \max_i |c_i'|=1,

PA = PB = A\times E(1-0)\times\frac{1000}{B\times1 +5 + 1000} \times \frac{1000}{1+1000}=98910990.00009891.

SCORE = \lfloor \frac{2\times 98910990.00009891}{2}\rfloor =98910990.

Input Format Example 2

6 7
3 69 3 5 6
3 -93 2 3 4
3 -63 2 5 6
4 -95 1 2 5 6
3 24 1 4 5
2 75 1 6
2 49 3 6

Output Format Example 2

11 28
2 24 1 4
2 24 1 5
2 75 1 6
2 -95 1 7
2 -24 1 8
2 -95 2 7
2 -93 2 9
2 -63 2 10
2 69 3 5
2 118 3 6
2 -93 3 9
2 -69 3 11
2 24 4 5
2 -24 4 8
2 -93 4 9
2 69 5 6
2 -95 5 7
2 -24 5 8
2 -63 5 10
2 -69 5 11
2 -95 6 7
2 -63 6 10
2 -69 6 11
1 285 7
1 24 8
1 186 9
1 126 10
1 69 11

Sample Code and Literature Hints

• Sample code for generating input formats and score evaluation can be downloaded from here.
• In order to get started on quadratization, we encourage the use of the literature and open source software listed below.

Review

A brief review giving an introduction to the main ideas of reducing higher-order Boolean polynomials into quadratic pseudo-Boolean polynomials.

• [Review] Endre Boros and Aritanan Gruber, "On Quadratization of Pseudo-Boolean Functions" [arxiv]

Fix, Gruber, Boros, Zabih

Two papers on a state of the art algorithm for quadratizing higher-order pseudo-Boolean cost functions and an open source software implementation are available from the following links.

• [Paper] Alexander Fix et al., "A graph cut algorithm for higher-order Markov Random Fields" [ieee] [pdf]
• [Paper] Alexander Fix et al., "A Hypergraph-Based Reduction for Higher-Order Binary Markov Random Fields" [ieee]
• [Code] Alexander Fix

Ishikawa

• [Paper] Hiroshi Ishikawa, "Higher-order clique reduction in binary graph cut" [ieee] [pdf]
• [Paper] Hiroshi Ishikawa, "Transformation of General Binary MRF Minimization to the First-Order Case" [ieee] [pdf]
• [Code] Hiroshi Ishikawa