Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Reverse Search for Parametric Linear Programming


C.N. Jones

IEEE Conference on Decision and Control

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.


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% No recipe for automatically generating a BibTex entry for (06)Talk
Permanent link