Skip to main content
Top

2017 | OriginalPaper | Chapter

Efficient Elimination of Redundancies in Polyhedra by Raytracing

Authors : Alexandre Maréchal, Michaël Périn

Published in: Verification, Model Checking, and Abstract Interpretation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A polyhedron can be represented as constraints, generators or both in the double description framework. Whatever the representation, most polyhedral operators spend a significant amount of time to maintain minimal representations. To minimize a polyhedron in constraints-only representation, the redundancy of each constraint must be checked with respect to others by solving a linear programming (lp) problem. We present an algorithm that replaces most lp problem resolutions by distance computations. It consists in launching rays starting from a point within the polyhedron and orthogonal to its bounding hyperplanes. A face first encountered by one of these rays is an irredundant constraint of the polyhedron. Since this procedure is incomplete, lp problem resolutions are required for the remaining undetermined constraints. Experiments show that our algorithm drastically reduces the number of calls to the simplex, resulting in a considerable speed improvement. To follow the geometric interpretation, the algorithm is explained in terms of constraints but it can also be used to minimize generators.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
We only deal with convex polyhedra. For readability, we will omit the adjective convex in the following.
 
2
Conversely, simplex \(\left( \exists \varvec{w}, \left\langle \varvec{\varvec{C_{}}'},\varvec{\varvec{w}}\right\rangle >0 \bigwedge _i \left\langle \varvec{\varvec{C_{i}}},\varvec{\varvec{w}}\right\rangle \le 0 \right) \) returns either \(\textsc {success} (\varvec{w})\) or \(\textsc {failure} (\varvec{\lambda })\) such that \( \varvec{C_{}}' = \sum _i \lambda _i \varvec{C_{i}}\).
 
3
As this property is a pure technicality it is not given here but is available in [15].
 
4
What is needed from the floating point solution is the set of basic variables and an ordering of the nonnull \(\lambda _i\) coefficients to speed up the search in exact simplex.
 
6
The opposite phenomena (2n vertices corresponding to \(2^n\) constraints) also exists but hardly ever occurs in practice [3].
 
Literature
1.
go back to reference Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd edn. Society for Industrial and Applied Mathematics, Philadelphia (1999)CrossRefMATH Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd edn. Society for Industrial and Applied Mathematics, Philadelphia (1999)CrossRefMATH
2.
go back to reference 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), 4672–4691 (2009)MathSciNetCrossRefMATH 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), 4672–4691 (2009)MathSciNetCrossRefMATH
3.
go back to reference Benoy, F., King, A., Mesnard, F.: Computing convex hulls with a linear solver. TPLP: Theory Pract. Log. Program. 5(1–2), 259–271 (2005)MATH Benoy, F., King, A., Mesnard, F.: Computing convex hulls with a linear solver. TPLP: Theory Pract. Log. Program. 5(1–2), 259–271 (2005)MATH
4.
go back to reference Chernikova, N.V.: Algorithm for discovering the set of all the solutions of a linear programming problem. USSR Comput. Math. Math. Phys. 8, 282–293 (1968)CrossRefMATH Chernikova, N.V.: Algorithm for discovering the set of all the solutions of a linear programming problem. USSR Comput. Math. Math. Phys. 8, 282–293 (1968)CrossRefMATH
5.
go back to reference Chvatal, V.: Linear Programming. Series of Books in the Mathematical Sciences. W. H. Freeman, New York (1983)MATH Chvatal, V.: Linear Programming. Series of Books in the Mathematical Sciences. W. H. Freeman, New York (1983)MATH
6.
go back to reference Feautrier, P., Lengauer, C.: Polyhedron model. In: Padua, D. (ed.) Encyclopedia of Parallel Computing, vol. 1, pp. 1581–1592. Springer, Berlin (2011) Feautrier, P., Lengauer, C.: Polyhedron model. In: Padua, D. (ed.) Encyclopedia of Parallel Computing, vol. 1, pp. 1581–1592. Springer, Berlin (2011)
7.
go back to reference Fouilhé, A., Monniaux, D., Périn, M.: Efficient certificate generation for the abstract domain of polyhedra. In: Static Analysis Symposium (2013) Fouilhé, A., Monniaux, D., Périn, M.: Efficient certificate generation for the abstract domain of polyhedra. In: Static Analysis Symposium (2013)
8.
9.
go back to reference Goldman, A.J., Tucker, A.W.: Polyhedral convex cones. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems. Annals of Mathematics Studies, vol. 38, pp. 19–40. Princeton University Press, Princeton (1956) Goldman, A.J., Tucker, A.W.: Polyhedral convex cones. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems. Annals of Mathematics Studies, vol. 38, pp. 19–40. Princeton University Press, Princeton (1956)
10.
go back to reference Halbwachs, N.: Détermination automatique de relations linéaires vérifiées par les variables d’un programme. Ph.D. thesis, Université scientifique et médicale de Grenoble, (in French) (1979) Halbwachs, N.: Détermination automatique de relations linéaires vérifiées par les variables d’un programme. Ph.D. thesis, Université scientifique et médicale de Grenoble, (in French) (1979)
11.
12.
go back to reference Jourdan, J.-H., Laporte, V., Blazy, S., Leroy, X., Pichardie, D.: A formally-verified C static analyzer. In: ACM Principles of Programming Languages (POPL), pp. 247–259. ACM Press, January 2015 Jourdan, J.-H., Laporte, V., Blazy, S., Leroy, X., Pichardie, D.: A formally-verified C static analyzer. In: ACM Principles of Programming Languages (POPL), pp. 247–259. ACM Press, January 2015
13.
go back to reference Lassez, J.-L., Huynh, T., McAloon, K.: Simplification and elimination of redundant linear arithmetic constraints. In: Constraint Logic Programming, pp. 73–87. MIT Press, Cambridge (1993) Lassez, J.-L., Huynh, T., McAloon, K.: Simplification and elimination of redundant linear arithmetic constraints. In: Constraint Logic Programming, pp. 73–87. MIT Press, Cambridge (1993)
14.
go back to reference Le Verge, H.: A note on Chernikova’s algorithm. Research report RR-1662, INRIA (1992) Le Verge, H.: A note on Chernikova’s algorithm. Research report RR-1662, INRIA (1992)
15.
go back to reference Maréchal, A., Périn, M.: Efficient elimination of redundancies in polyhedra using raytracing. Technical report TR-2016-6, Verimag, Université Grenoble-Alpes, October 2016 Maréchal, A., Périn, M.: Efficient elimination of redundancies in polyhedra using raytracing. Technical report TR-2016-6, Verimag, Université Grenoble-Alpes, October 2016
16.
go back to reference Motzkin, T.S., Raiffa, H., Thompson, G.L., Thrall, R.M.: The double description method. In: Contributions to the Theory of Games. Annals of Mathematics Studies, vol. 2, pp. 51–73. Princeton University Press, Princeton (1953) Motzkin, T.S., Raiffa, H., Thompson, G.L., Thrall, R.M.: The double description method. In: Contributions to the Theory of Games. Annals of Mathematics Studies, vol. 2, pp. 51–73. Princeton University Press, Princeton (1953)
17.
go back to reference Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Hoboken (1999)MATH Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Hoboken (1999)MATH
18.
go back to reference Simon, A., King, A.: Exploiting sparsity in polyhedral analysis. In: Hankin, C., Siveroni, I. (eds.) SAS 2005. LNCS, vol. 3672, pp. 336–351. Springer, Heidelberg (2005). doi:10.1007/11547662_23 CrossRef Simon, A., King, A.: Exploiting sparsity in polyhedral analysis. In: Hankin, C., Siveroni, I. (eds.) SAS 2005. LNCS, vol. 3672, pp. 336–351. Springer, Heidelberg (2005). doi:10.​1007/​11547662_​23 CrossRef
19.
go back to reference Wilde, D.K.: A library for NG polyhedral operations. Master’s thesis, Oregon State University, Corvallis, Oregon, December 1993. Also Published as IRISA Technical report PI 785, Rennes, France (1993) Wilde, D.K.: A library for NG polyhedral operations. Master’s thesis, Oregon State University, Corvallis, Oregon, December 1993. Also Published as IRISA Technical report PI 785, Rennes, France (1993)
20.
go back to reference Zolotykh, N.Y.: New modification of the double description method for constructing the skeleton of a polyhedral cone. Comput. Math. Math. Phys. 52(1), 146–156 (2012)MathSciNetCrossRefMATH Zolotykh, N.Y.: New modification of the double description method for constructing the skeleton of a polyhedral cone. Comput. Math. Math. Phys. 52(1), 146–156 (2012)MathSciNetCrossRefMATH
Metadata
Title
Efficient Elimination of Redundancies in Polyhedra by Raytracing
Authors
Alexandre Maréchal
Michaël Périn
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-52234-0_20

Premium Partner