Optimization Online


Granularity in nonlinear mixed-integer optimization

Christoph Neumann (christoph.neumann***at***kit.edu)
Oliver Stein (stein***at***kit.edu)
Nathan Sudermann-Merx (nathan.sudermann-merx***at***basf.com)

Abstract: 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.

Keywords: Rounding; granularity; inner parallel set; consistency; global error bound

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Optimization Online, Preprint ID 2017-12-6373, 2017.

Download: [PDF]

Entry Submitted: 12/12/2017
Entry Accepted: 12/12/2017
Entry Last Modified: 12/12/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