Unconstrained 0-1 optimization and Lagrangean relaxation. (English) Zbl 0725.90067

Adams, Warren E.; Billionnet, Alain; Sutter, Alain

Discrete Appl. Math. 29, No. 2-3, 131-142 (1990).

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.

Reviewer: O.A.Shcherbina (Simferopol)

MSC:

90C09

Boolean programming

Keywords:

polynomial optimization; Lagrangean relaxation; unconstrained 0-1 polynomial programming; equivalent problem; roof duality gap

References:

[1]	Adams, W.P.; Dearing, P.M., On the equivalence between roof duality and Lagrangian duality for unconstrained 0-1 quadratic programming problems, () · Zbl 0794.90038
[2]	Aspvall, B.; Plass, M.F.; Tarjan, R.E., A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Inform. process. lett., 8, 121-123, (1979) · Zbl 0398.68042
[3]	Glover, F.; Woolsey, E., Converting the 0-1 polynomial programming problem to a 0-1 linear program, Oper. res., 22, 180-182, (1974) · Zbl 0272.90049
[4]	Hammer, P.L.; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Math. programming, 28, 121-155, (1984) · Zbl 0574.90066
[5]	P. Hansen, S.H. Lu and B. Simeone, On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization, Discrete Appl. Math., to appear · Zbl 0744.90060
[6]	Lu, S.H.; Williams, A.C., Roof duality for polynomial 0-1 optimization, Math. programming, 37, 357-360, (1987) · Zbl 0632.90044
[7]	Rhys, J.M.W., A selection problem of shared fixed costs and network flows, Management sci., 17, 200-207, (1970) · Zbl 0203.52505