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

Document Type : Original paper

Authors

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

2 The University of Jordan

Abstract

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.

Keywords

Main Subjects

References

[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
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 08 March 2024

Files

Share

How to cite

Statistics