Adjustable robust optimization through multi-parametric programming. (English) Zbl 1444.90087
Summary: Adjustable robust optimization (ARO) involves recourse decisions (i.e. reactive actions after the realization of the uncertainty, ‘wait-and-see’) as functions of the uncertainty, typically posed in a two-stage stochastic setting. Solving the general ARO problems is challenging, therefore ways to reduce the computational effort have been proposed, with the most popular being the affine decision rules, where ‘wait-and-see’ decisions are approximated as affine adjustments of the uncertainty. In this work we propose a novel method for the derivation of generalized affine decision rules for linear mixed-integer ARO problems through multi-parametric programming, that leads to the exact and global solution of the ARO problem. The problem is treated as a multi-level programming problem and it is then solved using a novel algorithm for the exact and global solution of multi-level mixed-integer linear programming problems. The main idea behind the proposed approach is to solve the lower optimization level of the ARO problem parametrically, by considering ‘here-and-now’ variables and uncertainties as parameters. This will result in a set of affine decision rules for the ‘wait-and-see’ variables as a function of ‘here-and-now’ variables and uncertainties for their entire feasible space. A set of illustrative numerical examples are provided to demonstrate the potential of the proposed novel approach.
MSC:
| 90C17 | Robustness in mathematical programming |
| 90C31 | Sensitivity, stability, parametric optimization |
References:
| [1] | Avraamidou, S.; Pistikopoulos, EN, B-pop: bi-level parametric optimization toolbox, Comput. Chem. Eng., 122, 193-202 (2019) |
| [2] | Avraamidou, S.; Pistikopoulos, EN, Multi-parametric global optimization approach for tri-level mixed-integer linear optimization problems, J. Glob. Optim. (2018) |
| [3] | Avraamidou, S.; Pistikopoulos, EN, A Multi-Parametric optimization approach for bilevel mixed-integer linear and quadratic programming problems, Comput. Chem. Eng., 122, 98-113 (2019) |
| [4] | Bard, J., An investigation of the linear three level programming problem, IEEE Trans. Syst. Man Cybern., 14, 5, 711-717 (1984) · Zbl 0552.90081 |
| [5] | Baron, O.; Milner, J.; Naseraldin, H., Facility location: a robust optimization approach, Prod. Oper. Manag., 20, 5, 772-785 (2010) |
| [6] | Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Math. Oper. Res., 23, 4, 769-805 (1998) · Zbl 0977.90052 |
| [7] | Ben-Tal, A.; Nemirovski, A., Robust solutions of uncertain linear programs, Oper. Res. Lett., 25, 1, 1-13 (1999) · Zbl 0941.90053 |
| [8] | Ben-Tal, A.; Nemirovski, A., Robust solutions of linear programming problems contaminated with uncertain data, Math. Program., 88, 3, 411-424 (2000) · Zbl 0964.90025 |
| [9] | Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Math. Program., 99, 2, 351-376 (2004) · Zbl 1089.90037 |
| [10] | Bertsimas, D.; Brown, DB, Constructing uncertainty sets for robust linear optimization, Oper. Res., 57, 6, 1483-1495 (2009) · Zbl 1228.90061 |
| [11] | Bertsimas, D., Caramanis, C.: Adaptability via sampling. In: 2007 46th IEEE Conference on Decision and Control, pp. 4717-4722 (2007) |
| [12] | Bertsimas, D.; Georghiou, A., Design of near optimal decision rules in multistage adaptive mixed-integer optimization, Oper. Res., 63, 3, 610-627 (2015) · Zbl 1327.90126 |
| [13] | Bertsimas, D.; Georghiou, A., Binary decision rules for multistage adaptive mixed-integer optimization, Math. Program., 167, 395-433 (2017) · Zbl 1391.90437 |
| [14] | Bertsimas, D.; Sim, M., The price of robustness, Oper. Res., 52, 1, 35-53 (2004) · Zbl 1165.90565 |
| [15] | Bertsimas, D.; Iancu, D.; Parrilo, P., A hierarchy of near-optimal policies for multistage adaptive optimization (technical report), IEEE Trans. Autom. Control, 56, 12, 2809(16) (2011) · Zbl 1368.93336 |
| [16] | Blair, C., The computational complexity of multi-level linear programs, Ann. Oper. Res., 34, 1, 13-19 (1992) · Zbl 0751.90046 |
| [17] | de Ruiter, FJCT; Ben-Tal, A.; Brekelmans, RCM; den Hertog, D., Robust optimization of uncertain multistage inventory systems with inexact data in decision rules, Comput. Manag. Sci., 14, 1, 45-66 (2017) · Zbl 1397.90047 |
| [18] | Dua, V.; Bozinis, NA; Pistikopoulos, EN, A multiparametric programming approach for mixed-integer quadratic engineering problems, Comput. Chem. Eng., 26, 4-5, 715-733 (2002) |
| [19] | Faisca, NP; Saraiva, PM; Rustem, B.; Pistikopoulos, EN, A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems, Comput. Manag. Sci., 6, 377-397 (2009) · Zbl 1189.90152 |
| [20] | Ghaoui, LE; Lebret, H., Robust solutions to least-squares problems with uncertain data, SIAM J. Matrix Anal. Appl., 18, 4, 1035-1064 (1997) · Zbl 0891.65039 |
| [21] | Ghaoui, LE; Oustry, F.; Lebret, H., Robust solutions to uncertain semidefinite programs, SIAM J. Optim., 9, 1, 33-52 (1998) · Zbl 0960.93007 |
| [22] | Hanasusanto, GA; Kuhn, D.; Wiesemann, W., K-adaptability in two-stage robust binary programming, Oper. Res., 63, 4, 877-891 (2015) · Zbl 1329.90164 |
| [23] | Hansen, P.; Jaumard, B.; Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM J. Sci. Stat. Comput., 13, 5, 1194-1217 (1992) · Zbl 0760.65063 |
| [24] | Lai, YJ, Hierarchical optimization: a satisfactory solution, Fuzzy Sets Syst., 77, 3, 321-335 (1996) · Zbl 0869.90042 |
| [25] | Lappas, NH; Gounaris, CE, Multi-stage adjustable robust optimization for process scheduling under uncertainty, AIChE J., 62, 5, 1646-1667 (2016) |
| [26] | Lappas, NH; Gounaris, CE, Robust optimization for decision-making under endogenous uncertainty, Comput. Chem. Eng., 111, 252-266 (2018) |
| [27] | Lappas, NH; Gounaris, CE, Theoretical and computational comparison of continuous-time process scheduling models for adjustable robust optimization, AIChE J., 64, 8, 3055-3070 (2018) |
| [28] | Ning, C.; You, F., Data-driven adaptive nested robust optimization: general modeling framework and efficient computational algorithm for decision making under uncertainty, AIChE J., 63, 9, 3790-3817 (2017) |
| [29] | Nohadani, O.; Sharma, K., Optimization under decision-dependent uncertainty, SIAM J. Optim., 28, 2, 1773-1795 (2018) · Zbl 1401.90117 |
| [30] | Oberdieck, R.; Diangelakis, N.; Nascu, I.; Papathanasiou, M.; Sun, M.; Avraamidou, S.; Pistikopoulos, E., On multi-parametric programming and its applications in process systems engineering, Chem. Eng. Res. Des., 116, 61-82 (2016) |
| [31] | Oberdieck, R.; Diangelakis, NA; Avraamidou, S.; Pistikopoulos, EN, On unbounded and binary parameters in multi-parametric programming: Applications to mixed-integer bilevel optimization and duality theory, J. Glob. Optim., 69, 3, 587-606 (2017) · Zbl 1381.90081 |
| [32] | Poss, M., Robust combinatorial optimization with variable cost uncertainty, Eur. J. Oper. Res., 237, 3, 836-845 (2014) · Zbl 1338.90353 |
| [33] | Pramanik, S.; Roy, T., Fuzzy goal programming approach to multilevel programming problems, Eur. J. Oper. Res., 176, 2, 1151-1166 (2007) · Zbl 1110.90084 |
| [34] | Sakawa, M.; Matsui, T., Interactive fuzzy stochastic multi-level 0-1 programming using tabu search and probability maximization, Expert Syst. Appl., 41, 6, 2957-2963 (2014) |
| [35] | Sakawa, M.; Nishizaki, I.; Uemura, Y., Interactive fuzzy programming for multilevel linear programming problems, Comput. Math. Appl., 36, 2, 71-86 (1998) · Zbl 0937.90123 |
| [36] | Sakawa, M.; Nishizaki, I.; Hitaka, M., Interactive fuzzy programming for multi-level 0-1 programming problems through genetic algorithms, Eur. J. Oper. Res., 114, 3, 580-588 (1999) · Zbl 0938.90077 |
| [37] | Shih, HS; Lai, YJ; Lee, E., Fuzzy approach for multi-level programming problems, Comput. Oper. Res., 23, 1, 73-91 (1996) · Zbl 0838.90140 |
| [38] | Sinha, S., Fuzzy mathematical programming applied to multi-level programming problems, Comput. Oper. Res., 30, 9, 1259-1268 (2003) · Zbl 1036.90077 |
| [39] | Wen, UP; Bialas, W., The hybrid algorithm for solving the three-level linear programming problem, Comput. Oper. Res., 13, 4, 367-377 (1986) · Zbl 0643.90058 |
| [40] | White, D., Penalty function approach to linear trilevel programming, J. Optim. Theory Appl., 93, 1, 183-197 (1997) · Zbl 0898.90089 |
| [41] | Zeng, B.; Zhao, L., Solving two-stage robust optimization problems using a column-and-constraint generation method, Oper. Res. Lett., 41, 457-461 (2013) · Zbl 1286.90143 |
| [42] | Zhao, L., Zeng, B.: Robust unit commitment problem with demand response and wind energy. In: 2012 IEEE Power and Energy Society General Meeting, pp. 1-8 (2012) |
| [43] | Zhen, J.; den Hertog, D.; Sim, M., Adjustable robust optimization via Fourier-Motzkin elimination, Oper. Res., 66, 4, 1086-1100 (2018) · Zbl 1455.90124 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
