Nonlinear Integer Programming

D. Li and C. K. Ng

The research goal is to establish convergent duality theory and to develop efficient solution algorithms for large-scale nonlinear integer programming problems. The fundamental target underlying our theoretical development is to eliminate duality gap in the classical Lagrangian dual formulation. We have developed nonlinear Lagrangian theory that has yielded several new dual formulations with asymptotic zero duality gap.The key concept is the construction of a nonlinear support for a nonconvex piecewise-constant perturbation function. Our numerical implementation of a duality-gap reduction process relies on some novel cutting procedures. Performing objective-level cut, objective contour cut or domain cut reshapes the perturbation function, thus exposing eventually an optimal solution to the convex hull of a revised perturbation function and guaranteeing a zero duality gap for a convergent Lagrangian method. Applications include nonlinear knapsack problems, constrained redundancy optimization in reliability networks, and optimal control problems with integer constraints.