Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp đối ngẫu ẩn cho các bài toán ba lô phi tuyến đa chiều
Tóm tắt
Các bài toán ba lô phi tuyến đa chiều thường gặp trong phân bổ tài nguyên, lập kế hoạch công nghiệp và mạng máy tính. Trong bài báo này, một phương pháp đối ngẫu ẩn được đề xuất để giải quyết lớp bài toán này. Bài toán có nhiều ràng buộc được đơn giản hóa thành bài toán với một ràng buộc bằng cách sử dụng kỹ thuật đối ngẫu. Để tính toán các giới hạn chặt chẽ hơn cho bài toán gốc, phương pháp mặt cắt được sử dụng để giải quyết bài toán đối ngẫu ẩn, trong đó bài toán đối ngẫu ẩn được giải quyết bằng phương pháp tuyến tính hóa 0-1. Kỹ thuật cắt miền được áp dụng để loại bỏ khoảng cách đối ngẫu và do đó đảm bảo sự hội tụ của thuật toán. Kết quả số liệu được báo cáo cho các bài toán ba lô phi tuyến đa chiều quy mô lớn.
Từ khóa
#bài toán ba lô #phương pháp đối ngẫu #tối ưu hóa #ràng buộc phi tuyến #thuật toán hội tụTài liệu tham khảo
Bretthauer K M, Shetty B. The nonlinear resource allocation problem [J]. Operations Research, 1995, 43: 670–683.
Bretthauer K M, Shetty B. The nonlinear knapsack problem-algorithms and applications [J]. European Journal of Operational Research, 2002, 138: 459–472.
Cooper M W. The use of dynamic programming for the solution of a class of nonlinear programming problems [J]. Naval Research Logistics Quarterly, 1980, 27: 89–95.
Cooper M W. Survey of methods of pure nonlinear integer programming [J]. Management Science, 1981, 27: 353–361.
Körner F. A hybrid method for solving nonlinear knapsack problems [J]. European Journal of Operational Research, 1989, 38: 238–427.
Djerdjour M, Mathur K, Salkin H M. A surrogate relaxation based algorithm for a general quadratic multi-dimensional knapsack problem [J]. Operations Research Letters, 1988, 7: 253–258.
Marsten R E, Morin T L. A hybrid approach to discrete mathematical programming [J]. Mathematical Programming, 1978, 14: 21–40.
Glover F. A multiphase-dual algorithm for the zero-one integer programming problem [J]. Operations Research, 1965, 13: 879–919.
Parker R G, Rardin R L. Discrete Optimization [M]. Boston: Academic Press, 1988.
Dyer M E. Calculating surrogate constraints [J]. Mathematical Programming, 1980, 19: 255–278.
Kim S L, Kim S. Exact algorithm for the surrogate dual of an integer programming problem: subgradient method approach [J]. Journal of Optimization Theory and Applications, 1998, 96: 363–375.
Karwan M H, Rardin R L. Searchability of the composite and multiple surrogate dual functions [J]. Operations Research, 1980, 28: 1251–1257.
Sarin S, Karwan M H, Rardin R L. A new surrogate dual multiplier search procedure [J]. Naval Research Logistics, 1987, 34: 431–450.
Li D, Sun X L. Nonlinear Integer Programming [M]. New York: Springer, 2006.
Hochbaum D S. A nonlinear knapsack problem [J]. Operations Research Letters, 1995, 17: 103–110.
Sun X L, Wang F L, Li D. Exact algorithm for concave knapsack problems: linear underestimation and partition method [J]. Journal of Global Optimization, 2005, 33: 15–30.