A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope

Hanif D. Sherali; Youngho Lee; Warren P. Adams

doi:10.1016/0167-6377(94)00065-E

A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope

Hanif D. Sherali, Youngho Lee, Warren P. Adams

Research output: Contribution to journal › Article › peer-review

18 Citations (Scopus)

Abstract

We develop a framework for characterizing classes of facets for the Boolean quadric polytope obtainable through a simultaneous lifting procedure. In particular, we begin with a class of product-form facets that subsume Padberg's clique, cut, and generalized cut inequality facets. By applying the proposed general approach to this class of facets, we derive a specially structured polyhedron whose vertices describe all facets that are simultaneous liftings of these facets. We identify specific classes of vertices for this polyhedron to reveal a new class of facets for the quadric polytope. Such an approach can be applied to lifting other facets, as well as to analyze other combinatorial optimization problems.

Original language	English
Pages (from-to)	19-26
Number of pages	8
Journal	Operations Research Letters
Volume	17
Issue number	1
DOIs	https://doi.org/10.1016/0167-6377(94)00065-E
Publication status	Published - 1995 Feb

Bibliographical note

Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. DMII-9121419, and by the Air Force Office of ScientificR esearchu nderGrant No. AFOSR-90-0191.

Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

Keywords

Cut polytope
Facets
Lifting
Quadric polytope
Reformulation-linearization-technique

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Access to Document

10.1016/0167-6377(94)00065-E

Cite this

@article{ec832fc697f54bd1a8aad453da58832c,

title = "A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope",

abstract = "We develop a framework for characterizing classes of facets for the Boolean quadric polytope obtainable through a simultaneous lifting procedure. In particular, we begin with a class of product-form facets that subsume Padberg's clique, cut, and generalized cut inequality facets. By applying the proposed general approach to this class of facets, we derive a specially structured polyhedron whose vertices describe all facets that are simultaneous liftings of these facets. We identify specific classes of vertices for this polyhedron to reveal a new class of facets for the quadric polytope. Such an approach can be applied to lifting other facets, as well as to analyze other combinatorial optimization problems.",

keywords = "Cut polytope, Facets, Lifting, Quadric polytope, Reformulation-linearization-technique",

author = "Sherali, {Hanif D.} and Youngho Lee and Adams, {Warren P.}",

note = "Funding Information: This material is based upon work supported by the National Science Foundation under Grant No. DMII-9121419, and by the Air Force Office of ScientificR esearchu nderGrant No. AFOSR-90-0191. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.",

year = "1995",

month = feb,

doi = "10.1016/0167-6377(94)00065-E",

language = "English",

volume = "17",

pages = "19--26",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope

AU - Sherali, Hanif D.

AU - Lee, Youngho

AU - Adams, Warren P.

N1 - Funding Information: This material is based upon work supported by the National Science Foundation under Grant No. DMII-9121419, and by the Air Force Office of ScientificR esearchu nderGrant No. AFOSR-90-0191. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.

PY - 1995/2

Y1 - 1995/2

N2 - We develop a framework for characterizing classes of facets for the Boolean quadric polytope obtainable through a simultaneous lifting procedure. In particular, we begin with a class of product-form facets that subsume Padberg's clique, cut, and generalized cut inequality facets. By applying the proposed general approach to this class of facets, we derive a specially structured polyhedron whose vertices describe all facets that are simultaneous liftings of these facets. We identify specific classes of vertices for this polyhedron to reveal a new class of facets for the quadric polytope. Such an approach can be applied to lifting other facets, as well as to analyze other combinatorial optimization problems.

AB - We develop a framework for characterizing classes of facets for the Boolean quadric polytope obtainable through a simultaneous lifting procedure. In particular, we begin with a class of product-form facets that subsume Padberg's clique, cut, and generalized cut inequality facets. By applying the proposed general approach to this class of facets, we derive a specially structured polyhedron whose vertices describe all facets that are simultaneous liftings of these facets. We identify specific classes of vertices for this polyhedron to reveal a new class of facets for the quadric polytope. Such an approach can be applied to lifting other facets, as well as to analyze other combinatorial optimization problems.

KW - Cut polytope

KW - Facets

KW - Lifting

KW - Quadric polytope

KW - Reformulation-linearization-technique

UR - http://www.scopus.com/inward/record.url?scp=0029254543&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029254543&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(94)00065-E

DO - 10.1016/0167-6377(94)00065-E

M3 - Article

AN - SCOPUS:0029254543

SN - 0167-6377

VL - 17

SP - 19

EP - 26

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this