Pseudo-Boolean function: Difference between revisions

Revision as of 22:20, 27 May 2021

Revision as of 01:01, 1 June 2021

Line 25:

===Quadratizations===

If the degree of ''f'' is greater than 2, one can always employ ''reductions'' to obtain an equivalent quadratic problem with additional variables. AnOne openpossible sourcereduction book on the subject, mainly written by Nike Dattani, contains dozens of different quadratization methods.<ref name="dattani">{{citationis

| last1 = Dattani | first1 = N.

| title = Quadratization in discrete optimization and quantum mechanics

| date = 2019-01-14| arxiv = 1901.04405

}}</ref>

One possible reduction is

:<math> \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3) </math>

There are other possibilities, for example,