An Exact L-Shaped Decomposition Algorithm for Multi-Objective Two-Stage Stochastic Integer Programs
Keywords:
Multi-objective optimization , Integer optimization, Stochastic programming, Two-stage model, L-shaped method , Efficient solutionAbstract
This paper studies a finite-scenario multi-objective two-stage stochastic integer programming problem with fixed recourse. We propose a decomposition-based solution framework that combines L-shaped feasibility and optimality cuts with an efficient-solution generation procedure for the first-stage integer decisions. This novel exact framework effectively integrates the L-shaped decomposition method with an advanced exploration strategy for generating the complete set of Pareto-efficient solutions. Unlike existing approaches that often struggle with scalability, our methodology leverages these specialized cuts to navigate the stochastic search space while systematically identifying non-dominated integer points. The efficiency and robustness of the proposed algorithm are demonstrated through comprehensive numerical experiments on a diverse set of randomly generated instances. The results indicate that our method provides a significant improvement in computational precision and reliability compared to traditional techniques. By establishing a robust performance database, this study underscores the viability of the proposed approach for large-scale stochastic decision-making and provides a solid foundation for future research in multi-objective optimization under uncertainty.
Downloads
References
[1] M. Abbas and D. Chaabane, An algorithm for solving multiple objective integer linear programming problem, RAIRO-Operations Research 36:4 (2002), 351–364. 1
[2] M. Abbas and D. Chaabane, Optimizing a linear function over an integer efficient set, European Journal of Operational Research 174 (2006), 1140–1161. 1
[3] M. Abbas and F. Bellahcene, Cutting plane method for multiple objective stochastic integer linear programming, European Journal of Operational Research 168:3 (2006), 967–984. 1, 3.3
[4] N. Adelgren and A. Gupte, Branch-and-bound for biobjective mixed-integer linear programming, INFORMS Journal on Computing 34:2 (2022), 909–933.
[5] S. Amrouche and M. Moula¨ı, Multi-objective stochastic integer linear programming with fixed recourse, International Journal of Multicriteria Decision Making 2:4 (2012), 355–378. 1, 2.2.2, 3.4.1, 3.4.3, 3, 3.4.3, 4
[6] A. Azaron, K. Brown, S. Tarim and M. Modarres, A multi-objective stochastic programming approach for supply chain design considering risk, International Journal of Production Economics 116:1 (2008), 129–138.
[7] E. Beale, On minimizing a convex function subject to linear inequalities, Journal of the Royal Statistical Society 17:2 (1955), 173–184. 1, 2.2
[8] T. Bektas, Disjunctive programming for multiobjective discrete optimisation, INFORMS Journal on Computing 30:4 (2018), 625–633. 1
[9] F. Ben Abdelaziz, B. Aouni and R. E. Fayedh, Multi-objective stochastic programming for portfolio selection, European Journal of Operational Research 177:3 (2007), 1811–1823.
[10] F. Ben Abdelaziz, R. El Fayedh and A. Rao, A discrete stochastic goal program for portfolio selection: The case of United Arab Emirates equity market, Information Systems and Operational Research 19 (2009), 185–200. 1
[11] N. Boland, H. Charkhgard and M. Savelsbergh, The quadrant shrinking method: A simple and efficient algorithm for solving tri-objective integer programs, European Journal of Operational Research 260:3 (2017), 873–885. 1
[12] N. Boland and H. C. M. Savelsbergh, The l-shape search method for triobjective integer programming, Mathematical Programming Computation 8:2 (2016), 217–251. 1, 3.4.3
[13] D. Chaabane, Contribution to Multicriteria Optimization in Discrete Variables, PhD Thesis, Polytechnic Faculty of Mons, (2007).
[14] D. Chaabane and P. Marc, A method for optimizing over the integer efficient set, Journal of Industrial and Management Optimization 6 (2010), 811–823. 1
[15] D. Chaabane and F. Mebrek, Optimization of a linear function over the set of stochastic efficient solutions, Computational Management Science 11 (2014), 157–178. 1
[16] A. Charnes and W. W. Cooper, Deterministic equivalents for optimizing and satisficing under chance constrained, Operations Research 11 (1963), 18–39.
[17] G. B. Dantzig, Linear programming under uncertainty, Management Science 1:3–4 (1955), 173–184. 1, 2.2
[18] G. B. Dantzig, On a linear combinatorial approach to the travelling salesman problem, Operations Research 7 (1959), 58–66.
[19] G. B. Dantzig and G. Infanger, Multi-stage stochastic linear programs for portfolio optimization, Annals of Operations Research 45:1 (1993), 59–76.
[20] G. B. Dantzig and A. Madansky, On the solution of two-stage linear program under uncertainty, Proceedings of the Berkeley Symposium on Statistics and Probability 4:1 (1961), 165–176. 1, 2.2
[21] M. Ehrgott, Multicriteria Optimization, 2nd edition, Springer, Berlin, Heidelberg, (2005).
[22] J. Farkas, Theorie der einfachen Ungleichungen, Journal f¨ur die reine und angewandte Mathematik 124 (1902), 1–24. 2.2.1
[23] N. Forget, S. L. Gadegaard and L. R. Nielsen, Warm-starting lower bound set computations for branch-and-bound algorithms for multiobjective integer linear programs, European Journal of Operational Research 302:3 (2022), 909–924.
[24] G. R. Jahanshahloo, F. H. Lotfi, N. Shoja and G. Tohidi, A method for generating all efficient solutions of 0–1 multi-objective linear programming problem, Applied Mathematics and Computation 169:2 (2005), 874–886. 1, 3.1
[25] P. Kall, Stochastic Linear Programming, Springer-Verlag, Berlin, (1976).
[26] P. Kall and S. W. Wallace, Stochastic Programming, Wiley-Interscience Series in Systems and Optimization, John Wiley and Sons, Chichester, (1994). 1, 3.1
[27] R. Kasri and F. Bellahcene, A novel approach for solving stochastic problems with multiple objective functions, RAIRO-Operations Research 55 (2021), 2413–2422. 1
[28] W. K. Klein Haneveld and M. H. Van der Vlerk, Stochastic integer programming: General models and algorithms, Annals of Operations Research 85 (1999), 39–57.
[29] G. Kirlik and S. Sayın, A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems, European Journal of Operational Research 232:3 (2014), 479–488. 1
[30] A. Menni and D. Chaabane, A possibilistic optimization over an integer efficient set within a fuzzy environment, RAIRO-Operations Research 54 (2020), 1437–1452. 1
[31] T. Niknam, R. Azizipanah-Abarghooee and M. R. Narimani, An efficient scenario-based stochastic programming framework for multi-objective optimal micro-grid operation, Applied Energy 99 (2012), 455–470.
[32] M. Ozlen, B. A. Burton and C. A. MacRae, Multi-objective integer programming: An improved recursive algorithm, Journal of Optimization Theory and Applications 160 (2014), 470–482. 1
[33] A. Przybylski and X. Gandibleux, Multi-objective branch and bound, European Journal of Operational Research 260:3 (2017), 856–872. 1
[34] F. Rahmanniyay and A. J. Yu, A multi-objective stochastic programming model for project-oriented human resource management optimization, International Journal of Management Science and Engineering Management 14:4 (2018), 231–239.
[35] M. D. Santis, G. Eichfelder, J. Niebling and S. Rockt¨aschel, Solving multiobjective mixed integer convex optimization problems, SIAM Journal on Optimization 30:4 (2020), 3122–3145.
[36] R. E. Steuer, Multiple Criteria Optimization: Theory, Computation and Application, John Wiley, New York, (1986).
[37] S. Tamby and D. Vanderpooten, Enumeration of the nondominated set of multiobjective discrete optimization problems, INFORMS Journal on Computing 33:1 (2021), 72–85. 1
[38] J. Teghem and P. Kunsch, Multiobjective decision making under uncertainty: An example of power systems, in J. A. Anderson (ed.), Decision Making with Multiple Objectives, Springer-Verlag, Berlin, (1985), 95–108.
[39] J. Teghem and P. Kunsch, A survey of techniques for finding efficient solutions to multiobjective integer linear programming, Asia Pacific Journal of Operational Research 3:2 (1986), 95–108.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Abd Essamed Guettouche, Djamal Chaabane
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
