Nonlinearoptimizationproblemscontainingbothcontinuousanddiscretevariables
are called mixed integer nonlinear programs (MINLP). Such problems arise
in many ?elds, such as process industry, engineering design,
communications, and ?nance. There is currently a huge gap between MINLP
and mixed integer linear programming(MIP) solvertechnology.With a
modernstate-of-the-artMIP solver
itispossibletosolvemodelswithmillionsofvariablesandconstraints,
whereasthe
dimensionofsolvableMINLPsisoftenlimitedbyanumberthatissmallerbythree or
four orders of magnitude. It is theoretically possible to approximate a
general MINLP by a MIP with arbitrary precision. However, good MIP
approximations are usually much larger than the original problem.
Moreover, the approximation of nonlinear functions by piecewise linear
functions can be di?cult and ti- consuming. In this book relaxation and
decomposition methods for solving nonconvex structured MINLPs are
proposed. In particular, a generic branch-cut-and-price (BCP) framework
for MINLP is presented. BCP is the underlying concept in almost all
modern MIP solvers. Providing a powerful decomposition framework for
both sequential and parallel solvers, it made the success of the current
MIP technology possible. So far generic BCP frameworks have been
developed only for MIP, for example, COIN/BCP (IBM, 2003) andABACUS
(OREAS GmbH, 1999). In order to generalize MIP-BCP to MINLP-BCP, the
following points have to be taken into account: - A given (sparse) MINLP
is reformulated as a block-separable program with linear coupling
constraints.The block structure makes it possible to generate Lagrangian
cuts and to apply Lagrangian heuristics. - In order to facilitate the
generation of polyhedral relaxations, nonlinear c- vex relaxations are
constructed. - The MINLP separation and pricing subproblems for
generating cuts and columns are solved with specialized MINLP solvers.
