A general lexicographic partial enumeration algorithm for the solution of integer nonlinear programming problems
Mohammad S. Sabbagh · 1983
This dissertation presents a general lexicographic partial enumeration algorithm for solving discrete nonlinear optimization problems of the form: Minimize g(,0)(x), subject to g(,i) (x) (GREATERTHEQ) b(,i); i = 1, 2, . . . , m, x = (x(,1),x(,2), . . . , x(,n)), 0 (LESSTHEQ) lb(,j) (LESSTHEQ) x(,j) (LESSTHEQ) ub(,j); j = 1, 2, . . . , n. Here each x(,j) is an integer variable with integer lower bound lb(,j) and integer upper bound ub(,j). The algorithm can solve any discrete optimization problem of this form, but it is more efficient if some of the functions g(,i) can be expressed as differences of two isotone nondecreasing functions. It is even more efficient if some of the functions g(,i) are isotone nondecreasing functions, and it is most efficient if the objective function or some of the constraint functions, or both, are linear. Some of the features of this algorithm are as follows: (1) It locates the global constrained discrete optimal solution by function evaluations only and so does not require that the functions by continuous or even defined for noninteger values of the variables. It is not even necessary to have explicit algebraic expressions for the functions. (2) It is easy to program and requires a small amount of computer memory. (3) It is not necessary to transform the variables to weighted sums of binary variables. (4) No extra constraints or transformations are needed to impose the lower and upper bounds on the non-negative variables. (5) It incorporates a special new approach to take advantage of a linear objective function or any linear constraint functions, or both, that may be present. (6) It may be used to obtain approximate solutions to mixed and continuous nonlinear optimization problems. After a review of the literature on discrete nonlinear optimization, the algorithm is presented and its operation is described in detail. It is shown that in this algorithm, we are working in a space in which there is a minimum total number of possible points. Rules for reducing the number of infeasible points to be considered are given and illustrated, and then guidelines for reordering the variables to reduce the overall solution time are developed and illustrated. Illustrative applications are given in the areas of multi-echelon repairable item provisioning and aircraft development and production scheduling, and a number of test problems from the literature are solved.