Abstract
In this paper, we present a new method for finding robust solutions to mixed-integer linear programs subject to uncertain events. We present a new modeling framework for such events that result in uncertainty sets that depend parametrically on the decision taken. We also develop results that can be used to compute corresponding robust solutions. The usefulness of our proposed approach is illustrated by applying it in the context of a scheduling problem. For instance, we address uncertainty on the start times chosen for the tasks or on which unit they are to be executed. Delays and unit outages are possible causes for such events and can be very common in practice. Through our approach, we can accommodate them without altering the remainder of the schedule. We also allow for the inclusion of recourse on the continuous part of the problem, that is, we allow for the revision of some of the decisions once uncertainty is observed. This allows one to increase the performance of the robust solutions. The proposed scheme is also computationally favorable since the robust optimization problem to be solved remains a mixed-integer linear program, and the number of integer variables is not increased with respect to the nominal formulation. We finally apply the method to a concrete batch scheduling problem and discuss the effects of robustification in this case.
Similar content being viewed by others
References
Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769–805 (1998)
Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2009)
Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53, 464 (2011)
Pflug, G.C.: On-line optimization of simulated Markovian processes. Math. Oper. Res. 15(3), 381–395 (1990)
Goel, V., Grossmann, I.E.: A class of stochastic programs with decision dependent uncertainty. Math. Program. 108(2–3), 355–394 (2006)
Soyster, A.L.: Technical note—convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5), 1154–1157 (1973)
Thuente, D.J.: Technical note—duality theory for generalized linear programs with computational methods. Oper. Res. 28(4), 1005–1011 (1980)
Li, Z., Ding, R., Floudas, C.A.: A comparative theoretical and computational study on robust counterpart optimization: I. robust linear optimization and robust mixed integer linear optimization. Ind. Eng. Chem. Res. 50(18), 10567–10603 (2011)
Li, Z., Tang, Q., Floudas, C.A.: A comparative theoretical and computational study on robust counterpart optimization: II. probabilistic guarantees on constraint satisfaction. Ind. Eng. Chem. Res. 51(19), 6769–6788 (2012)
Li, Z., Floudas, C.A.: A comparative theoretical and computational study on robust counterpart optimization: III. improving the quality of robust solutions. Ind. Eng. Chem. Res. 53(33), 13112–13124 (2014)
El Ghaoui, L., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18(4), 1035–1064 (1997)
Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35–53 (2004)
Kuhn, D., Wiesemann, W., Georghiou, A.: Primal and dual linear decision rules in stochastic and robust optimization. Math. Program. 130(1), 177–209 (2011)
Bertsimas, D., Georghiou, A.: Design of near optimal decision rules in multistage adaptive mixed-integer optimization. Oper. Res. 63(3), 610–627 (2015)
Georghiou, A., Wiesemann, W., Kuhn, D.: Generalized decision rule approximations for stochastic programming via liftings. Math. Program. 152, 1–38 (2010)
Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Program. 99(2), 351–376 (2004)
Guslitser, E.: Uncertainty-immunized solutions in linear programming. Master’s thesis, Minerva Optimization Center, Technion (2002)
Goulart, P.J., Kerrigan, E.C., Maciejowski, J.M.: Optimization over state feedback policies for robust control with constraints. Automatica 42(4), 523–533 (2006)
Zhang, Q., Grossmann, I.E., Heuberger, C.F., Sundaramoorthy, A., Pinto, J.M.: Air separation with cryogenic energy storage: optimal scheduling considering electric energy and reserve markets. AIChE J. 61(5), 1547–1558 (2015)
Lin, X., Janak, S.L., Floudas, C.A.: A new robust optimization approach for scheduling under uncertainty: I. bounded uncertainty. Comput. Chem. Eng. 28(6), 1069–1085 (2004)
Janak, S.L., Lin, X., Floudas, C.A.: A new robust optimization approach for scheduling under uncertainty: II. uncertainty with known probability distribution. Comput. Chem. Eng. 31(3), 171–195 (2007)
Vin, J.P., Ierapetritou, M.G.: Robust short-term scheduling of multiproduct batch plants under demand uncertainty. Ind. Eng. Chem. Res. 40(21), 4543–4554 (2001)
Jia, Z., Ierapetritou, M.G.: Generate pareto optimal solutions of scheduling problems using normal boundary intersection technique. Comput. Chem. Eng. 31(4), 268–280 (2007)
Cott, B., Macchietto, S.: Minimizing the effects of batch process variability using online schedule modification. Comput. Chem. Eng. 13(1), 105–113 (1989)
Rodrigues, M., Gimeno, L., Passos, C., Campos, M.: Reactive scheduling approach for multipurpose chemical batch plants. Comput. Chem. Eng. 20, 1215–1220 (1996)
Méndez, C.A., Cerdá, J.: Dynamic scheduling in multiproduct batch plants. Comput. Chem. Eng. 27(8), 1247–1259 (2003)
Mendez, C.A., Cerdá, J.: An MILP framework for batch reactive scheduling with limited discrete resources. Comput. Chem. Eng. 28(6), 1059–1068 (2004)
Vin, J.P., Ierapetritou, M.G.: A new approach for efficient rescheduling of multiproduct batch plants. Ind. Eng. Chem. Res. 39(11), 4228–4238 (2000)
Ruiz, D., Cantón, J., Nougués, J.M., Espuña, A., Puigjaner, L.: On-line fault diagnosis system support for reactive scheduling in multipurpose batch chemical plants. Comput. Chem. Eng. 25(4), 829–837 (2001)
Kanakamedala, K.B., Reklaitis, G.V., Venkatasubramanian, V.: Reactive schedule modification in multipurpose batch chemical plants. Ind. Eng. Chem. Res. 33(1), 77–90 (1994)
Janak, S.L., Floudas, C.A., Kallrath, J., Vormbrock, N.: Production scheduling of a large-scale industrial batch plant. II. Reactive scheduling. Ind. Eng. Chem. Res. 45(25), 8253–8269 (2006)
Tarhan, B., Grossmann, I.E., Goel, V.: Stochastic programming approach for the planning of offshore oil or gas field infrastructure under decision-dependent uncertainty. Ind. Eng. Chem. Res. 48(6), 3078–3097 (2009)
Vujanic, R., Schmitt, M., Warrington, J., Morari, M.: Extending affine control policies to hybrid systems: robust control of a DC–DC buck converter. In: European Control Conference, pp. 1523–1528 (2013)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Rockafellar, R.T.: Convex analysis. In: Princeton Landmarks in Mathematics. Princeton University Press, Princeton (1997). Reprint of the 1970 original, Princeton Paperbacks
Vujanic, R., Mariéthoz, S., Goulart, P., Morari, M.: Robust integer optimization and scheduling problems for large electricity consumers. In: American Control Conference, pp. 3108–3113 (2012)
Kondili, E., Pantelides, C., Sargent, R.: A general algorithm for short-term scheduling of batch operations—I. MILP formulation. Comput. Chem. Eng. 17(2), 211–227 (1993)
Biegler, L.T., Grossmann, I.E., Westerberg, A.W., Kravanja, Z.: Systematic Methods of Chemical Process Design, vol. 796. Prentice Hall PTR, Upper Saddle River (1997)
Diamond, S., Chu, E., Boyd, S.: CVXPY: A Python-embedded modeling language for convex optimization, version 0.2. http://cvxpy.org/ (2014)
Gurobi: Constrained optimization software. http://www.gurobi.com/ (2014)
Acknowledgments
The authors are thankful to Peyman Mohajerin Esfahani from EPFL, who helped integrating recourse in our approach, as well as to Qi Zhang from Carnegie Mellon University, for his early feedback on our manuscript. This research was supported by the Swiss National Science Foundation grant P2EZP2 159089.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Christodoulos Floudas.
Rights and permissions
About this article
Cite this article
Vujanic, R., Goulart, P. & Morari, M. Robust Optimization of Schedules Affected by Uncertain Events. J Optim Theory Appl 171, 1033–1054 (2016). https://doi.org/10.1007/s10957-016-0920-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-016-0920-3