Relaxation and decomposition methods for mixed integer nonlinear programming. (Q2386510)

This monograph is the outgrow of a 5 years project on mixed-integer nonlinear programming. The first part deals with basic concepts, the second part with algorithms. The book starts with problem reformulations including disjunctive constraints, block separability, convex underestimators and Lagrangian relaxations. The next chapter is devoted to decomposition methods, in particular dual methods (subgradient and bundle methods), primal cutting plane methods, column generation and Benders decomposition. The next chapter gives an introduction to semidefinite relaxations and presents a new approach for solving the dual of a general block-separable mixed integer quadratic program via eigenvalue optimization. Chapter 6 presents methods for generating convex underestimators. In particular Bézier polynomials are used and a new sampling method for constructing polynomial underestimators for general multivariate black box functions is presented. In the sequence cuts and lower bounds are considered and local as well as global optimality criteria are derived. A short chapter deals with the adaptive discretization of infinite dimensional nonlinear mixed-integer programs. Part 2 starts with an overview of global optimization methods. Moreover, it presents several heuristics like a deformation heuristic based on smoothing the objective function by combining it with a convex understimator, rounding heuristics and a partitoning heuristic. A main chapter deals with branch-cut-and-price algorithms. All algorithms are illustrated by numerical results. The monograph closes with the description of LaGO -- an object oriented library for solving mixed-integer nonlinear programs. An extensive bibliography documents the literature in this field.