A Disjunctive Cutting-Plane-Based Branch-and-Cut Algorithm for 0-1 Mixed-Integer Convex Nonlinear Programs

In this paper, a disjunctive cutting-plane-based branch-and-cut algorithm is developed to solve the 0-1 mixed-integer convex nonlinear programming (MINLP) problems. In a branch-and-bound framework, the 0-1 MINLP problem is approximated with a 0-1 mixed-integer linear program at each node, and then the lift-and-project technology is used to generate valid cuts to accelerate the branching process. The cut is produced by solving a linear program that is transformed from a projection problem, in terms of the disjunction on a free binary variable, and its dual solutions are applied to lift the cut to become valid throughout the enumeration tree. A strengthening process is derived to improve the coefficients of the cut by imposing integrality on the left free binary variables. Finally, the computational results on four test problems indicate that the added cutting planes can reduce the branching process greatly and show that the proposed algorithm is very promising for large-scale 0-1 MINLP problems, because a linear program is always computationally less expensive than a nonlinear program.