Quadratic pseudo-Boolean optimization: Difference between revisions

Revision as of 12:23, 1 June 2021

Revision as of 14:50, 1 June 2021

Line 31:

The algorithm can be divided in three steps: graph construction, max-flow computation, and assignment of values to the variables.

When constructing the graph, the set of vertices <math>V</math> contains the source and sink nodes <math>s</math> and <math>t</math>, and a couplepair of nodes <math>p</math> and <math>p'</math> for each variable. After re-parametrising the function to normal form,<ref name="normal form" group="note" /> a pair of edges is added to the graph for each term <math>w</math>:

* for each term <math>w_p(0)</math> the edges <math>p \rightarrow t</math> and <math>s \rightarrow p'</math>, with weight <math>\frac{1}{2} w_p(0)</math>;

* for each term <math>w_p(1)</math> the edges <math>s \rightarrow p</math> and <math>p' \rightarrow t</math>, with weight <math>\frac{1}{2} w_p(1)</math>;