We propose a new elimination method for linear and quadratic optimization involving parametric coefficients. In comparison to the classical Fourier-Motzkin method that is of doubly exponential worst-case complexity our method is singly exponential in the worst case. Moreover it applies also to minimization of a quadratic objective functions with arbitrary parametric coefficients. Examples confirm the superiority of the method over Fourier-Motzkin and its applicability to problems of interesting size.
Ulrike Peiker, Martin Griebl