Optimization Online


Error bounds for mixed integer nonlinear optimization problems

Oliver Stein (stein***at***kit.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
Entry Accepted: 07/22/2015
Entry Last Modified: 02/05/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society