We introduce a new technique to generate good feasible points of mixed-integer nonlinear optimization problems. It makes use of the so-called inner parallel set of the relaxed feasible set, which was employed in O. Stein, Error bounds for mixed integer linear optimization problems, Mathematical Programming, Vol. 156 (2016), 101-123, as well as O. Stein, Error bounds for mixed integer nonlinear optimization problems, Optimization Letters, 2016, DOI 10.1007/s11590-016-1011-y, to bound the error occurring when an optimal point of the relaxed problem is rounded to the next integer point. On the contrary, in the present paper we show that efficiently solving certain purely continuous optimization problems over the inner parallel set and rounding their optimal points leads to feasible points of the original mixed-integer problem. For their objective function values we present computable a-priori and a-posteriori bounds on the deviation from the optimal value, as well as a computable certificate for the consistency of the inner parallel set. Numerical examples for large scale knapsack problems and for several problems from the MIPLIB libraries illustrate that our method is able to outperform standard software. A post processing step to our approach further improves the results.
Citation
Optimization Online, Preprint ID 2016-05-5459, 2016.