Error bounds for mixed integer linear optimization problems

• 成果类型: Article
• 署名作者: Stein, Oliver
• 署名单位: Helmholtz Association; Karlsruhe Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0872-7
• 发表日期: 2016
• 页码: 101-123
• 关键词: sharp lipschitz-constants; systems; inequalities

摘要

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 a global error bound for mixed integer linear problems constructed via a so-called grid relaxation retract. Relations to proximity results, the integer rounding property, and binary analytic problems are highlighted.