Error bounds for mixed integer linear optimization problems (Q263186)

This article improves the calculation of error bounds for optimality and feasibility of a solution generated as the rounding of an optimal point of the linear relaxation of a mixed integer program. The author begins with an introduction to mixed integer programming and the definitions of optimality error and feasibility error. This is followed by a number of interesting properties of these errors, including proofs of the magnitude of the global error bounds. The article continues with two sections, one considering the derivation of a posteriori error bounds, which are those that are linked to the current value of the optimal point, and one which considers a priori error bounds which do not depend on the current optimal point. Several properties of these bounds are presented with proof and their link to the existing literature is established. The article concludes with a section on the applicability of the error bounds to certain convex optimization problems such as quadratic programming.