二维装箱问题非线性规划模型和算法

A nonlinear programming model for two-dimensional strip-packing problem and its numerical method

二维装箱问题是具有广泛应用背景的一类组合优化问题,这类问题是NP难问题,很难得到精确解.将二维装箱问题表示为一个非线性规划模型,用变分分析中切锥的概念建立了这一优化问题的一阶最优性条件.给出了求解这一优化问题的增广Lagrange方法,并求解了具体问题.数值实验表明增广Lagrange方法适合求解该问题,对于不超过10个物品的装箱问题可以求得精确解.

As a class of combinatorial optimization problems with many important applications, two-dimensional strip-packing problems are quite difficult to be solved accurately as they are NP hard. A two-dimensional strip-packing problem is formulated as a nonlinear programming （NLP） model and the notion of tangent cones in variational analysis is employed to establish the first-order optimality conditions for the NLP problem. The augmented Lagrange method is presented to solve this NLP problem and specific problems are solved by it. Numerical results show that the augmented Lagrange method is suitable for solving this NLP problem and it is able to find exact solutions to strlp-packing problems involving up to 10 items.