×

The cut polytope and the Boolean quadric polytope. (English) Zbl 0683.90068

Summary: F. Barahona [Oper. Res. Lett. 2, 107-111 (1983; Zbl 0525.90094)] defined the class of cut polytopes; recently M. Padberg [The Boolean quadric polytope: Some characteristics and facets (unpublished manusc. 1988)] defined the class of Boolean quadric polytopes. We show that every Boolean quadric polytope is the image of a cut polytope under a bijective linear transformation, and so studying Boolean quadric polytopes reduces to studying special cut polytopes. Our proof uses an idea introduced by P. L. Hammer [Oper. Res. 13, 388-399 (1965)].

MSC:

90C27 Combinatorial optimization
52Bxx Polytopes and polyhedra
90C35 Programming involving graphs or networks
90C10 Integer programming
90C09 Boolean programming
90C20 Quadratic programming

Citations:

Zbl 0525.90094
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barahona, F., The max-cut problem on graphs not contractible to \(K_5\), Operations Research Letters, 2, 107-111 (1983) · Zbl 0525.90094
[2] Barahona, F.; Mahjoub, A. R., On the cut polytope, Math. Programming, 36, 157-173 (1986) · Zbl 0616.90058
[3] Deza, M., Matrices de formes quadratiques non negatives pour des arguments binaires, C.R. Acad. Sc. Paris, 277, 873-875 (1973) · Zbl 0275.05014
[4] Hammer, P. L., Some network flow problems solved with pseudo-boolean programming, Operations Research, 13, 388-399 (1965) · Zbl 0132.13804
[5] Padberg, M., The Boolean Quadric Polytope: Some Characteristics and Facets (March, 1988), Manuscript
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.