×

zbMATH — the first resource for mathematics

Efficient constraint/generator removal from double description of polyhedra. (English) Zbl 1337.68262
Simon, Axel (ed.) et al., Proceedings of the 5th international workshop on numerical and symbolic abstract domains, NSAD 2014, Munich, Germany, September 10, 2014. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 307, 3-15, electronic only (2014).
Summary: We present an algorithm for the removal of constraints (resp., generators) from a convex polyhedron represented in the double description framework. Instead of recomputing the dual representation from scratch, the new algorithm tries to better exploit the information available in the double description pair, so as to capitalize on the computational work already done. A preliminary experimental evaluation shows that significant efficiency improvements can be obtained. In particular, a combined algorithm can be defined that dynamically selects whether or not to apply the new algorithm, based on suitable profitability heuristics.
For the entire collection see [Zbl 1310.68020].

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
52B55 Computational aspects related to convexity
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
Software:
HyTech; PHAVer; PPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amato, G.; Scozzari, F., Localizing widening and narrowing, (Logozzo, F.; Fahndrich, M., Static Analysis, 20th International Symposium, SAS 2013, Lecture Notes in Computer Science, vol. 7936, (2013)), 25-42
[2] Apinis, K.; Seidl, H.; Vojdani, V., How to combine widening and narrowing for non-monotonic systems of equations, (Bohem, H.-J.; Flanagan, C., Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, (2013)), 377-386
[3] Bachem, A.; Groötschel, M., Characterization of adjacency of faces of polyhedra, Mathematical Programming Study, 14, 1-22, (1981) · Zbl 0449.90069
[4] Bagnara, R.; Hill, P. M.; Ricci, E.; Zaffanella, E., Precise widening operators for convex polyhedra, Science of Computer Programming, 58, 28-56, (2005) · Zbl 1088.68173
[5] Bagnara, R.; Hill, P. M.; Zaffanella, E., Not necessarily closed convex polyhedra and the double description method, Formal Aspects of Computing, 17, 222-257, (2005) · Zbl 1101.68674
[6] Bagnara, R.; Hill, P. M.; Zaffanella, E., The parma polyhedra library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems, Science of Computer Programming, 72, 3-21, (2008)
[7] Bagnara, R.; Hill, P. M.; Zaffanella, E., Applications of polyhedral computations to the analysis and verification of hardware and software systems, Theoretical Computer Science, 410, 4672-4691, (2009) · Zbl 1187.68311
[8] Chernikova, N. V., Algorithm for finding a general formula for the non-negative solutions of system of linear equations, U.S.S.R. Computational Mathematics and Mathematical Physics, 4, 151-158, (1964) · Zbl 0221.65055
[9] Chernikova, N. V., Algorithm for finding a general formula for the non-negative solutions of system of linear inequalities, U.S.S.R. Computational Mathematics and Mathematical Physics, 5, 228-233, (1965) · Zbl 0171.35701
[10] Chernikova, N. V., Algorithm for discovering the set of all solutions of a linear programming problem, U.S.S.R. Computational Mathematics and Mathematical Physics, 8, 282-293, (1968) · Zbl 0218.90030
[11] Cousot, P.; Halbwachs, N., 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
[12] Frehse, G., Phaver: algorithmic verification of hybrid systems past hytech, (Morari, M.; Thiele, L., Hybrid Systems: Computation and Control: Proceedings of the 8th International Workshop (HSCC 2005), Lecture Notes in Computer Science, vol. 3414, (2005)), 258-273 · Zbl 1078.93533
[13] Fukuda, K.; Prodon, A., Double description method revisited, (Deza, M.; Euler, R.; Manoussakis, Y., Combinatorics and Computer Science, 8th Franco-Japanese and 4th Franco-Chinese Conference, Brest, France, July 3-5, 1995, Selected Papers, Lecture Notes in Computer Science, vol. 1120, (1996)), 91-111
[14] Halbwachs, N., Détermination automatique de relations linéaires Vérifiées par LES variables d’un programme, (1979), Université scientifique et médicale de Grenoble Grenoble, France, Thèse de 3ème cycle d’informatique
[15] Le Verge, H., A note on Chernikova’s algorithm, publication interne 635, IRISA, (1992), Campus de Beaulieu Rennes, France
[16] Miné, A., Inferring sufficient conditions with backward polyhedral under-approximations, (Proceedings of the 4th International Workshop on Numerical and Symbolic Abstract Domains (NSAD’12), Electronic Notes in Theoretical Computer Science (ENTCS), vol. 287, (2012)), 89-100 · Zbl 1294.68062
[17] Motzkin, T. S.; Raiffa, H.; Thompson, G. L.; Thrall, R. M., The double description method, (Kuhn, H. W.; Tucker, A. W., Contributions to the Theory of Games - Volume II, Annals of Mathematics Studies, vol. number 28, (1953), Princeton University Press Princeton, New Jersey), 51-73 · Zbl 0050.14201
[18] Stoer, J.; Witzgall, C., Convexity and optimization in finite dimensions I, (1970), Springer-Verlag Berlin · Zbl 0203.52203
[19] Zolotykh, N. Y., New modification of the double description method for constructing the skeleton of a polyhedral cone, Computational Mathematics and Mathematical Physics, 52, 146-156, (2012) · Zbl 1249.52017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.