Optimization Online


A feasible rounding approach for granular optimization problems

Christoph Neumann (christoph.neumann89***at***gmail.com)
Oliver Stein (stein***at***kit.edu)
Nathan Sudermann-Merx (sudermann***at***kit.edu)

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.

Download: [PDF]

Entry Submitted: 05/24/2016
Entry Accepted: 05/24/2016
Entry Last Modified: 02/16/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society