Branching rules in branch-and-bound algorithms for nonconvex mixed-integer nonlinear programming
Presenter
November 17, 2008
Keywords:
- Nonlinear programming
MSC:
- 49M37
Abstract
For the general class of MINLP problems where relaxing the integrality on integer variables yields a nonconvex problem, a commonly used solution method is Branch-and-Bound (BB). Two crucial components of a BB algorithm are: a convex relaxation, often an LP relaxation, to obtain lower bounds; and branching
rules for partitioning the solution set.
We present an extension to nonconvex MINLP of a branching technique that proved successful for Mixed-Integer Linear Programming, namely reliability branching. Branching rules can be applied on both integer and continuous variables in nonconvex MINLPs, and the choice of the branching variable depends on both the MINLP problem and its linear relaxation.
We discuss in detail the choice of both the branching variable and the branching point, i.e. the value of that variable where branching is done. We present some computational results and compare reliability branching with another branching technique for nonconvex MINLPs, Violation Transfer, on a set of publicly available instances.