A feasible rounding approach for mixed-integer optimization problems: theoretical aspects

Oliver Stein, Christoph Neumann, Nathan Sudermann-Merx

We introduce a new deterministic technique to generate good feasible points of mixed-integer optimization problems which satisfy a structural requirement that we call granularity. Finding a feasible point is known to be NP hard even for mixed-integer linear problems, so that many construction heuristics have been developed, among them the feasibility pump. In contrast to these heuristics, we show that solving certain purely continuous optimization problems and rounding their optimal points leads to feasible points of the original mixed-integer problem, as long as the latter is granular. The resulting algorithm is not heuristic but deterministic and, under an additional convexity assumption, even efficient.

The continuous optimization problems appearing in our approach have a structure that is similar to that of the continuous relaxation, and thus our approach has significant advantages over heuristics. For instance, the computational cost of our approach corresponds to merely a single step of the feasibility pump. For the objective function values of the generated feasible points we present computable a-priori and a-posteriori bounds on the deviation from the optimal value, as well as efficiently computable certificates for the granularity of a given problem.

A computational improvement step by integer line search and our promising experiences regarding the applicability of this approach are reported in the subsequent talk by Christoph Neumann.