Error bounds for mixed integer nonlinear optimization problems

We introduce a-posteriori and a-priori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the NLP relaxation of a mixed-integer nonlinear optimization problem. Our analysis mainly bases on the construction of a tractable approximation of the so-called grid relaxation retract. Under appropriate Lipschitz assumptions on the defining functions, we thereby generalize and slightly improve results for the mixed-integer linear case from O. Stein, Error bounds for mixed integer linear optimization problems, Mathematical Programming, 2015, DOI 10.1007/s10107-015-0872-7. In particular, we identify cases in which the optimality and feasibility errors tend to zero at an at least linear rate for increasingly refined meshes.


Optimization Letters, 2016, DOI 10.1007/s11590-016-1011-y.