New Algorithms For Nonlinear Integer Programming Problems

Integer programming deals with the problem of optimizing an objective function subjected to equality and/or inequality constraints and integer variables. If all the functions are linear, the problem is of a linear integer program. Otherwise, the problem is called a nonlinear integer program. The ultimate goal in integer optimization study is to develop efficient implementable algorithms for solving problems with integer variables. The development of efficient and robust algorithms and softwares for linear integer programming and the advent of high-speed computers have made linear integer programming an important tool for solving many real-world problems. However, many real-world problems cannot be modelled or approximated adequately by linear integer program problems, due to the nature of the nonlinearity of the objective function and/or the nonlinearity of the constraints. Rapid progress has been made in designing efficient solution methods for nonlinear integer programming during the past three decades. This thesis is devoted to develop efficient and robust algorithms for three classes of nonlinear integer programming problems.The thesis consists of five chapters. The motivations of the algorithms are presented in each chapter. The algorithms are then described with detailed numerical examples and graphical illustrations. Extensive computational experiments and numerical results are presented for each algorithm.Chapter 1 discusses the background of nonlinear integer programming and gives several examples of nonlinear integer programming problems from different application fields. such as stratified sampling and capital planning in manufacturing, etc.Chapter 2 presents an algorithm for a class of concave knapsack problem with a single linear constraint. The algorithm is of branch-and-bound method where lower bounds and upper bounds of the problem are computed by linearly underestimating the objective function. Domain cut-partition scheme is adopted to eliminate the duality gap. The lower bound can be improved during the iteration process. The algorithm finds an optimal solution of the primal problem in a finite number of iterations. Promising computational results are reported for large-scale concave...