×

zbMATH — the first resource for mathematics

Granularity in nonlinear mixed-integer optimization. (English) Zbl 1433.90089
Summary: We study a new technique to check the existence of feasible points for mixed-integer nonlinear optimization problems that satisfy a structural requirement called granularity. For granular optimization problems, we show how rounding the optimal points of certain purely continuous optimization problems can lead to feasible points of the original mixed-integer nonlinear problem. To this end, we generalize results for the mixed-integer linear case from [the authors, Comput. Optim. Appl. 72, No. 2, 309–337 (2019; Zbl 1414.90239)]. We study some additional issues caused by nonlinearity and show how to overcome them by extending the standard granularity concept to an advanced version, which we call pseudo-granularity. In a computational study on instances from a standard test library, we demonstrate that pseudo-granularity can be expected in many nonlinear applications from practice, and that its explicit use can be beneficial.

MSC:
90C11 Mixed integer programming
90C30 Nonlinear programming
90C10 Integer programming
90C31 Sensitivity, stability, parametric optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Neumann, C.; Stein, O.; Sudermann-Merx, N., A feasible rounding approach for mixed-integer optimization problems, Comput. Optim. Appl., 72, 309-337 (2019) · Zbl 1414.90239
[2] Danna, E.; Rothberg, E.; Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, 71-90 (2005) · Zbl 1131.90036
[3] Papadimitriou, Ch; Steiglitz, K., Combinatorial Optimization (1998), Mineola: Dover Publications, Mineola
[4] Achterberg, T.; Berthold, T., Improving the feasibility pump, Discrete Optim., 4, 77-86 (2007) · Zbl 1170.90443
[5] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program., 104, 91-104 (2005) · Zbl 1077.90039
[6] Fischetti, M.; Salvagnin, D., Feasibility pump 2.0, Math. Program. Comput., 1, 201-222 (2009) · Zbl 1180.90208
[7] Berthold, T.; Gleixner, Am, Undercover: a primal MINLP heuristic exploring a largest sub-MIP, Math. Program., 144, 315-346 (2014) · Zbl 1291.90144
[8] Berthold, T., RENS—the optimal rounding, Math. Program. Comput., 6, 33-54 (2014) · Zbl 1304.90147
[9] Bonami, P.; Gonçalves, Jpm, Heuristics for convex mixed integer nonlinear programs, Comput. Optim. Appl., 51, 729-747 (2012) · Zbl 1241.90189
[10] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131 (2013) · Zbl 1291.65172
[11] Stein, O., Error bounds for mixed integer linear optimization problems, Math. Program., 156, 101-123 (2016) · Zbl 1345.90061
[12] Stein, O., Error bounds for mixed integer nonlinear optimization problems, Optim. Lett., 10, 1153-1168 (2016) · Zbl 1377.90061
[13] Conforti, M.; Cornuéjols, G.; Zambelli, G., Integer Programming (2014), Cham: Springer, Cham · Zbl 1307.90001
[14] Grunewald, F.; Segal, D., How to Solve a Quadratic Equation in Integers. (1981), Cambridge: Cambridge University Press, Cambridge · Zbl 0471.10012
[15] Siegel, C.L.: Zur Theorie der quadratischen Formen. Nachr. Akad. Wiss. Göttingen, Math.-Phys. Klasse, 21-46 (1972) · Zbl 0252.10019
[16] Bussieck, Mr; Drud, As; Meeraus, A., MINLPLib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119 (2003) · Zbl 1238.90104
[17] Hart, We; Watson, J-P; Woodruff, Dl, Pyomo: modeling and solving mathematical programs in Python, Math. Program. Comput., 3, 219-260 (2011)
[18] Wächter, A.; Biegler, Lt, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-58 (2008) · Zbl 1134.90542
[19] COIN-OR. https://www.coin-or.org
[20] MINLPLib. http://www.minlplib.org/instances.html
[21] Bonami, P.; Biegler, Lt; Conn, Ar; Cornuéjols, G.; Grossmann, Ie; Laird, Cd; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 186-204 (2008) · Zbl 1151.90028
[22] Bonami, P., Lee, J.: Bonmin users’ manual. Technical report, September (2009)
[23] Hansen, E., Global Optimization Using Interval Analysis (1992), New York: Marcel Dekker, New York
[24] Neumaier, A., Interval Methods for Systems of Equations (1990), Cambridge: Cambridge University Press, Cambridge · Zbl 0706.15009
[25] Rockafellar, Rt, Convex Analysis (1970), Princeton: Princeton University Press, Princeton
[26] Fukushima, M.; Pang, J-S, Some feasibility issues in mathematical programs with equilibrium constraints, SIAM J. Optim., 8, 673-681 (1998) · Zbl 0911.90302
[27] Audet, C.; Hansen, P.; Jaumard, B.; Savard, G., Links between linear bilevel and mixed 0-1 programming problems, J. Optim. Theory Appl., 93, 273-300 (1997) · Zbl 0901.90153
[28] Fortuny-Amat, J.; Mccarl, B., A representation and economic interpretation of a two-level programming problem, J. Oper. Res. Soc., 32, 783-792 (1981) · Zbl 0459.90067
[29] Neumann, C., Stein, O., Sudermann-Merx, N.: Bounds on the objective value of feasible roundings (forthcoming) · Zbl 1414.90239
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.