A Dynamic Programming Method for Separable Nonlinear Integer Programming

摘要

A dynamic programming method is proposed for solving nonlinear integer programming problem with separable quadratic objective function and multiple linear constraints. To mitigate the curse of dimensionality in dynamic programming, the surrogate constraint formulation is used as a platform for powerful utilization of dynamic programming. In this paper, by investigating the contour of objective function, the polyhedron of feasible region and their relationship in domain space, we find the condition when zero duality gap happens and propose a domain-cutting scheme to reduce the duality gap successively and eventually eliminate it.