Abstract :
[en] In this work we focus on linear parametric programming, where the constraint matrix is an affine function of an external parameter lambda; the goal is to assess the impact of lambda on the objective value of the optimal solutions.
Computing the objective for multiple values of lambda is usually cumbersome and involves solving the related linear program in full multiple times.
We show that by reformulating the problem in term an optimal basis for a given lambda*, we can use an eigendecomposition and Schur’s decomposition to obtain an upper bound for the objective value for other values of lambda. Moreover, the bound is actually tight when the basis stays optimal.
Given a solution for lambda*, the bound can be computed in quadratic time (in the number of constraints) for another lambda. The range for the bound is exact can also be computed in quadratic time: this opens the way to an iterative algorithm for computing the full function, changing base each time the current one becomes invalid.
