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

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.