Error bounds for mixed integer linear optimization problems
Oliver Stein (steinkit.edu)
Abstract: We introduce computable a-priori and a-posteriori error bounds for optimality and feasibility of a point generated as the rounding of an optimal point of the LP relaxation of a mixed integer linear optimization problem. Treating the mesh size of integer vectors as a parameter allows us to study the effect of different `granularities' in the discrete variables on the error bounds. Our analysis mainly bases on the construction of a so-called grid relaxation retract. Relations to proximity results and the integer rounding property are highlighted.
Keywords: Error bound, grid relaxation retract, granularity, Hoffman constant
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Citation: Mathematical Programming, Vol. 156 (2016), 101-123, DOI 10.1007/s10107-015-0872-7.
Entry Submitted: 11/25/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|