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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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&apos;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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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&apos;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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-11117S" target="_blank" >GA22-11117S: Globální analýza citlivosti a stabilita v optimalizačních úlohách</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název periodika

Journal of Optimization Theory and Applications

ISSN

0022-3239

e-ISSN

1573-2878

Svazek periodika

199

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

38

Strana od-do

955-992

Kód UT WoS článku

001099492300002

EID výsledku v databázi Scopus

2-s2.0-85176106671