Geodesic
Elimination of inequalities from a facet description of a polyhedron
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 37-45 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider the following problem: given vertex and facet representations of a convex polyhedron, compute a vertex representation of the polyhedron defined by a subsystem of inequalities of the original polyhedron. We present a new algorithm, prove its correctness, and give upper bounds for the complexity. Unlike other approaches, the proposed algorithm is polynomial for the case of removing one inequality. Computational experiments show that the algorithm outperforms the incremental method in a number of cases.
Keywords: convex polyhedra, constraint removal, double description method. 
@article{TIMM_2015_21_3_a4,
     author = {S. Bastrakov and N. Yu. Zolotykh},
     title = {Elimination of inequalities from a facet description of a polyhedron},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {37--45},
     year = {2015},
     volume = {21},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a4/}
}
TY  - JOUR
AU  - S. Bastrakov
AU  - N. Yu. Zolotykh
TI  - Elimination of inequalities from a facet description of a polyhedron
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2015
SP  - 37
EP  - 45
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a4/
LA  - ru
ID  - TIMM_2015_21_3_a4
ER  - 
%0 Journal Article
%A S. Bastrakov
%A N. Yu. Zolotykh
%T Elimination of inequalities from a facet description of a polyhedron
%J Trudy Instituta matematiki i mehaniki
%D 2015
%P 37-45
%V 21
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a4/
%G ru
%F TIMM_2015_21_3_a4
S. Bastrakov; N. Yu. Zolotykh. Elimination of inequalities from a facet description of a polyhedron. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 21 (2015) no. 3, pp. 37-45. http://geodesic.mathdoc.fr/item/TIMM_2015_21_3_a4/

[1] Chernikov S.N., “Lineinye neravenstva”, Nauka, M., 1968, 488 pp. | MR | Zbl

[2] Eremin I.I., Astafev N.N., Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya, Nauka, M., 1970, 191 pp. | MR

[3] Eremin I.I., Teoriya lineinoi optimizatsii, Izd-vo “Ekaterinburg”, Ekaterinburg, 1999, 312 pp.

[4] Tsigler G., Teoriya mnogogrannikov, MTsNMO, M., 2014, 586 pp.

[5] Chernikova N.V., “Algoritm dlya otyskaniya mnozhestva vsekh reshenii zadachi lineinogo programmirovaniya”, Zhurn. vychisl. matematiki i mat. fiziki, 8:6 (1968), 1387–1395 | Zbl

[6] Horst R., Pardalos P.M., Thoai N., Introduction to global optimization, Nonconvex Optim. Appl., 3, Kluwer Academic Publishers, Dordrecht, 1995, 318 pp. | DOI | MR | Zbl

[7] Terzer M., Stelling J., “Large-scale computation of elementary flux modes with bit pattern trees”, Bioinformatics, 24:19 (2008), 2229–2235 | DOI

[8] Cousot P., Halbwachs N., “Automatic discovery of linear restraints among variables of a program”, Conf. Record of the Fifth Annual ACM Symposium on Principles of Programming Languages, 1978, 84–96

[9] Bagnara R., Hill P.M., Zaffanella E., “Applications of polyhedral computations to the analysis and verification of hardware and software systems”, Theoret. Comput. Sci., 410:46 (2009), 4672–4691 | DOI | MR | Zbl

[10] Panyukov A.V., “Predstavlenie summy Minkovskogo dlya dvukh poliedrov sistemoi lineinykh neravenstv”, Vestn. YuUrGU. Ser. Mat. modelirovanie i programmirovanie, 2012, no. 14, 108–119

[11] Zorkaltsev V.I., “Ivan Ivanovich Eremin i lineinaya optimizatsiya”, Informatsionnyi byulleten Assotsiatsii matematicheskogo programmirovaniya, 2015, no. 13, 241–250, IMM UrO RAN, Ekaterinburg

[12] T.S. Motskin, Kh. Raifa, D.L. Tompson, R.M. Troll, “Metod dvoinogo opisaniya”, Matrichnye igry, Fizmatgiz, M., 1961, 81–109

[13] Chernikova N.V., “Algoritm dlya nakhozhdeniya obschei formuly neotritsatelnykh reshenii sistemy lineinykh neravenstv”, Zhurn. vychisl. matematiki i mat. fiziki, 5:2 (1965), 334–337 | MR

[14] Amato G., Scozzari F., Zaffanella E., “Efficient sonstraint/generator removal from double description of polyhedra”, Electr. Notes Theor. Comput. Sci., 307 (2014), 3–15 | DOI

[15] Avis D., Bremner D., Seidel R., “How good are convex hull algorithms?”, Comput. Geom., 7:5-6 (1997), 265–301 | DOI | MR | Zbl

[16] Avis D., Fukuda K., “Reverse search for enumeration”, Discrete Appl. Math., 65:1-3 (1996), 21–46 | DOI | MR | Zbl

[17] Bremner D., Fukuda K., Marzetta A., “Primal-dual methods for vertex and facet enumeration”, Discrete Comput. Geom., 20:3 (1998), 333–357 | DOI | MR | Zbl

[18] Zolotykh N.Yu., “Novaya modifikatsiya metoda dvoinogo opisaniya dlya postroeniya ostova mnogogrannogo konusa”, Zhurn. vychisl. matematiki i mat. fiziki, 52:1 (2012), 153–163 | MR | Zbl

[19] Fukuda K., Prodon A., “Double description method revisited”, Lecture Notes in Comput. Sci., 1120 (1996), 91–111 | DOI | MR

[20] GiTHub [site]: qskeleton. URL: https:github.com/sbastrakov/qskeleton

[21] Bastrakov S.I., Zolotykh N.Yu., “Ispolzovanie idei algoritma Quickhull v metode dvoinogo opisaniya”, Vychislitelnye metody i programmirovanie, 12 (2011), 232–237

[22] GiTHub [site]: cddlib. URL: https:github.com/mcmtroffaes/cddlib/