Error bounds for mixed integer nonlinear optimization problems
Oliver Stein (steinkit.edu)
Abstract: 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.
Keywords: Rounding, granularity, grid relaxation retract, global error bound
Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )
Citation: Optimization Letters, 2016, DOI 10.1007/s11590-016-1011-y.
Entry Submitted: 07/22/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|