An Efficient Parametric Linear Programming Solver and Application to Polyhedral Projection

DOI10.1007/978-3-030-32304-2_11MaRDI QIDQ6329663zbMATH OpenOpenAlexFDO

Authors Hang Yu, David Monniaux

Publication date 18 November 2019

Full work available at URL https://doi.org/10.1007/978-3-030-32304-2_11

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Specification and verification (program logics, model checking, etc.) (68Q60) Linear programming (90C05)

Abstract: Polyhedral projection is a main operation of the polyhedron abstract domain.It can be computed via parametric linear programming (PLP), which is more efficient than the classic Fourier-Motzkin elimination method.In prior work, PLP was done in arbitrary precision rational arithmetic.In this paper, we present an approach where most of the computation is performed in floating-point arithmetic, then exact rational results are reconstructed.We also propose a workaround for a difficulty that plagued previous attempts at using PLP for computations on polyhedra: in general the linear programming problems are degenerate, resulting in redundant computations and geometric descriptions.

Recommendations

• On polyhedral projection and parametric programming
• Scalable Minimizing-Operators on Polyhedra via Parametric Linear Programming
• Static Analysis
• Compiler Construction
• The polyhedral projection problem

This page was built for publication: An Efficient Parametric Linear Programming Solver and Application to Polyhedral Projection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6329663)