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

Author(s):

C.N. Jones, Jan M. Maciejowski
Conference/Journal:

International Congress on Mathematical Software, Castro Urdiales, Spain, Also available as a book chapter in Lecture Notes in Computer Science, Volume 4151/2006 http://www.springerlink.com/content/gk25357585uh2p53/
Abstract:

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.

Year:

2006
Type of Publication:

(01)Article
Supervisor:

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
	  Programming}},
    booktitle={International Congress on Mathematical Software},
    pages={},
    year={2006},
    address={Castro Urdiales, Spain},
    month=sep,
    url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=2450}
}
Permanent link