EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4279. Efficient exact recomputation of linear modifications of the constraint matrix in Linear Programming
Invited abstract in session TC-38: Modern techniques for network optimization, stream Conic Optimization: Theory, Algorithms, and Applications.
Tuesday, 12:30-14:00Room: 34 (building: 306)
Authors (first author is the speaker)
| 1. | Guillaume Derval
|
| 2. | Bardhyl Miftari
|
| SmartGrids, University of Liege | |
| 3. | Damien Ernst
|
| SmartGrids, University of Liège | |
| 4. | Quentin Louveaux
|
| Montefiore Institute, Université de Liège |
Abstract
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.
Keywords
- Programming, Linear
Status: accepted
Back to the list of papers