747
eng
reportzib
0
2003-08-13
2003-08-13
--
Polynomial Inequalities Representing Polyhedra
Our main result is that every n-dimensional polytope can be described by at most (2n-1) polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n-2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities.
03-25
748
urn:nbn:de:0297-zib-7473
For a rev. vers. see ZR-04-53; the final version appeared in: Mathematical Programming 103 (2005) 35-44
Hartwig Bosse
Martin GrÃ¶tschel
Martin Henk
ZIB-Report
03-25
eng
uncontrolled
polyhedra and polytopes
eng
uncontrolled
semi-algebraic sets
eng
uncontrolled
polyhedral combinatorics
eng
uncontrolled
polynomial inequalities
eng
uncontrolled
stability index
Informatik, Informationswissenschaft, allgemeine Werke
Semialgebraic sets and related spaces
n-dimensional polytopes
Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]
Combinatorial optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut
ZIB Allgemein
GrÃ¶tschel, Martin
https://opus4.kobv.de/opus4-zib/files/747/ZR-03-25.ps
https://opus4.kobv.de/opus4-zib/files/747/ZR-03-25.pdf