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

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