Quantifying Outcome Functions of Linear Programs: An Approach Based on Interval-Valued Right-Hand Sides

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10474011" target="_blank" >RIV/00216208:11320/23:10474011 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Soo1WMAMlb" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Soo1WMAMlb</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10957-023-02311-3" target="_blank" >10.1007/s10957-023-02311-3</a>

Result language
angličtina
Original language name
Quantifying Outcome Functions of Linear Programs: An Approach Based on Interval-Valued Right-Hand Sides
Original language description
This paper addresses a linear programming problem with interval right-hand sides, forming a family of linear programs associated with each realization of the interval data. The paper focuses on the outcome range problem, which seeks the range of an additional function-termed the outcome function-over all possible optimal solutions of such linear programs. We explore the problem's applicability in diverse contexts, discuss its connections to certain existing problems, and analyze its computational complexity and theoretical foundations. Given the inherent computational challenges, we propose three heuristics to solve the problem. The first heuristic employs a reformulation-linearization technique (RLT) to obtain an outer approximation of the range of the outcome function. We also present two algorithms-a gradient-restoration-based approach (GI) and a bases inspection method (BI)-for computing an inner approximation of the range. Computational experiments illustrate the competitive advantage of our proposed approaches versus off-the-shelf solvers. The GI and BI methods present promising results in finding a cheap but tight inner approximation, while the performance of the RLT technique decreases as problem size and uncertainty increase.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA22-11117S" target="_blank" >GA22-11117S: Global sensitivity analysis and stability in optimization problems</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)