Un solveur de programmation linéaire paramétrique efficace et une application à la projection polyédrique.

Résumé La projection polyédrique est une opération principale du domaine abstrait des polyèdres. Elle peut être calculée par programmation linéaire paramétrique (PLP), qui est plus efficace que la méthode classique d'élimination de Fourier-Motzkin. Dans les travaux antérieurs, la PLP était effectuée en arithmétique rationnelle de précision arbitraire. Dans cet article, nous présentons une approche où la plupart des calculs sont effectués en arithmétique à virgule flottante, puis les résultats rationnels exacts sont reconstruits. Nous proposons également une solution à une difficulté qui a entravé les tentatives précédentes d'utilisation de la PLP pour les calculs sur les polyèdres : en général, les problèmes de programmation linéaire sont dégénérés, ce qui entraîne des calculs et des descriptions géométriques redondants.