Accelerating Fourier–Motzkin elimination using bit pattern trees. (3rd September 2021)

• Record Type: Journal Article
• Authors: Bastrakov, S. I.; Churkin, A. V.; Zolotykh, N. Yu.
• Is Part Of: Optimization methods and software. Volume 36:Number 5(2021)
• Page Start: 1082
• Page End: 1095
• Publication Date: 2021-09-03
• Subjects: Convex polyhedra -- system of linear inequalities -- variable elimination -- Fourier–Motzkin elimination -- Chernikov rules -- bit pattern tree; 15A39 -- 52B11 -- 68U05; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1712600
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : The paper concerns the elimination of a set of variables from a system of linear inequalities. We employ the widely used Fourier–Motzkin elimination method extended with the Chernikov rules. A straightforward implementation of the algorithm results in extensive enumeration during the most computationally demanding stage. We propose a new way of checking Chernikov rules using bit pattern trees as an accelerating data structure to avoid extensive enumeration. The bit pattern tree is a data structure based on k -d tree used to accelerate the double description method. First we describe an adaptation of that approach to check the second Chernikov rule in Fourier–Motzkin elimination. We also propose a new algorithm that employs bit pattern trees to accelerate both Chernikov rules. Presented results of computational evaluation prove competitiveness of the proposed algorithms.