تعداد نشریات | 5 |
تعداد شمارهها | 108 |
تعداد مقالات | 1,228 |
تعداد مشاهده مقاله | 1,146,418 |
تعداد دریافت فایل اصل مقاله | 1,004,960 |
A hybrid branch-and-bound and interior-point algorithm for stochastic mixed-integer nonlinear second-order cone programming | ||
Communications in Combinatorics and Optimization | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 18 اسفند 1402 اصل مقاله (470.4 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2024.28898.1768 | ||
نویسندگان | ||
Hadjer Alioui1؛ Baha Alzalg* 2 | ||
1Department of Mathematics, M'Hamed Bougara University of Boumerdés, Algeria | ||
2The University of Jordan | ||
چکیده | ||
One of the chief attractions of stochastic mixed-integer second-order cone programming is its diverse applications, especially in engineering (Alzalg and Alioui, {\em IEEE Access}, 10:3522-3547, 2022). The linear and nonlinear versions of this class of optimization problems are still unsolved yet. In this paper, we develop a hybrid optimization algorithm coupling branch-and-bound and primal-dual interior-point methods for solving two-stage stochastic mixed-integer nonlinear second-order cone programming. The adopted approach uses a branch-and-bound technique to handle the integer variables and an infeasible interior-point method to solve continuous relaxations of the resulting subproblems. The proposed hybrid algorithm is also implemented to data to show its efficiency. | ||
کلیدواژهها | ||
Mixed-integer programming؛ Stochastic programming؛ Nonlinear second-order cone programming؛ Interior-point methods؛ Branch-and-bound | ||
مراجع | ||
[1] B. Alzalg, Decomposition-based interior point methods for stochastic quadratic second-order cone programming, Appl. Math. Comput. 249 (2014), 1–18. https://doi.org/10.1016/j.amc.2014.10.015 [2] B. Alzalg, Homogeneous self-dual algorithms for stochastic second-order cone programming, J. Optim. Theory Appl. 163 (2014), no. 1, 148–164. https://doi.org/10.1007/s10957-013-0428-z [3] B. Alzalg, Volumetric barrier decomposition algorithms for stochastic quadratic second-order cone programming, Appl. Math. Comput. 265 (2015), 494–508. https://doi.org/10.1016/j.amc.2015.05.014 [4] B. Alzalg, A primal-dual interior-point method based on various selections of displacement step for symmetric optimization, Comput. Optim. Appl. 72 (2019), no. 2, 363–390. https://doi.org/10.1007/s10589-018-0045-8 [5] B. Alzalg, A logarithmic barrier interior-point method based on majorant functions for second-order cone programming, Optim. Lett. 14 (2020), no. 3, 729–746. https://doi.org/10.1007/s11590-019-01404-1 [6] B. Alzalg and H. Alioui, Applications of stochastic mixed-integer second-order cone optimization, IEEE Access 10 (2021), 3522–3547. https://doi.org/10.1109/ACCESS.2021.3139915 [7] B. Alzalg and K.A. Ariyawansa, Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming, J. Math. Anal. Appl. 409 (2014), no. 2, 973–995. https://doi.org/10.1016/j.jmaa.2013.07.075 [8] B. Alzalg, K. Badarneh, and A. Ababneh, An infeasible interior-point algorithm for stochastic second-order cone optimization, J. Optim. Theory Appl. 181 (2019), no. 1, 324–346. https://doi.org/10.1007/s10957-018-1445-8 [9] A. Atamtürk and V. Narayanan, Cuts for conic mixed-integer programming, International Conference on Integer Programming and Combinatorial Optimization (M. Fischetti and D.P. Williamson, eds.), Springer, 2007, pp. 16–29.
[10] H.Y. Benson, Mixed integer nonlinear programming using interior-point methods, Optim. Methods Softw. 26 (2011), no. 6, 911–931. https://doi.org/10.1080/10556781003799303 [11] H.Y. Benson, A. Sen, D.F. Shanno, and R.J. Vanderbei, Interior-point algorithms, penalty methods and equilibrium problems, Comput. Optim. Appl. 34 (2006), no. 2, 155–182. https://doi.org/10.1007/s10589-005-3908-8 [12] H.Y. Benson and D.F. Shanno, An exact primal–dual penalty method approach to warmstarting interior-point methods for linear programming, Comput. Optim. Appl. 38 (2007), no. 3, 371–399. https://doi.org/10.1007/s10589-007-9048-6 [13] H.Y. Benson and D.F. Shanno, Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts, Comput. Optim. Appl. 40 (2008), no. 2, 143–189. https://doi.org/10.1007/s10589-007-9089-x [14] H.Y. Benson, D.F. Shanno, and R.J. Vanderbei, A comparative study of large-scale nonlinear optimization algorithms, High Performance Algorithms and Software for Nonlinear Optimization (G. Di Pillo and A. Murli, eds.), Springer, 2003, pp. 95–127. https://doi.org/10.1007/978-1-4613-0241-4_5 [15] H.Y. Benson and R.J. Vanderbei, Solving problems with semidefinite and related constraints using interior-point methods for nonlinear programming, Math. Program. 95 (2003), no. 2, 279–302. https://doi.org/10.1007/s10107-002-0350-x [16] H.Y. Benson, R.J. Vanderbei, and D.F. Shanno, Interior-point methods for nonconvex nonlinear programming: Filter methods and merit functions, Comput. Optim. Appl. 23 (2002), no. 2, 257–272. https://doi.org/10.1023/A:1020533003783 [17] C.C. Carøe and J. Tind, L-shaped decomposition of two-stage stochastic programs with integer recourse, Math. Program. 83 (1998), no. 1, 451–464. https://doi.org/10.1007/BF02680570 [18] M.T. Cezik and G. Iyengar, Cuts for mixed 0-1 conic programming, Math. Program. 104 (2005), no. 1, 179–202. https://doi.org/10.1007/s10107-005-0578-3 [19] S. Drewes and S. Ulbrich, Mixed Integer Second Order Cone Programming, Verlag Dr. Hut Germany, 2009.
[20] J. Faraut and A. Korányi, Analysis on symmetric cones, Oxford University Press, 1994.
[21] D. Gade, G. Hackebeil, S.M. Ryan, J.P. Watson, R.J.B. Wets, and D.L. Woodruff, Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs, Math. Program. 157 (2016), no. 1, 47–67. https://doi.org/10.1007/s10107-016-1000-z [22] D. Gade, S. Küjcükyavuz, and S. Sen, Decomposition algorithms with parametric gomory cuts for two-stage stochastic integer programs, Math. Program. 144 (2014), no. 1, 39–64. https://doi.org/10.1007/s10107-012-0615-y [23] P.E. Gill, W. Murray, and M.A. Saunders, User’s guide for SNOPT 5.3: A Fortran package for large-scale nonlinear programming, (1997).
[24] J. Lee and S. Leyffer, Mixed Integer Nonlinear Programming, vol. 154, Springer Science and Business Media, 2011.
[25] Y. Qi and S. Sen, The ancestral benders’ cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming, Math. Program. 161 (2017), no. 1, 193–235. https://doi.org/10.1007/s10107-016-1006-6 [26] S. Sen, Stochastic mixed-integer programming algorithms: Beyond benders’ decomposition, Wiley Encyclopedia of Operations Research and Management Science, 2010.
[27] S. Sen and J.L. Higle, The $C^3$ theorem and a $D^2$2 algorithm for large scale stochastic mixed-integer programming: Set convexification, Math. Program. 104 (2005), no. 1, 1–20. https://doi.org/10.1007/s10107-004-0566-z [28] S. Sen and H.D. Sherali, Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming, Math. Program. 106 (2006), no. 2, 203–223. https://doi.org/10.1007/s10107-005-0592-5 [29] H.D. Sherali and B.M.P. Fraticelli, A modification of benders’ decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse, J. Global Optim. 22 (2002), no. 1, 319–342. https://doi.org/10.1023/A:1013827731218 [30] R.J. Vanderbei and D.F. Shanno, An interior-point algorithm for nonconvex nonlinear programming, Comput. Optim. Appl. 13 (1999), no. 1, 231–252. https://doi.org/10.1023/A:1008677427361 [31] J.P. Vielma, S. Ahmed, and G.L. Nemhauser, A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs, INFORMS J. Comput. 20 (2008), no. 3, 438–450. https://doi.org/10.1287/ijoc.1070.0256 [32] L.A. Wolsey and G.L. Nemhauser, Integer and Combinatorial Optimization, vol. 55, John Wiley and Sons, 1999.
[33] M. Zhang and S. Kucukyavuz, Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs, SIAM J. Optim. 24 (2014), no. 4, 1933–1951. https://doi.org/10.1137/13092678X [34] G. Zhao, A lagrangian dual method with self-concordant barriers for multi-stage stochastic convex programming, Math. Program. 102 (2005), no. 1, 1–24. https://doi.org/10.1007/s10107-003-0471-x | ||
آمار تعداد مشاهده مقاله: 73 تعداد دریافت فایل اصل مقاله: 503 |