A subgradient algorithm for nonlinear integer programming and its parallel implementation

[摘要] This work concerns efficiently solving a class of nonlinear integer programming problems: min ${f(x)$: $x in {0,1}sp{n}}$ where $f(x)$ is a general nonlinear function. The notion of subgradient for the objective function is introduced. A necessary and sufficient condition for the optimal solution is constructed. And a new algorithm, called the subgradient algorithm, is developed. The algorithm is an iterative procedure, searching for the solution iteratively among feasible points, and in each iteration, generating the next iterative point by solving the problem for a local piecewise linear model of the original problem which is constructed with supporting planes for the objective function at a set of feasible points. Special continuous optimization techniques are used to compute the supporting planes. The problem for each local piecewise linear model is solved by solving an equivalent linear integer program. The fundamental theory for the new approach is built and all related mathematical proofs and derivations such as proofs for convergence properties, the finiteness of the algorithm, as well as the correct formulation of the subproblems are presented. The algorithm is parallelized and implemented on parallel distributed-memory machines. The preliminary numerical results show that the algorithm can solve test problems effectively. To implement the subgradient algorithm, a parallel software system written in EXPRESS C is developed. The system contains a group of parallel subroutines that can be used for either continuous or discrete optimization such as subroutines for QR, LU and Cholesky factorizations, triangular system solvers and so on. A sequential implementation of the simplex algorithm for linear programming also is included. Especially, a parallel branch-and-bound procedure is developed. Different from directly parallelizing the sequential binary branch-and-bound algorithm, a parallel strategy with multiple branching is used for good processor scheduling. Performance results of the system on NCUBE are given.

[发布机构] Rice University

[效力级别] Computer science