Accelerating Fourier-Motzkin elimination using bit pattern trees

DOI10.1080/10556788.2020.1712600MaRDI QIDQ5865333zbMATH OpenOpenAlexWikidataFDO

Authors Sergei I. Bastrakov, A. V. Churkin, N. Yu. Zolotykh

Publication date 13 June 2022

Published in Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10556788.2020.1712600

zbMATH Keywords

bit pattern treeChernikov rulesconvex polyhedraFourier-Motzkin eliminationsystem of linear inequalitiesvariable elimination

Mathematics Subject Classification ID

Linear equations (linear algebraic aspects) (15A06) Linear inequalities of matrices (15A39) (n)-dimensional polytopes (52B11) Iterative numerical methods for linear systems (65F10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Fast method for verifying Chernikov rules in Fourier-Motzkin elimination
• Combinatorial properties of Fourier-Motzkin elimination
• Integration over a Polyhedron: An Application of the Fourier-Motzkin Elimination Method
• scientific article; zbMATH DE number 1507955
• Solution of parametrized linear inequalities by Fourier elimination and its applications

Cites work

• Applications of polyhedral computations to the analysis and verification of hardware and software systems
• DC programming: overview.
• Efficient constraint/generator removal from double description of polyhedra
• Exploring the dynamic Buchberger algorithm
• Fast method for verifying Chernikov rules in Fourier-Motzkin elimination
• Geometry of cuts and metrics
• How good are convex hull algorithms?
• scientific article; zbMATH DE number 437556 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3182476 (Why is no real title available?)
• scientific article; zbMATH DE number 3078984 (Why is no real title available?)
• Introduction to global optimization
• Multidimensional binary search trees used for associative searching
• New modification of the double description method for constructing the skeleton of a polyhedral cone
• The convolution of finite systems of linear inequalities
• Two variations of graph test in double description method

Cited in

(5)

• How to find the convex hull of all integer points in a polyhedron?
• Fast method for verifying Chernikov rules in Fourier-Motzkin elimination
• Combinatorial properties of Fourier-Motzkin elimination
• Integration over a Polyhedron: An Application of the Fourier-Motzkin Elimination Method
• A novel linear optimization presolve technique based on Fourier-Motzkin elimination

Describes a project that uses

Uses Software

• PORTA
• qskeleton
• efmtool
• addibit
• GitHub

This page was built for publication: Accelerating Fourier-Motzkin elimination using bit pattern trees

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