Reverse Search for Parametric Linear Programming

This paper introduces a new enumeration technique for (multi)parametric linear programs (pLPs) based on the reverse-search paradigm. We prove that the proposed algorithm has a computational complexity that is linear in the size of the output (number of so-called critical regions) and a constant space complexity. This is an improvement over the quadratic and linear computational and space complexities of current approaches. Current implementations of the proposed approach become faster than existing methods for large problems. Extensions of this method are proposed that make the computational requirements lower than those of existing approaches in all cases, while allowing for efficient parallelisation and bounded memory usage