Generating feasible points for mixed-integer convex optimization problems by inner parallel cuts. (English) Zbl 1479.90142


90C11 Mixed integer programming
90C10 Integer programming
90C31 Sensitivity, stability, parametric optimization
90C30 Nonlinear programming
Full Text: DOI


[1] T. Achterberg and T. Berthold, Improving the feasibility pump, Discrete Optim., 4 (2007), pp. 77-86. · Zbl 1170.90443
[2] D. Azé, A survey on error bounds for lower semicontinuous functions, n Proceedings of the 2003 MODE-SMAI Conference, ESAIM Proc. 13, EDP Sci., Les Ulis, 2003, pp. 1-17. · Zbl 1037.49009
[3] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan, Mixed-integer nonlinear optimization, Acta Numer., 22 (2013), pp. 1-131. · Zbl 1291.65172
[4] T. Berthold, RENS-the optimal rounding, Math. Progam. Comput., 6 (2014), pp. 33-54. · Zbl 1304.90147
[5] T. Berthold and A. M. Gleixner, Undercover: A primal MINLP heuristic exploring a largest sub-MIP, Math. Program., 144 (2014), pp. 315-346. · Zbl 1291.90144
[6] L. T. Biegler and I. E. Grossmann, Retrospective on optimization, Comput. Chem. Eng., 28 (2004), pp. 1169-1192.
[7] P. Bonami, L. T. Biegler, A. R. Conn, G. Cornuéjols, I. E. Grossmann, C. D. Laird, J. Lee, A. Lodi, F. Margot, N. Sawaya, and A. Wächter, An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5 (2008), pp. 186-204. · Zbl 1151.90028
[8] P. Bonami, G. Cornuéjols, A. Lodi, and F. Margot, A Feasibility Pump for mixed integer nonlinear programs, Math. Program., 119 (2009), pp. 331-352. · Zbl 1163.90013
[9] P. Bonami and J. P. M. Gonçalves, Heuristics for convex mixed integer nonlinear programs, Comput. Optim. Appl., 51 (2012), pp. 729-747. · Zbl 1241.90189
[10] M. R. Bussieck, A. S. Drud, and A. Meeraus, MINLPLib-a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15 (2003), pp. 114-119. · Zbl 1238.90104
[11] COIN-OR, https://www.coin-or.org.
[12] M. A. Duran and I. E. Grossmann, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Programming, 36 (1986), pp. 307-339. · Zbl 0619.90052
[13] M. Fischetti, F. Glover, and A. Lodi, The feasibility pump, Math. Program., 104 (2005), pp. 91-104. · Zbl 1077.90039
[14] M. Fischetti and D. Salvagnin, Feasibility pump 2.0, Math. Program. Comput., 1 (2009), pp. 201-222. · Zbl 1180.90208
[15] R. Fletcher and S. Leyffer, Solving mixed integer nonlinear programs by outer approximation, Math. Programming, 66 (1994), pp. 327-349. · Zbl 0833.90088
[16] G. Gamrath, D. Anderson, K. Bestuzheva, W.-K. Chen, L. Eifler, M. Gasse, P. Gemander, A. Gleixner, L. Gottwald, K. Halbig, G. Hendel, C. Hojny, T. Koch, P. Le Bodic, S. J. Maher, F. Matter, M. Miltenberger, E. Mühmer, B. Müller, M. E. Pfetsch, F. Schlösser, F. Serrano, Y. Shinano, C. Tawfik, S. Vigerske, F. Wegscheider, D. Weninger, and J. Witzig, The SCIP Optimization Suite 7.0, Optimization Online, ZIB-Report 20-10, Zuse Institute, Berlin, Germany.
[17] E. Hansen, Global Optimization Using Interval Analysis, Marcel Dekker, New York, 1992.
[18] W. E. Hart, J.-P. Watson, and D. L. Woodruff, Pyomo: Modeling and solving mathematical programs in Python, Math. Program. Comput., 3 (2011), pp. 219-260.
[19] H. Hijazi, P. Bonami, and A. Ouorou, An outer-inner approximation for separable mixed-integer nonlinear programs, INFORMS J. Comput., 26 (2014), pp. 31-44. · Zbl 1356.90091
[20] A. J. Hoffman, On approximate solutions of systems of linear inequalities, J. Research Nat. Bur. Standards, 49 (1952), pp. 263-265.
[21] J. E. Kelley, The cutting-plane method for solving convex programs, J. Soc. Indust. Appl. Math., 8 (1960), pp. 703-712, https://doi.org/10.1137/0108053. · Zbl 0098.12104
[22] D. Klatte and G. Thiere, Error bounds for solutions of linear equations and inequalities, ZOR-Math. Methods Oper. Res., 41 (1995), pp. 191-214. · Zbl 0823.65055
[23] J. Kronqvist, D. E. Bernal, A. Lundell, and T. Westerlund, A center-cut algorithm for quickly obtaining feasible solutions and solving convex MINLP problems, Comput. Chem. Eng., 122 (2019), pp. 105-113.
[24] J. Kronqvist, A. Lundell, and T. Westerlund, The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Global Optim., 64 (2016), pp. 249-272. · Zbl 1339.90247
[25] W. Li, The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program, Linear Algebra Appl., 187 (1993), pp. 15-40. · Zbl 0809.65057
[26] W. Li, Sharp Lipschitz constants for basic optimal solutions and basic feasible solutions of linear programs, SIAM J. Control Optim., 32 (1994), pp. 140-153, https://doi.org/10.1137/S036301299222723X. · Zbl 0792.90080
[27] M. Lubin, E. Yamangil, R. Bent, and J. P. Vielma, Polyhedral approximation in mixed-integer convex optimization, Math. Program., 172 (2018), pp. 139-168. · Zbl 1401.90158
[28] O. L. Mangasarian and T. H. Shiau, Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems, SIAM J. Control Optim., 25 (1987), pp. 583-595, https://doi.org/10.1137/0325033. · Zbl 0613.90066
[29] MINLPLib, http://www.minlplib.org/instances.html.
[30] A. Neumaier, Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, 1990. · Zbl 0715.65030
[31] C. Neumann and O. Stein, Feasible rounding approaches for equality constrained mixed-integer optimization problems, Optimization, to appear, mailto:https://doi.org/10.1080/02331934.2021.1981894. · Zbl 1414.90239
[32] C. Neumann, O. Stein, and N. Sudermann-Merx, A feasible rounding approach for mixed-integer optimization problems, Comput. Optim. Appl., 72 (2019), pp. 309-337. · Zbl 1414.90239
[33] C. Neumann, O. Stein, and N. Sudermann-Merx, Granularity in nonlinear mixed-integer optimization, J. Optim. Theory Appl., 184 (2020), pp. 433-465. · Zbl 1433.90089
[34] C. Neumann, O. Stein, and N. Sudermann-Merx, Bounds on the objective value of feasible roundings, Vietnam J. Math., 48 (2020), pp. 299-313. · Zbl 1440.90032
[35] J.-S. Pang, Error bounds in mathematical programming, Math. Programming, 79 (1997), pp. 299-332. · Zbl 0887.90165
[36] S. M. Robinson, An application of error bounds for convex programming in a linear space, SIAM J. Control Optim., 13 (1975), pp. 271-273, https://doi.org/10.1137/0313015. · Zbl 0297.90072
[37] O. Stein, Error bounds for mixed integer linear optimization problems, Math. Program., 156 (2016), pp. 101-123. · Zbl 1345.90061
[38] O. Stein, Error bounds for mixed integer nonlinear optimization problems, Optim. Lett., 10 (2016), pp. 1153-1168. · Zbl 1377.90061
[39] A. Wächter and L. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), pp. 25-57. · Zbl 1134.90542
[40] T. Westerlund and F. Pettersson, An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19 (1995), pp. 131-136.
[41] C. Zalinescu, Sharp estimates for Hoffman’s constant for systems of linear inequalities and equalities, SIAM J. Optim., 14 (2003), pp. 517-533, https://doi.org/10.1137/S1052623402403505. · Zbl 1072.90028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.