Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân nhánh trên các bất đẳng thức tổng quát
Tóm tắt
Bài báo này xem xét một sự sửa đổi của thuật toán phân nhánh và cắt trong Lập trình tuyến tính nguyên (Mixed Integer Linear Programming) khi mà việc phân nhánh được thực hiện trên các bất đẳng thức tổng quát thay vì trên các biến. Chúng tôi chọn các bất đẳng thức phân nhánh đầy hứa hẹn dựa trên một chỉ số heuristic về chất lượng của bất đẳng thức. Chỉ số này khai thác mối quan hệ giữa các bất đẳng thức phân nhánh và các cắt giao nhau. Trong công trình này, chúng tôi tập trung vào các bất đẳng thức xác định các cắt Gomory cho nguyên tại một cơ sở tối ưu của việc thư giãn lập trình tuyến tính. Quy trình được thử nghiệm trên các ví dụ từ tài liệu hiện có. Các thử nghiệm cho thấy rằng, đối với phần lớn các ví dụ, cây phân loại thu được khi phân nhánh trên các bất đẳng thức tổng quát có kích thước nhỏ hơn so với cây thu được khi phân nhánh trên các biến, ngay cả khi việc phân nhánh theo biến được thực hiện bằng cách phân nhánh mạnh hoàn tất.
Từ khóa
#thuật toán phân nhánh và cắt #lập trình tuyến tính nguyên #bất đẳng thức tổng quát #cắt Gomory #cây phân loạiTài liệu tham khảo
Aardal K., Bixby R.E., Hurkens C.A.J., Lenstra A.K., Smeltink J.W.: Market split and basis reduction: towards a solution of the Cornuéjols-Dawande instances. Inf. J. Comput. 12(3), 192–202 (2000)
Aardal K., Hurkens C.A.J., Lenstra A.K.: Solving a system of linear diophantine equations with lower and upper bounds on the variables. Math. Oper. Res. 25(3), 427–442 (2000)
Achterberg T., Koch T., Martin A.: Branching rules revisited. Oper. Res. Lett. 33, 42–54 (2005)
Achterberg, T.,Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34, 361–372Available from http://www.miplib.zib.de (2006)
Andersen K., Cornuéjols G., Li Y.: Reduce-and-split cuts: improving the performance of mixed integer Gomory cuts. Manag. Sci. 51, 1720–1732 (2006)
Balas E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)
Balas E., Ceria S., Cornuéjols G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58, 295–324 (1993)
Balas E., Ceria S., Cornuéjols G.: Mixed 0–1 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 42(9), 1229–1246 (1996)
Beale E.M.L., Tomlin J.A.: Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In: Lawrence, J. (eds) OR 69: Proc. Fifth Int. Conf. Oper. Res., pp. 447–454. Tavistock Publications, London (1970)
Bixby R.E., Ceria S., McZeal C.M., Savelsbergh M.W.P.: An updated mixed integer programming library: MIPLIB 3.0. Optima. 58, 12–15 (1998)
Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed integer programming: a progress report. In: Grötschel, M. (ed.) The Sharpest Cut: The Impact of Manfred Padberg and his Work, pp. 309–326. MPS/SIAM Series in Optimization, SIAM (2004)
Cook W., Kannan R., Schrijver A.: Chvátal closures for mixed integer programs. Math. Program. 47, 155–174 (1990)
Cornuéjols G., Dawande M.: A class of hard small 0–1 programs. In: Bixby, R.E., Boyd, E.A., Rios-Mercado, R.Z. (eds) Integer Programming and Combinatorial Optimization, 6th International IPCO Conference, Lecture notes in Computer Science 1412, pp. 284–293. Springer-Verlag, Berlin (1998)
Cornuéjols, G., Liberti, L., Nannicini, G.: Improved strategies for branching on general disjunctions. Technical report, Working paper, July 2008, revised April (2009)
Fischetti M., Lodi A.: Local branching. Math. Program. 98, 23–47 (2003)
Gomory, R.E.: An algorithm for the mixed integer problem. Technical Report RM-2597, Rand Corporation (1960)
Grötschel M., Lovász L., Schrijver A.: Progress in combinatorial optimizarion chapter Geometric methods in combinatorial optimization, pp. 167–183. Academic Press, Toronto (1984)
Lenstra H.W. Jr: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)
Laundy, R., Perregaard, M., Tavares, G., Tipi, H., Vazacopoulos, A.: Solving hard mixed integer programming problems with Xpress-MP: a MIPLIB 2003 case study. Technical report (2009)
Lenstra A.K., Lenstra H.W. Jr., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)
Linderoth J.T., Savelsbergh M.W.P.: A computational study of search strategies for mixed integer programming. Inf. J. Comput. 11, 172–187 (1999)
Lovász L., Scarf H.E.: The generalized basis reduction algorithm. Math. Oper. Res. 17, 751–764 (1992)
Mahajan, A., Ralphs, T.K.: Experiments with branching using general disjunctions. In: Chinneck, J.W. et al. (eds.) Operations Research and Cyber-Infrastructure, Operations Research/Computer Science Interfaces Series 47, pp. 101–118. Springer, Berlin (2009)
Marchand H., Wolsey L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001)
Mehrotra, S., Li, Z.: On generalized branching methods for mixed integer programming. Technical report, Northwestern University, Evanston, Illinois 60208 (2004)
Mittelman, H.: Benchmarks for optimization software. http://www.plato.la.asu.edu/bench.html (2006)
Owen J., Mehrotra S.: Experimental results on using general disjunctions in branch-and-bound for general-integer linear program. Comput. Optim. Appl. 20, 159–170 (2001)
MIPLIB website of Zuse Institute Berlin. URL: http://www.miplib.zib.de/miplib3/miplib_prev.html