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.


Primal-Dual Enumeration for Multiparametric Linear Programming


C.N. Jones, Jan M. Maciejowski

International Congress on Mathematical Software, Castro Urdiales, Spain, Also available as a book chapter in Lecture Notes in Computer Science, Volume 4151/2006

Optimal control problems for constrained linear systems with a linear cost can be posed as multiparametric linear programs (pLPs) and solved explicitly offline. Several algorithms have recently been proposed in the literature that solve these pLPs in a fairly efficient manner, all of which have as a base operation the computation and removal of redundant constraints. For many problems, it is this redundancy elimination that requires the vast majority of the computation time. This paper introduces a new solution technique for multiparametric linear programs based on the primal--dual paradigm. The proposed approach reposes the problem as the vertex enumeration of a linearly transformed polytope and then simultaneously computes both its vertex and halfspace representations. Exploitation of the halfspace representation allows, for smaller problems, a very significant reduction in the number of redundancy elimination operations required, resulting in many cases in a much faster algorithm.


Type of Publication:


M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@InProceedings { JonMac:2006:IFA_2450,
    author={C.N. Jones and Jan M. Maciejowski},
    title={{Primal-Dual Enumeration for Multiparametric Linear
    booktitle={International Congress on Mathematical Software},
    address={Castro Urdiales, Spain},
Permanent link