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

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.


90C09 Boolean programming
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.