A feasible rounding approach for granular optimization problems
Christoph Neumann (christoph.neumann89gmail.com)
Abstract: 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.
Keywords: Rounding, granularity, grid relaxation retract, global error bound, knapsack problem
Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )
Category 2: Integer Programming ((Mixed) Integer Linear Programming )
Citation: Optimization Online, Preprint ID 2016-05-5459, 2016.
Entry Submitted: 05/24/2016
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|