A hybrid branch-and-bound and interior-point algorithm for stochastic mixed-integer nonlinear second-order cone programming

Document Type : Original paper


1 Department of Mathematics, M'Hamed Bougara University of Boumerd├ęs, Algeria

2 The 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.


Main Subjects

[1] B. Alzalg, Decomposition-based interior point methods for stochastic quadratic second-order cone programming, Appl. Math. Comput. 249 (2014), 1–18.
[2] B. Alzalg, Homogeneous self-dual algorithms for stochastic second-order cone programming, J. Optim. Theory Appl. 163 (2014), no. 1, 148–164.
[3] B. Alzalg, Volumetric barrier decomposition algorithms for stochastic quadratic second-order cone programming, Appl. Math. Comput. 265 (2015), 494–508.
[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.
[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.
[6] B. Alzalg and H. Alioui, Applications of stochastic mixed-integer second-order cone optimization, IEEE Access 10 (2021), 3522–3547.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[18] M.T. Cezik and G. Iyengar, Cuts for mixed 0-1 conic programming, Math. Program. 104 (2005), no. 1, 179–202.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.