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

Published in:
Proceedings of the 45th IEEE Conference on Decision and Control, 1504-1509
Presented at:
45th IEEE Conference on Decision and Control, San Diego, CA, USA, 13-15 December 2006

Note: The status of this file is: EPFL only

 Record created 2011-10-24, last modified 2018-01-28

Rate this document:

Rate this document:
(Not yet reviewed)