Unconstrained 0-1 optimization and Lagrangean relaxation (Q2277361)

The unconstrained 0-1 polynomial programming problem (PPP), (P1) is considered. An equivalent problem with nonnegative coefficients of the terms of degree 2 and more is used: \[ (P2)\quad Z_{P_ 2}=\max \{f(x,\bar x)| x\in \{0,1\}^ n,\quad \bar x\in \{0,1\}^{\{I_ c\}}= \] \[ \sum^{n}_{i=1}\ell_ ix_ i+\sum_{k\in P}d_ k\prod_{i\in Q(k)}x_ i+\sum_{k\in N}c_ k\bar x_{T(k)}\prod_{i\in R(k)}x_ i, \] (here \(\bar x_ i=1-x_ i)\). A linear function \(p(x)\), a roof for (P2), is constructed as an upper bounding function of \(f(x,\bar x)\). Let R be the set of all roofs, then the dual roof is defined as \[ W(R)=\min_{p(x)\in R}\{\max_{x\in \{0,1\}^ n}p(x)\} \] and this value may be calculated by solving the LP problem \[ Z_{LP}=\max [\sum^{n}_{i=1}\ell_ ix_ i+\sum_{k\in P}d_ xt_ k+\sum_{k\in N}c_ kw_ k] \] subject to linear constraints. W(R) is an upper bound on \(Z_{P_ 1}\) with the so-called roof duality gap \[ W(R)-Z_{P_ 1}=\min_{p(x)\in R}\{\max_{x\in \{0,1\}^ n}p(x)\}-\max_{x\in \{0,1\}^ n}\{\min_{p(x)\in R}p(x)\}. \] The problem (P3) is built from (P2) by substitution \(y_ i=\bar x_ i\). A Lagrangean dual function LD(\(\pi\)) is constructed for problem \((P3)\quad Z_{LD}=\min_{(\pi)} LD(\pi).\) One of the results is the following Theorem 1. \(W(R)=Z_{LD}.\) It is shown that checking the existence of a roof duality gap is equivalent to the checking of the consistency of a 0-1 quadratic posiform. The results of the paper are illustrated on an example of a 0-1 cubic programming problem with 4 variables.