EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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:00
Room: 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

Status: accepted


Back to the list of papers