Cutting planes and the elementary closure in fixed dimension
Identifieur interne : 000899 ( PascalFrancis/Corpus ); précédent : 000898; suivant : 000900Cutting planes and the elementary closure in fixed dimension
Auteurs : A. Bockmayr ; F. EisenbrandSource :
- Mathematics of Operations Research [ 0364-765X ] ; 2001.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
The elementary closure P$PRM of a polyhedron P is the intersection of P with all its Gomory-Chvatal cutting planes. P$PRM is a rational polyhedron provided that P is rational. The known bounds for the number of inequalities defining P$PRM are exponential, even in fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. If P is a simplicial cone, we construct a polytope Q, whose integral elements correspond to cutting planes of P. The vertices of the integer hull Q1 include the facets of P $PRM. A polynomial upper bound on their number can be obtained by applying a result of Cook et al. (1992). Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone that correspond to vertices of Q1.
Notice en format standard (ISO 2709)
Pour connaître la documentation sur le format Inist Standard.
| pA |
|
|---|
Format Inist (serveur)
| NO : | PASCAL 02-0067045 EI |
|---|---|
| ET : | Cutting planes and the elementary closure in fixed dimension |
| AU : | BOCKMAYR (A.); EISENBRAND (F.) |
| AF : | Universite Henri Poincare LORIA Campus Scientifique/F-54506 Vanduvre-les-Nancy/France (1 aut.) |
| DT : | Publication en série; Niveau analytique |
| SO : | Mathematics of Operations Research; ISSN 0364-765X; Etats-Unis; Da. 2001; Vol. 26; No. 2; Pp. 304-312; Bibl. 29 Refs. |
| LA : | Anglais |
| EA : | The elementary closure P$PRM of a polyhedron P is the intersection of P with all its Gomory-Chvatal cutting planes. P$PRM is a rational polyhedron provided that P is rational. The known bounds for the number of inequalities defining P$PRM are exponential, even in fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. If P is a simplicial cone, we construct a polytope Q, whose integral elements correspond to cutting planes of P. The vertices of the integer hull Q1 include the facets of P $PRM. A polynomial upper bound on their number can be obtained by applying a result of Cook et al. (1992). Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone that correspond to vertices of Q1. |
| CC : | 001D01A; 001D02A; 001A02D; 001A02B |
| FD : | Théorie; Complexité calcul; Polynôme; Théorie ensemble; Méthode heuristique; Algorithme; Programmation en nombres entiers |
| ED : | Cutting plane methods; Theory; Computational complexity; Polynomials; Set theory; Heuristic methods; Algorithms; Integer programming |
| LO : | INIST-17696 |
| ID : | 02-0067045 |
Links to Exploration step
Pascal:02-0067045Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Cutting planes and the elementary closure in fixed dimension</title><author><name sortKey="Bockmayr, A" sort="Bockmayr, A" uniqKey="Bockmayr A" first="A." last="Bockmayr">A. Bockmayr</name><affiliation><inist:fA14 i1="01"><s1>Universite Henri Poincare LORIA Campus Scientifique</s1><s2>F-54506 Vanduvre-les-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14></affiliation></author><author><name sortKey="Eisenbrand, F" sort="Eisenbrand, F" uniqKey="Eisenbrand F" first="F." last="Eisenbrand">F. Eisenbrand</name></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">02-0067045</idno><date when="2001">2001</date><idno type="stanalyst">PASCAL 02-0067045 EI</idno><idno type="RBID">Pascal:02-0067045</idno><idno type="wicri:Area/PascalFrancis/Corpus">000899</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Cutting planes and the elementary closure in fixed dimension</title><author><name sortKey="Bockmayr, A" sort="Bockmayr, A" uniqKey="Bockmayr A" first="A." last="Bockmayr">A. Bockmayr</name><affiliation><inist:fA14 i1="01"><s1>Universite Henri Poincare LORIA Campus Scientifique</s1><s2>F-54506 Vanduvre-les-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14></affiliation></author><author><name sortKey="Eisenbrand, F" sort="Eisenbrand, F" uniqKey="Eisenbrand F" first="F." last="Eisenbrand">F. Eisenbrand</name></author></analytic><series><title level="j" type="main">Mathematics of Operations Research</title><title level="j" type="abbreviated">Math Oper Res</title><idno type="ISSN">0364-765X</idno><imprint><date when="2001">2001</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Mathematics of Operations Research</title><title level="j" type="abbreviated">Math Oper Res</title><idno type="ISSN">0364-765X</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Computational complexity</term><term>Cutting plane methods</term><term>Heuristic methods</term><term>Integer programming</term><term>Polynomials</term><term>Set theory</term><term>Theory</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Théorie</term><term>Complexité calcul</term><term>Polynôme</term><term>Théorie ensemble</term><term>Méthode heuristique</term><term>Algorithme</term><term>Programmation en nombres entiers</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The elementary closure P$PRM of a polyhedron P is the intersection of P with all its Gomory-Chvatal cutting planes. P$PRM is a rational polyhedron provided that P is rational. The known bounds for the number of inequalities defining P$PRM are exponential, even in fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. If P is a simplicial cone, we construct a polytope Q, whose integral elements correspond to cutting planes of P. The vertices of the integer hull Q1 include the facets of P $PRM. A polynomial upper bound on their number can be obtained by applying a result of Cook et al. (1992). Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone that correspond to vertices of Q1.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0364-765X</s0></fA01><fA03 i2="1"><s0>Math Oper Res</s0></fA03><fA05><s2>26</s2></fA05><fA06><s2>2</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>Cutting planes and the elementary closure in fixed dimension</s1></fA08><fA11 i1="01" i2="1"><s1>BOCKMAYR (A.)</s1></fA11><fA11 i1="02" i2="1"><s1>EISENBRAND (F.)</s1></fA11><fA14 i1="01"><s1>Universite Henri Poincare LORIA Campus Scientifique</s1><s2>F-54506 Vanduvre-les-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></fA14><fA20><s1>304-312</s1></fA20><fA21><s1>2001</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>17696</s2></fA43><fA44><s0>A100</s0></fA44><fA45><s0>29 Refs.</s0></fA45><fA47 i1="01" i2="1"><s0>02-0067045</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Mathematics of Operations Research</s0></fA64><fA66 i1="01"><s0>USA</s0></fA66><fC01 i1="01" l="ENG"><s0>The elementary closure P$PRM of a polyhedron P is the intersection of P with all its Gomory-Chvatal cutting planes. P$PRM is a rational polyhedron provided that P is rational. The known bounds for the number of inequalities defining P$PRM are exponential, even in fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. If P is a simplicial cone, we construct a polytope Q, whose integral elements correspond to cutting planes of P. The vertices of the integer hull Q1 include the facets of P $PRM. A polynomial upper bound on their number can be obtained by applying a result of Cook et al. (1992). Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone that correspond to vertices of Q1.</s0></fC01><fC02 i1="01" i2="X"><s0>001D01A</s0></fC02><fC02 i1="02" i2="X"><s0>001D02A</s0></fC02><fC02 i1="03" i2="X"><s0>001A02D</s0></fC02><fC02 i1="04" i2="X"><s0>001A02B</s0></fC02><fC03 i1="01" i2="1" l="ENG"><s0>Cutting plane methods</s0><s4>INC</s4></fC03><fC03 i1="02" i2="1" l="FRE"><s0>Théorie</s0></fC03><fC03 i1="02" i2="1" l="ENG"><s0>Theory</s0></fC03><fC03 i1="03" i2="1" l="FRE"><s0>Complexité calcul</s0></fC03><fC03 i1="03" i2="1" l="ENG"><s0>Computational complexity</s0></fC03><fC03 i1="04" i2="1" l="FRE"><s0>Polynôme</s0></fC03><fC03 i1="04" i2="1" l="ENG"><s0>Polynomials</s0></fC03><fC03 i1="05" i2="1" l="FRE"><s0>Théorie ensemble</s0></fC03><fC03 i1="05" i2="1" l="ENG"><s0>Set theory</s0></fC03><fC03 i1="06" i2="1" l="FRE"><s0>Méthode heuristique</s0></fC03><fC03 i1="06" i2="1" l="ENG"><s0>Heuristic methods</s0></fC03><fC03 i1="07" i2="1" l="FRE"><s0>Algorithme</s0></fC03><fC03 i1="07" i2="1" l="ENG"><s0>Algorithms</s0></fC03><fC03 i1="08" i2="1" l="FRE"><s0>Programmation en nombres entiers</s0><s3>P</s3></fC03><fC03 i1="08" i2="1" l="ENG"><s0>Integer programming</s0><s3>P</s3></fC03><fN21><s1>037</s1></fN21></pA></standard><server><NO>PASCAL 02-0067045 EI</NO><ET>Cutting planes and the elementary closure in fixed dimension</ET><AU>BOCKMAYR (A.); EISENBRAND (F.)</AU><AF>Universite Henri Poincare LORIA Campus Scientifique/F-54506 Vanduvre-les-Nancy/France (1 aut.)</AF><DT>Publication en série; Niveau analytique</DT><SO>Mathematics of Operations Research; ISSN 0364-765X; Etats-Unis; Da. 2001; Vol. 26; No. 2; Pp. 304-312; Bibl. 29 Refs.</SO><LA>Anglais</LA><EA>The elementary closure P$PRM of a polyhedron P is the intersection of P with all its Gomory-Chvatal cutting planes. P$PRM is a rational polyhedron provided that P is rational. The known bounds for the number of inequalities defining P$PRM are exponential, even in fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. If P is a simplicial cone, we construct a polytope Q, whose integral elements correspond to cutting planes of P. The vertices of the integer hull Q1 include the facets of P $PRM. A polynomial upper bound on their number can be obtained by applying a result of Cook et al. (1992). Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone that correspond to vertices of Q1.</EA><CC>001D01A; 001D02A; 001A02D; 001A02B</CC><FD>Théorie; Complexité calcul; Polynôme; Théorie ensemble; Méthode heuristique; Algorithme; Programmation en nombres entiers</FD><ED>Cutting plane methods; Theory; Computational complexity; Polynomials; Set theory; Heuristic methods; Algorithms; Integer programming</ED><LO>INIST-17696</LO><ID>02-0067045</ID></server></inist></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000899 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000899 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Corpus
|type= RBID
|clé= Pascal:02-0067045
|texte= Cutting planes and the elementary closure in fixed dimension
}}
| This area was generated with Dilib version V0.6.33. |  |