Proximity and Flatness Bounds for Linear Integer Optimization: With Integral , an Optimal LP Vertex Is Strictly Within -Distance of an Integer OptimumResearch Paper
An integer linear program asks for the maximum of over the integer points of a polyhedron . Its linear relaxation is much easier to solve, so a basic question is how far an optimal vertex of the relaxation can be from the nearest optimal integer solution . A bound on confines the search…