# zbMATH — the first resource for mathematics

A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. (English) Zbl 0712.90050
The authors consider the feasible region $$X=\{x\in R^ n:$$ Ax$$\geq b$$, $$0\leq x\leq e$$, x integer$$\}$$ of a linear 0-1 programming problem. By multiplication of each of the constraints (excluding $$0\leq x\leq e)$$ by each of the polynomial factors $F_ d(J_ 1,J_ 2)=(\prod_{j\in J_ 1}x_ j)(\prod_{j\in J_ 2}(1-x_ j))$ for $$J_ 1,J_ 2\subseteq N=\{1,2,...,n\}$$, $$J_ 1\cap J_ 2=\emptyset$$ and $$| J_ 1\cup J_ 2| =d$$, the 0-1 programming problem is converted into a series of 0-1 polynomial programming problems for $$d=0,1,2,...,n$$. The resulting polynomial constraints are relinearized using the relationships $$x_ j^ 2=x_ j$$ and $$x_ j(1-x_ j)=0$$ for $$j=1,...,n$$. The authors show that the projections of the feasible regions of the relinearized polynomial programming problems onto the x-space for $$d=0,1,2,...,n$$ is a hierarchy of relaxations $$X_{P_ d}$$ of X with $$X_{P_ 0}\supseteq X_{P_ 1}\supseteq...\supseteq X_{P_ n}$$, where $$X_{P_ 0}$$ is the linear programming relaxation and $$X_{P_ n}$$ the convex hull of X.
Reviewer: G.Schulz

##### MSC:
 90C09 Boolean programming 90C05 Linear programming 90C27 Combinatorial optimization 90C10 Integer programming
Full Text: