Improving efficiency in variable elimination for optimization problems
Accelerating Fourier--Motzkin elimination: redundancy removal and the choice of variable elimination order
Computational Complexity
Summary
Eliminating variables one by one to simplify systems of inequalities can become very complicated and slow because the number of intermediate inequalities can explode. The authors studied how to remove unnecessary inequalities efficiently and how to decide the best order to eliminate variables. They found that combining two different methods for removing redundancies can work well if done carefully. They also proposed a new strategy for choosing the elimination order that can drastically reduce the time needed and keep the problem manageable, especially for complex cases involving many inequalities and variables.
Fourier-Motzkin eliminationpolyhedron projectioninequality systemsredundancy removalvariable elimination orderlinear programmingentropic constraintscausal structurescomputational optimizationpolytope
Authors
Shashaank Khanna
Abstract
Fourier-Motzkin elimination computes an inequality description of the projection of a polyhedron onto a subset of its coordinates by eliminating one variable at a time. It is used in several areas of optimisation and computer science, and it is a standard way of obtaining the entropic constraints of a causal structure, where the marginalisation over the latent variables produces such a projection. Its limitation is the growth of the intermediate systems of inequalities, which can be doubly exponential in the number of eliminated variables even though the projection itself grows only as a single exponential. In practice the computational overload of the method therefore depends on two choices: how the redundant inequalities are removed after each step, and the order in which the variables are eliminated. We consider both. We first show, by an explicit example, that Imbert's redundancy test cannot be interleaved with redundancy removal by linear programming. We show that the two methods, however, can be combined soundly if the derivation records used by Imbert's test are re-initialised after every step at which linear programming is used. We then propose a rule for choosing the elimination order of the variables that gives a significant computational advantage, however, at the cost of increased resource usage. We demonstrate this advantage on some random polytopes, where the rule reduces the running time by factors of between 6 and 25 compared with the same elimination under a fixed order. For entropic descriptions of causal structures, with more than 250 inequalities and more than 100 variables to eliminate, our rule keeps the number of inequalities handled at each step one to two orders of magnitude lower than a fixed order.