Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các ràng buộc phá vỡ đối xứng cho việc đóng gói các hình chữ nhật đồng nhất trong các khối đa diện
Tóm tắt
Hai vấn đề liên quan đến việc đóng gói các hình chữ nhật đồng nhất trong một khối đa diện được giải quyết trong công trình hiện tại. Các hình chữ nhật chỉ được phép khác nhau thông qua các phép dịch theo chiều ngang hoặc chiều đứng và có thể là các phép quay 90 độ. Vấn đề đầu tiên được xem xét là làm thế nào để đóng gói càng nhiều hình chữ nhật đồng nhất càng tốt trong một khối đa diện đã cho, trong khi vấn đề thứ hai là tìm khối đa diện nhỏ nhất của một loại nhất định có thể chứa một số lượng hình chữ nhật đồng nhất cố định. Cả hai vấn đề đều được mô hình hóa dưới dạng các bài toán lập trình số nguyên hỗn hợp. Các ràng buộc phá vỡ đối xứng được giới thiệu để hỗ trợ việc giải quyết các mô hình MIP. Các kết quả số được trình bày.
Từ khóa
#đóng gói hình chữ nhật #khối đa diện #lập trình số nguyên hỗn hợp #ràng buộc phá vỡ đối xứng #tối ưu hóaTài liệu tham khảo
Beasley J.E.: An exact two-dimensional non-guillotine cutting tree-search procedure. Oper. Res. 33, 49–64 (1985)
Birgin E.G., Lobato R.D.: Orthogonal packing of identical rectangles within isotropic convex regions. Comput. Ind. Eng. 59, 595–602 (2010)
Birgin E.G., Lobato R.D., Morabito R.: An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. J. Oper. Res. Soc. 61, 306–320 (2010)
Birgin, E.G., Lobato, R.D., Morabito, R.: Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm. J. Oper. Res. Soc. doi:10.1057/jors.2011.6
Birgin E.G., Martínez J.M., Mascarenhas W.F., Ronconi D.P.: Method of sentinels for packing items within arbitrary convex regions. J. Oper. Res. Soc. 57, 735–746 (2006)
Birgin E.G., Morabito R., Nishihara F.H.: A note on an L-approach for solving the manufacturer’s pallet loading problem. J. Oper. Res. Soc. 56, 1448–1451 (2005)
Birgin E.G., Martínez J.M., Nishihara F.H., Ronconi D.P.: Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization. Comput. Oper. Res. 33, 3535–3548 (2006)
Cao F., Du D.-Z., Gao B., Wan P.-J., Pardalos P.M.: Minimax problems in combinatorial optimization. In: Du, D.-Z., Pardalos, P.M. (eds) Minimax and Applications, pp. 262–285. Kluwer Academic Publishers, Dordrecht (1995)
Cassioli A., Locatelli M.: A heuristic approach for packing identical rectangles in convex regions. Comput. Oper. Res. 38, 1342–1350 (2011)
Floudas, C.A., Pardalos, P.M. (eds): Encyclopedia of Optimization, , 2nd edn. Springer, Berlin (2009)
Hurkens, C.A.J., Lodi, A., Martello, S., Monaci, M., Woeginger, G.J.: Complexity and approximation of an area packing problem. Optim. Lett. doi:10.1007/s11590-010-0246-2 (in press)
Kallrath J.: Cutting circles and polygons from area-minimizing rectangles. J. Global Optim. 43, 299–328 (2009)
Lodi A., Monaci M.: Integer linear programming models for 2-staged two-dimensional Knapsack problems. Math. Program. 94, 257–278 (2003)
Mascarenhas W.F., Birgin E.G.: Using sentinels to detect intersections of convex and nonconvex polygons. Comput. Appl. Math. 29, 247–267 (2010)
Ostrowski J., Linderoth J., Rossi F., Smirglio S.: Solving Steiner triple covering problems. Otima 83, 1–7 (2010)
Sawaya N.W., Grossmann I.E.: A cutting plane method for solving linear generalized disjunctive programming problems. Comput. Chem. Eng. 29, 1891–1913 (2005)
Xie W., Sahinidis N.V.: A branch-and-bound algorithm for the continuous facility layout problem. Comput. Chem. Eng. 32, 1016–1028 (2008)