Convergent Lagrangian in separable nonlinear integer programming: Cutting methods

Adopting novel solution concepts of objective level cut and domain cut, two convergent Lagrangian methods are proposed in this thesis for obtaining exact solution to separable nonlinear integer programming problems. The Lagrangian and objective level cut method investigates how to expose an optimal solution to the convex hull of a revised perturbation function by successively reshaping the perturbation function. The objective level cut is used to eliminate the duality gap and thus to guarantee the convergence of the Lagrangian method on a revised domain. The nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable function subject to separable constraints. The Lagrangian and domain cut method is proposed for solving this kind of problems with monotonicities. It exploits the special structure of the problem by Lagrangian decomposition and dual search. The domain cut is used to eliminate the duality gap and thus to guarantee the convergence of the algorithm. Computational results are reported for a variety of problems with up to 5000 integer variables. The proposed methods are shown to be efficient in implementation and promising in solving large-scale separable nonlinear programming problems.