Reduction of nonlinear integer separable programming problems^∗

^∗This research was supported by the Division of Computer Research, National Science Foundation under Research Grant DCR8405489.

Abstract

This paper considers the general integer separable programming problem. The nonlinear part of the objective function is given in terms of the variables x∊Rⁿ , while the linear part is given in terms of x∊R^k , where k may be much larger than n. The original problem is reduced to a linear zero-one problem. The linearization is based on a particular representation of piecewise linear functions, that approximate the nonlinear part of the objective function. This approximation is exact for all integer feasible points and therefore the solution of the resulting problem is that of the original problem. In addition this linearization is valid for the general nonconvex problem. An example with a nonconvex objective function illustrates these ideas. Using the same techniques a simple algorithm (that requires only sorting) is given for a class of nonlinear integer knapsack problems.

Keywords:

• Minimization
• Hessian
• Matrix Definiteness

^∗This research was supported by the Division of Computer Research, National Science Foundation under Research Grant DCR8405489.

^∗This research was supported by the Division of Computer Research, National Science Foundation under Research Grant DCR8405489.

Notes

^∗This research was supported by the Division of Computer Research, National Science Foundation under Research Grant DCR8405489.