Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Mô hình cây giao của cây bao trùm tối thiểu và cây Steiner bị ràng buộc đường kính lẻ
Tóm tắt
Trong một bài báo trước đây, Gouveia và Magnanti (2003) đã nhận thấy rằng các bài toán cây bao trùm tối thiểu và cây Steiner bị ràng buộc đường kính trở nên khó giải hơn khi độ dài đường kính của cây D là số lẻ. Trong bài báo này, chúng tôi cung cấp một cách tiếp cận mô hình hóa thay thế mà xem các bài toán với đường kính lẻ như sự chồng chéo của hai bài toán với đường kính chẵn. Chúng tôi cho thấy cách thắt chặt các mô hình kết quả để phát triển một mô hình với sự thu hoạch lập trình tuyến tính mạnh mẽ hơn. Các khoảng cách lập trình tuyến tính cho mô hình đã được thắt chặt rất nhỏ, thường nhỏ hơn 0.5, và thường thì chỉ bằng một phần ba đến một phần mười các khoảng cách của mô hình tốt nhất trước đây được mô tả trong Gouveia và Magnanti (2003). Hơn nữa, mô hình mới cho phép chúng tôi giải quyết các trường hợp bài toán Euclide lớn mà các phương pháp trước đây không thể giải được.
Từ khóa
#cây bao trùm tối thiểu #cây Steiner #ràng buộc đường kính #lập trình tuyến tính #mô hình hóa.Tài liệu tham khảo
Abdalla, A., N. Deo, and R. Fraceschini. (1999). “Parallel Heuristics for the Diameter-Constrained Minimum Spanning Tree Problem.” Congressus Numeratium, 136, 97–118.
Achuthan, N.R., L. Caccetta, P. Caccetta, and J.F. Geelen. (1992). “Algorithms for the Minimum Weight Spanning Tree with Bounded Diameter Problem.” In P.K.H. Phua, C.M. Wang, W.Y. Yeong, T.Y. Leong, H.T. Loh, K.C. Tan, and F.S. Chou (eds.), Optimization: Techniques and Applications, Vol. 1. World Scientific Publishing, pp. 297–304.
Achuthan, N.R., L. Caccetta, P. Caccetta, and J.F. Geelen. (1994). “Computational Methods for the Diameter Restricted Minimum Weight Spanning Tree Problem.” Australasian Journal of Combinatorics 10, 51–71.
Garey, M. and D. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
Gouveia, L. (1998). “Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints.” INFORMS Journal on Computing, 10, 180–188.
Gouveia, L. and T. Magnanti. (2003). “Network Flow Models for Designing Diameter Constrained Spanning and Steiner Trees.” Networks, 41, 159–173.
Gouveia, L, T. Magnanti, and C. Requejo. (2004). “A 2-Path Approach for Odd-Diameter-Constrained Minimum Spanning and Steiner Trees.” Networks, 44, 254–265.
Magnanti, T. and L. Wolsey. (1996). “Optimal Trees” in “Network Models.” Handbooks in Operations Research and Management Science, 7, 503–615.
Magnanti, T. and R. Wong. (1984). “Network Design and Transportation Planning: Models and Algorithms.” Transportation Science, 18, 1–55.
Woolston, K. and S. Albin. (1988). “The Design of Centralized Networks with Reliability and Availability Constraints.” Computers and Operations Research, 15, 207–217.