Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các bài toán nhị phân ngẫu nhiên với hình phạt đơn giản cho vi phạm ràng buộc về dung lượng
Tóm tắt
Bài báo này nghiên cứu các chương trình ngẫu nhiên với các biến nhị phân ở giai đoạn đầu và các ràng buộc về dung lượng, sử dụng hình phạt đơn giản cho việc vi phạm dung lượng. Cụ thể, chúng tôi xem xét sâu hơn về bài toán ba lô trong đó trọng lượng và dung lượng theo các biến ngẫu nhiên độc lập và chứng minh rằng vấn đề này là yếu \(\mathcal{N}\mathcal{P}\)-khó trong tổng quát. Chúng tôi cung cấp các thuật toán pseudo-polynomial cho ba trường hợp đặc biệt của bài toán: trọng lượng và dung lượng có phân phối đồng nhất, tổng con với trọng lượng Gaussian và dung lượng ngẫu nhiên có phân phối dương tuyệt đối, và tổng con với trọng lượng cố định và dung lượng ngẫu nhiên tùy ý. Sau đó, chúng tôi chuyển sang một thuật toán nhánh và cắt dựa trên xấp xỉ bên ngoài của hàm mục tiêu. Chúng tôi cung cấp các kết quả tính toán cho bài toán ba lô ngẫu nhiên (i) với trọng lượng Gaussian và dung lượng cố định và (ii) với trọng lượng cố định và dung lượng phân phối đồng đều, trên các trường hợp được sinh ngẫu nhiên lấy cảm hứng từ các kết quả tính toán của bài toán ba lô.
Từ khóa
#bài toán ba lô ngẫu nhiên #biến nhị phân #ràng buộc dung lượng #thuật toán pseudo-polynomial #xấp xỉ bên ngoài #nghiên cứu tính toánTài liệu tham khảo
Abhishek K., Leyffer S., Linderoth J.T.: Filmint: an outer-approximation-based solver for nonlinear mixed integer programs. INFORMS J. Comput. 22(4), 555–567 (2010)
Badics T., Boros E.: Minimization of half-products. Math. Oper. Res. 23(3), 649–660 (1998)
Barnhart C., Hane C.A., Vance P.H.: Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 48(2), 318–326 (2000)
Beraldi P., Bruni M.E.: An exact approach for solving integer problem under probabilistic constraints with random technology matrix. Ann. Oper. Res. 177, 127–137 (2010)
Birge J.R., Louveaux F.V.: Introduction to Stochastic programming (2nd edn). Springer, New-York (2011)
Bonami P., Biegler L.T., Conn A.R., Cornuéjols G., Grossmann I.E., Laird C.D., Lee J., Lodi A., Margot F., Sawaya N., Wächter A.: An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim. 5(2), 186–204 (2008)
Bonami, P., Kilinc, M., Linderoth, J.: IMA Volumes. University of Minnesota. Algorithms and Software for Convex Mixed Integer Nonlinear Programs (2010)
Brown G.G., Graves G.W.: Real-time dispatch of petroleum tank trucks. Manage. Sci. 27, 19–32 (1981)
Cattrysse D.G., Van Wassenhove L.N.: A survey of algorithms for the generalized assignment problem. Eur. J. Oper. Res. 60(3), 260–272 (1992)
Cohn, A., Barnhart, C.: The stochastic knapsack problem with random weights: a heuristic approach to robust transportation planning. In: Proceedings of the Triennial Symposium on Transportation Analysis (TRISTAN III) (1998)
Hansotia B.: Some special cases of stochastic programs with recourse. Oper. Res. 25(2), 361–363 (1977)
ILOG CPLEX Division, Gentilly, France. ILOG. ILOG CPLEX 11.0 Reference Manual (2007)
Klein Haneveld, W.K., Stougie, L., van der Vlerk, M.H.: Stochastic integer programming with simple recourse. Technical Report Research Memorandum 455, University of Groningen (1991)
Kleywegt A.J., Papastavrou J.D.: The dynamic and stochastic knapsack problem with random sized items. Oper. Res. 49(1), 26–41 (2001)
Kleywegt A.J., Shapiro A., Homemde Mello T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2), 479–502 (2002)
Klopfenstein O.: Solving chance-constrained combinatorial problems to optimality. Comput. Optim. Appl. 45(3), 607–638 (2010)
Klopfenstein, O., Nace, D.: A note on polyhedral aspects of a robust knapsack problem. Optim. Online (2007)
Klopfenstein O., Nace D.: A robust approach to the chance-constrained knapsack problem. Oper. Res. Lett. 36(5), 628–632 (2008)
Kosuch S., Lisser A.: Upper bounds for the 0-1 stochastic knapsack problem and a b&b algorithm. Ann. Oper. Res. 176(1), 77–93 (2010)
Laporte G., Louveaux F.V., Mercure H.: The vehicle routing problem with stochastic travel times. Transp. Sci. 26(3), 161–170 (1992)
Louveaux F.V., van der Vlerk M.H.: Stochastic programming with simple integer recourse. Math. Program. 61, 301–325 (1993)
Martello S., Pisinger D., Toth P.: Dynamic programming and strong bounds for the 0-1 knapsack problem. Manage. Sci. 45(3), 414–424 (1999)
Morton D.P., Wood R.K.: Advances in computational and stochastic optimization, logic programming and Heuristic Search, chapter 5, pp. 149–168. Kluwer, Dordrecht (1998)
Mulvey J.M., Vanderbei R.J., Stavros A.Z.: Robust optimization of large-scale systems. Oper. Res. 43(2), 264–281 (1995)
Nauss R.M.: Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J. Comput. 15(3), 249–266 (2003)
Pisinger D.: An exact algorithm for large multiple knapsack problems. Eur. J. Oper. Res. 114(3), 528–541 (1999)
Prékopa A.: Stochastic Programming. Kluwer, Dordrecht (1995)
Quesada I., Grossman I.E.: An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Comput. Chem. Eng. 16(10/11), 937–947 (1992)
Spoerl, D., Wood, R.K.: A stochastic generalized assignment problem. INFORMS Annual Meeting, Atlanta, GA, 19–22 October (2003)
Wets R.J.B.: Solving stochastic programss with simple recourse. Stochastics 10(3), 219–242 (1983)