On the dynamic problem of computing generators of a polyhedral cone

S. I. Bastrakov   ; N. Yu. Zolotykh

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 9 (2017) no. 1, pp. 5-12

Résumé

This paper considers a dynamic problem of computing generators of a polyhedral cone. The problem is to sequentially perform operations of adding and removing inequalities from a facet description of the polyhedral cone with a corresponding re-computation of generators. The application of a double description method for both operations is discussed and complexity estimation is given in the paper. Adding a new inequality corresponds to a single step of the double description method. It can be performed with time complexity being quadratic or cubic of the input size for the current step, depending on the modification of the method and adjacency tests chosen. We give complexity bounds for adding a single inequality with widely used algebraic and combinatorial adjacency tests. The problem of removing inequalities is intrinsically much harder, compared to adding inequalities. We briefly describe the naive and incremental algorithms and show an example with output size being superpolynomial of the input size in case of removing a single inequality. A subclass of problems with certain adjacency properties is investigated, for this subclass we prove that the output size is bounded by a quadratic function of the input size. Finally, we prove that for the distinguished subclass any finite sequence of adding and removing inequalities can be performed in polynomial time of the input size.

Détail

Keywords: system of linear inequalities, polyhedral cone, computing dual description, double description method.

Bibliographie

[1] Chernikov S. N., Linear inequalities, Nauka Publ., M., 1968, 488 pp. (in Russ.)

[2] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Polyhedrons, graphs, optimization, Nauka Publ., M., 1981, 344 pp. (in Russ.)

[3] Schrijver A., Theory of Linear and Integer Programming, Wiley, New York, 1986, 471 pp. | DOI | MR | Zbl

[4] Ziegler G. M., Lectures on Polytopes, Graduate Texts in Mathematics, 152, Springer-Verlag, Berlin–New York, 1995, 373 pp. | DOI | MR | Zbl

[5] Motzkin T. S., Raiffa H., Thompson G. L., Trall R. M., “The Double Description Method”, Contributions to the Theory of Games, v. 2, Princeton University Press, 1953, 51–74 | DOI

[6] Chernikova N. V., “Algorithm for finding a general formula for the non-negative solutions of a system of linear inequalities”, USSR Computational Mathematics and Mathematical Physics, 5:2 (1965), 228–233 | DOI | MR

[7] D. Avis, K. Fukuda, “A Pivoting Algorithm for Convex Hull and Vertex Enumeration of Arrangements and Polyhedra”, Discrete and Computational Geometry, 8:3 (1992), 295–313 | DOI | MR | Zbl

[8] B. Chazelle, “An Optimal Convex Hull Algorithm in Any Fixed Dimension”, Discrete and Computational Geom., 10:4 (1993), 377–409 | DOI | MR | Zbl

[9] C. B. Barber, D. P. Dobkin, H. Huhdanpaa, “The Quickhull Algorithm for Convex Hulls”, ACM Transactions on Mathematical Software, 22:4 (1996), 469–483 | DOI | MR | Zbl

[10] D. Bremner, K. Fukuda, A. Marzetta, “Primal-Dual Methods for Vertex and Facet Enumeration”, Discrete and Computational Geometry, 20:3 (1998), 333–357 | DOI | MR | Zbl

[11] Shevchenko V. N., Gruzdev D. V., “A modification of the Fourier–Motskin algorithm for constructing a triangulation”, Diskretnyy analiz i issledovanie operatsiy, Ser. 2, 10:1 (2003), 53–64 (in Russ.)

[12] Panyukov A. V., Gorbik V. V., “The parallel simplex-method achievements for errorless solving of linear programming problems”, Bulletin of South Ural State University. Series: Mathematical Modelling, Programming Computer Software, 25(242):9 (2011), 107–118 (in Russ.) | Zbl

[13] Panyukov A. V., “The Linear Inequalities Set Representation of Minkovski's Sum for Two Polyhedrons”, Bulletin of South Ural State University. Series: Mathematical Modelling, Programming Computer Software, 40(299):14 (2012), 108–119 (in Russ.) | Zbl

[14] Panyukov A. V., Golodov V. A., “Approach to Solve the Set of Linear Algrebraic Equations with Interval Uncertainty of Data Given”, Bulletin of South Ural State University. Series: Mathematical Modelling, Programming Computer Software, 6:2 (2013), 108–119 (in Russ.)

[15] G. Amato, F. Scozzari, E. Zaffanella, “Efficient Constraint/Generator Removal from Double Description of Polyhedra”, Electronic Notes in Theoretical Computer Science, 307 (2014), 3–15 | DOI | MR | Zbl

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

[17] R. Bagnara, P.M. Hill, E. Zaffanella, “Applications of polyhedral computations to the analysis and verification of hardware and software systems”, Theoretical Computer Science, 410 (2009), 4672–4691 | DOI | MR | Zbl

[18] D. Avis, D. Bremner, R. Seidel, How Good are Convex Hull Algorithms?, Computational Geometry, 7:5–6 (1997), 265–301 | DOI | MR | Zbl

[19] E. Burger, “Über homogene lineare Ungleihungssysteme”, Zeitschrift Angewandte Math. Mehanik, 36:3–4 (1956), 135–139 | DOI | MR | Zbl

[20] K. Fukuda, A. Prodon, “Double Desription Method Revisited”, Lecture Notes in Computer Science, 1120, 1996, 91–111 | DOI | MR

[21] M. Terzer, J. Stelling, “Accelerating the Computation of Elementary Modes Using Pattern Trees”, Lecture Notes in Computer Science, 4175, 2006, 333–343 | DOI | MR

[22] Zolotykh N. Yu., “New modification of the double description method for constructing the skeleton of a polyhedral cone”, Journal of Computational mathematics and Mathematical Physics, 52:1 (2012), 146–156 | DOI | MR | Zbl

[23] Bastrakov S. I., Algorithmic issues of double description of a convex polyhedron, Cand. phys. and math. sci. diss., Nizhniy Novgorod, 2016, 100 pp. (in Russ.)

[24] D. Bremner, “Incremental Convex Hull Algorithms Are Not Output Sensitive”, Discrete and Computational Geometry, 21:1 (1999), 57–68 | DOI | MR | Zbl