Abstract
The usual formulation of a linear program is max \(c\cdot x{:}Ax \le b, x \ge 0\). The core part of this linear program is the \(A\) matrix since the columns define the variables and the rows define the constraints. The \(A\) matrix is constructed by populating columns or populating rows, or some of both, depending on the nature of the data and how it is collected. This paper addresses the construction of the \(A\) matrix and solution procedures when there are separate data sources for the columns and for the rows and, moreover, the data is uncertain. The \(A\) matrices which are “realizable” are only those which are considered possible from both sources. These realizable matrices then form an uncertainty set \(U\) for a robust linear program. We show how to formulate and solve linear programs which provide lower and upper bounds to the robust linear program defined by \(U\). We also show how to use ordinary linear programming duality to share and divide the “credit/responsibility” of the optimal value of the robust linear program between the two alternative data sources.
Similar content being viewed by others
Notes
For the row case, one specifies
$$\begin{aligned} \widehat{w_i} \left( \varepsilon \right) =w_i^*\left( \varepsilon \right) -\left( {\frac{w_i^{*} \left( \varepsilon \right) }{ w_1^*\left( \varepsilon \right) +w_2^*\left( \varepsilon \right) }} \right) \varepsilon \end{aligned}$$to find the row scale factor
$$\begin{aligned} \frac{ w_1^*\left( \varepsilon \right) }{\widehat{w_1} \left( \varepsilon \right) }= \frac{ w_2^*\left( \varepsilon \right) }{\widehat{w_2} \left( \varepsilon \right) }=\frac{1-5\varepsilon }{1-8\varepsilon }. \end{aligned}$$
References
Beck, A., Ben-Tal, A.: Duality in robust optimization: primal worst equals dual best. Oper. Res. Lett. 37(1), 1–6 (2009)
Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain programs. Oper. Res. Lett. 25(1), 1–13 (1999)
Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88(Ser A), 411–424 (2000)
Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35–53 (2004)
Bertsimas, D., Brown, D.B.: Constructing uncertainty sets for robust linear optimization. Oper. Res. 57(6), 1463–1498 (2009)
Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton, NJ (1963)
Greenberg, H.J., Murphy, F.H.: A comparison of mathematical programming modelling systems. Ann. Oper. Res. 38, 177–238 (1992)
Hibbard, W.R., Soyster, A.L., Gates, R.S.: A disaggregated supply model of the U.S. copper industry operating in an aggregated world econometric supply/demand system. Mater. Soc. 4(3), 261–284 (1980)
Luong, T., Murphy, F.H.: Modeling the impacts of the 1990 clean air act amendments. Interfaces 28(2), 1–20 (1998)
Ma, P., Murphy, F.H., Stohr, E.A.: Computer-assisted formulation of linear programs. IMA J. Manag. Math. 1(1), 147–161 (1987)
Mudrageda, M., Murphy, F.H.: An economic equilibrium model for marine transportation services in petroleum products. Oper. Res. 56(2), 278–285 (2008)
Murphy, F.H., Sanders, R., Shaw, S.H., Thrasher, R.: Modeling natural gas regulatory proposals using the project independence evaluation system. Oper. Res. 29(5), 876–902 (1981)
Murphy, F.H., Soyster, A.L.: Economic Behavior of Electric Utilities. Prentice-Hall, Englewood Cliffs (1983)
Rappaport, L.A., Soyster, A.L.: LORENDAS: A computer-based system for modeling of long range energy development and supplies. Natural Resources Forum 2(1), 19–36 (1977)
Soyster, A.L.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5), 1154–1157 (1973)
Soyster, A.L., Eynon, R.T.: The conceptual basis of the electric utility sub-model of project independence evaluation system. Appl. Math. Model. 3(4), 242–248 (1979)
Soyster, A.L., Sherali, H.D.: The influence of market structure in the supply and demand of copper. OMEGA 9(4), 381–388 (1981)
Soyster, A.L., Gordon, R.L., Enscore, E.E., We, Y.H.: An evaluation of the competitiveness of the U.S. coal market. Energy Econ. 7(1), 3–8 (1985)
Soyster, A.L., Ventura, J.A.: Linear programming. In: Avriel, M., Golany, B. (eds.) Mathematical Programming for Industrial Engineers. Marcel Dekker, New York (1996)
Soyster, A.L., Murphy, F.H.: A unifying framework for duality and modelling in robust linear programs. OMEGA 41(6), 984–997 (2013)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Soyster, A.L., Murphy, F.H. On the integration of row and column uncertainty in robust linear programming. J Glob Optim 66, 195–223 (2016). https://doi.org/10.1007/s10898-014-0240-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-014-0240-9