A feasible rounding approach for mixed-integer optimization problems: algorithmic aspects and applications

Christoph Neumann, Oliver Stein, Nathan Sudermann-Merx

A feasible rounding approach, introduced in the preceding talk by Oliver Stein, is a novel technique to compute good feasible points for mixed-integer optimization problems. The central idea of this approach is the construction of an enlarged inner parallel set for which any rounding of any point is feasible in the original problem. Under an additional convexity assumption, this approach may be carried out efficiently, if the optimization problem satisfies a structural requirement that is labeled granularity.

We elaborate that this concept is particularly promising for mixed-integer linear optimization problems due to the availability of an explicit and exact formula for the enlarged inner parallel set.
We provide a computational study on optimization problems from the MIPLIB libraries and demonstrate that granularity may be expected in various real world applications. For these problems we show that our method is able to outperform standard software. Finally, we develop and test a post processing step using integer line search, which is able to significantly improve the computational results.