Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Cắt Đồng Convex Tối Ưu Hóa Độ Sâu
Tóm tắt
Bài báo này trình bày một cách tiếp cận tổng quát, độc lập về tính lồi hoặc cắt giao nhau. Nó mô tả hai cách tương đương để tạo ra một cắt—thông qua một tập hợp lồi hoặc một hàm lồi—và một khái niệm về thứ tự một phần của độ mạnh của cắt. Chúng tôi sau đó đặc trưng hóa cấu trúc của các tập hợp và hàm tạo ra các cắt mạnh nhất theo thứ tự một phần. Tiếp theo, chúng tôi chuyên biệt hóa khung phân tích này cho trường hợp lập trình tuyến tính nguyên hỗn hợp (MIP). Đối với trường hợp này, chúng tôi xây dựng hai loại bài toán tạo cắt sâu nhất, thông qua tập hợp hoặc thông qua hàm, và tiếp theo xem xét một số trường hợp đặc biệt có thể tính toán hiệu quả. Chúng tôi kết luận với các bài kiểm tra tính toán của một trong những quy trình này trên một tập hợp lớn các bài toán MIPLIB.
Từ khóa
#cắt giao nhau #lập trình tuyến tính nguyên hỗn hợp #tính lồi #độ sâu tối ưuTài liệu tham khảo
Balas, E. (1971). “Intersection Cuts—A New Type of Cutting Planes for Integer Programming.” Operations Research 19, 19–39.
Balas, E. (1972). “Integer Programming and Convex Analysis: Intersection Cuts from Outer Polars.” Mathematical Programming 2, 330–382.
Balas, E., V.J. Bowman, F. Glover, and D. Sommer. (1971). “An Intersection Cut From the Dual of the Unit Hypercube.” Operations Research 19, 40–44.
Balas, E., S. Ceria, and G. Cornuéjols. (1993). “A Lift-And-Project Cutting Plane Algorithm for Mixed 0–1 Programs.” Mathematical Programming 58(3), 295–324.
Balas, E., S. Ceria, and G. Cornuéjols. (1996). “Mixed 0–1 Programming by Lift-And-Project in a Branch-And-Cut Framework.” Management Science 42(9), 1229–1246.
Balas, E., S. Ceria, G. Cornuéjols, and N. Natraj. (1996). “Gomory Cuts Revisited.” Operations Research Letters 19(1), 1–9.
Balas, E. and R.G. Jeroslow. (1980). “Strengthening Cuts for Mixed Integer Programs.” European Journal of Operational Research, 4(4), 224–234.
Balas, E. and M. Perregaard. (2003). “A Precise Correspondence Between Lift-And-Project Cuts, Simple Disjunctive Cuts, and Mixed Integer Gomory Cuts for 0–1 Programming.” Mathematical Programming 94(2–3, Ser. B), 221–245.
Bixby, R.E., S. Ceria, C.M. McZeal, and M.W.P. Savelsberg. (1998). “An Updated Mixed Integer Programming Library: MIPLIB 3.0.” Technical Report 98-3, Department of Computational and Applied Mathematics, Rice University.
COmputational INfrastructure for Operations Research, 2004. http://www.coin-or.org/.
Berg, M., M. Kreveld, M. Overmars, and O. Schwarzkopf. (2000). “Computational Geometry: Algorithms and Applications.” Springer-Verlag, Berlin, second, revised edition.
Cornuéjols, G. and Y. Li. (2001). “Elementary Closures for Integer Programs.” Operations Research Letters 28(1), 1–8.
Glover, F. (1973). “Convexity Cuts and Cut Search.” Operations Research 21, 123–134.
Jeroslow, R.G. (1977). “Cutting-Plane Theory: Disjunctive Methods.” In Studies in integer programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics, North-Holland, Amsterdam, vol. 1, pp. 293–330.
Lougee-Heimer, R. (2003). The Common Optimization Interface for Operations Research: Promoting Open-Source Software in the Operations Research Community. IBM Journal of Research and Development 47(1), 57–66. http://[0]//www.research.ibm.com/[0]journal/rd47-1.html.
Nediak, M. and J. Eckstein. (2001). “Pivot, Cut, and Dive: A Heuristic for 0–1 Mixed Integer Programming.” RUTCOR Research Report 53-2001. Rutgers University, Piscataway, NJ.
Owen, J.H. and S. Mehrotra. (2001). “A Disjunctive Cutting Plane Procedure for General Mixed-Integer Linear Programs.” Mathematical Programming 89(3), 437–448.
Raghavachari, M. (1969). “On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints.” Operations Research 17, 680–684.
Rockafellar, R.T. (1970). Convex analysis. Princeton University Press, Princeton, N.J.
Sherali, H.D. and W.P. Adams. (1994). A Hierarchy of Relaxations and Convex Hull Characterizations for Mixed-Integer Zero-One Programming Problems. Discrete Applied Mathematics 52(1), 83–106.
Tuy, H. (1964). “Concave Programming Under Linear Constraints.” Soviet Mathematics pp. 1437–1440.
Zwart, P.B. (1973). “Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms.” Operations Research 21(6), 1260–1266.