Accelerating Fourier–Motzkin elimination using bit pattern trees
Sergei I. Bastrakov, A. V. Churkin, Nikolai Yu. Zolotykh · Optimization methods & software · 2020
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.