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

Mohsen Mohammadi (), Monica Gentili (), Milan Hladík () and Raffaele Cerulli ()
Additional contact information
Mohsen Mohammadi: Northwestern University
Monica Gentili: University of Louisville
Milan Hladík: Charles University
Raffaele Cerulli: University of Salerno

Journal of Optimization Theory and Applications, 2023, vol. 199, issue 3, No 5, 955-992

Abstract: Abstract 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.

Keywords: Linear programming; Interval data; Outcome function; Uncertainty modeling; Heuristics; 90C05; 90C26; 90C27; 90C29; 90C30; 90C31; 90C46 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-023-02311-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:199:y:2023:i:3:d:10.1007_s10957-023-02311-3

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-023-02311-3

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().