Nonlinear Optimization Approaches For Two-Dimensional Strip Packing Problems

This dissertation studies, from a new viewpoint, one class of two-dimensional packing problems- two-dimensional strip packing problems(2SP). The purpose of this dissertation is to establish nonlinear optimization models for various 2SP problems and design algorithms for solving these optimization problems. The optimality theories for the given optimization models are established based on Quasidifferential Analysis and Variational Analysis, and some nonlinear Lagrange methods are adopted to find optimal solutions.The main results may be summarized as follows:1. Chapter 2 discusses the d (d is a positive integer) dimensional strip packing problem. We present the mathematical model for the problem of packing general items in d dimensional space firstly and then specify the model for the particular cases of packing generalized cuboids and balls. We construct a nondifferentiable model for the problem of packing generalized cuboids, which is a quasidifferentiable optimization problem, and establish the first order optimality conditions by using the quasidifferential theory. After that, we transfer this model into a smooth optimization model and establish the necessary optimality conditions using the optimality theory of variational analysis. As to the problem of packing balls, a smooth model is given and the corresponding optimality conditions are established by the optimality theory of variational analysis.2. Chapter 3 studies nonlinear optimization models for various two-dimensional strip packing problems(2SP). First, mathematical models for the two-dimensional strip packing problem of packing rectangles are constructed in two ways. Based on the mathematical description for the locational relationships of two rectangles, a smooth optimization model is presented by the former way and the optimality theory of nonlinear programming is used to establish its optimality conditions. On the other hand, a nondifferentiable model is proposed directly by the latter way based on the nonoverlapping condition of any two rectangles. The optimality conditions of this nondifferentiable model are established by the quasidifferential theory. The nondifferentiable model can be transformed into a nonlinear programming model and its necessary optimality conditions are established based on the optimality theory of variational analysis. Compared with the smooth one, the nonlinear programming model is better than the former. Furthermore, we consider the extended two-dimensional strip packing problem of packing circles, triangles and polygons. In view of the sep-arate theory of convex sets and the geometrical character of polygons, we construct the models for the problems of packing triangles and polygons and establish the first order optimality conditions for these models.3. Chapter 4 considers the numerical algorithms for solving the nonlinear optimization models for the two-dimensional strip packing problems. At first, we construct a modified Lagrange function for the nonlinear programming problem with inequality constraints and analyze the well performance of this function. Secondly, a dual algorithm, i.e., a nonlinear Lagrange algorithm, based on the modified Lagrange function is proposed. Detailed convergence results for the dual algorithm are given and it is proved that there exists a threshold, and the algorithm will converge if the penalty parameter is less than the threshold. Moreover, we estimate the condition number of the modified Lagrange function's Hesse and it turns out that the penalty parameter should not be too small in practical computation. Finally, the proposed nonlinear Lagrange algorithm and the classical augmented Lagrange algorithm are applied to solve the problems of packing circles and rectangles respectively and the computational results of several examples are shown,4. Chapter 5 applies the obtained results of two-dimensional strip packing problem to the berth allocation problem of the vessels in the container port. We formulate the berth allocation problem as a two-dimensional strip packing problem with additional constraints and use the augmented Lagrange algorithm to solve several instances.