De Simone, Caterina The cut polytope and the Boolean quadric polytope. (English) Zbl 0683.90068 Discrete Math. 79, No. 1, 71-75 (1990). 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)]. Cited in 61 Documents MSC: 90C27 Combinatorial optimization 52Bxx Polytopes and polyhedra 90C35 Programming involving graphs or networks 90C10 Integer programming 90C09 Boolean programming 90C20 Quadratic programming Keywords:cut polytopes; Boolean quadric polytope; bijective linear transformation Citations:Zbl 0525.90094 PDFBibTeX XMLCite \textit{C. De Simone}, Discrete Math. 79, No. 1, 71--75 (1990; Zbl 0683.90068) 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.