We study a deterministic technique to check the existence of feasible points for mixed-integer nonlinear optimization problems which satisfy a structural requirement that we call granularity. 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 present analysis is motivated by numerical results for mixed-integer linear problems from C. Neumann, O. Stein, N. Sudermann-Merx: A feasible rounding approach for mixed-integer optimization problems, Optimization Online, Preprint ID 2017-12-6367, 2017. We explain why the practical performance observed there improves when the number of discrete feasible points increases relative to the size of the relaxed feasible set. In particular, for the generated feasible points we present computable a-priori and a-posteriori bounds on the deviation of their objective function values from the optimal value. We illustrate our results computationally for large scale bounded knapsack problems.
Citation
Journal of Optimization Theory and Applications, Vol. 184 (2020), 433-465.