EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2357. Parametric upper and lower bounds of linear variations of a linear problem’s LHS

Invited abstract in session WC-38: Advances in algorithms and applications for linear and convex optimization, stream Conic Optimization: Theory, Algorithms, and Applications.

Wednesday, 12:30-14:00
Room: 34 (building: 306)

Authors (first author is the speaker)

1. Bardhyl Miftari
SmartGrids, University of Liege
2. Guillaume Derval
University of Liège
3. Quentin Louveaux
Montefiore Institute, Université de Liège
4. Damien Ernst
SmartGrids, University of Liège

Abstract

Assessing the impact of various hypotheses is a common task when working on models. In this paper, we focus on the linear parametric problem where we assess the impact of unknown constraints’ coefficients on the final objective. These multiple coefficients can vary linearly within a known range. Traditionally, this task is tackled using heavy computation, i.e., recomputing the optimum several times for every value of the coefficients, using approximations or using non-generic approaches. For large linear problems, we argue that computing every value of the coefficients in the interval is too computationally heavy and does not provide any information about the overall behavior between the points.

As a new approach to the problem, we derive several upper and lower bounds that allow us to avoid recomputing the problem for numerous coefficient values, provide guarantees between the computed points, as it does not allow for outliers, and require a smaller number of optimizations. We discuss these bounds and provide an iterative algorithm that uses them to compute an approximation to the original function within a given error threshold. We analyze the performance of the bounds on toy and real-world problems and demonstrate the effectiveness of the approach.

Keywords

Status: accepted

Back to the list of papers