Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Vấn đề phân hoạch đồ thị có dung lượng nút: Một nghiên cứu tính toán
Tóm tắt
Trong bài báo này, chúng tôi xem xét vấn đề phân hoạch k nút của một đồ thị với các hạn chế dung lượng về tổng trọng số nút trong mỗi tập con của phân hoạch, và mục tiêu là tối thiểu hóa tổng chi phí của các cạnh giữa các tập con của phân hoạch. Dựa trên nghiên cứu về các bất đẳng thức hợp lệ, chúng tôi trình bày một loạt các chiến lược tách biệt cho các bất đẳng thức chu trình, chu trình có tai, cây ba lô và chu kỳ đường-bịt, trong số những thứ khác. Các chiến lược tách biệt, cùng với các chiến lược cơ sở, đã được triển khai trong một quy trình nhánh-và-cắt sử dụng một công thức bao gồm các biến cho các cạnh có chi phí khác không và các biến phân hoạch nút. Kết quả được trình bày cho ba loại vấn đề: các vấn đề phân hoạch đồng đều phát sinh trong các phương pháp phần tử hữu hạn và các vấn đề phân hoạch liên quan đến thiết kế mạch điện tử và thiết kế biên dịch. © 1998 Hiệp hội Lập trình Toán học.
Từ khóa
#phân hoạch đồ thị #dung lượng nút #tối ưu hóa #thuật toán nhánh và cắt #bất đẳng thứcTài liệu tham khảo
D. Applegate, R.E. Bixby, V. Chvátal, W. Cook, Finding cuts in the TSP, DIMACS Technical Report, 1994, pp. 95–05.
F. Barahona, A. Casari, On the magnetisation of the ground states in two dimensional Ising spin glasses, Computer Physics Communications 49 (1988) 417–421.
F. Barahona, M. Grötschel, M. Jünger, G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research 36 (1988) 493–513.
F. Barahona, A. Mahjoub, On the cut polytope, Mathematical Programming 36 (1986) 157–173.
N. Boissin, Optimisation des Fonctions Quadratiques en Variables Bivalentes, Thèse de Doctorat, Conservatoire National des Arts et Métiers, Paris, 1994.
L. Brunetta, M. Conforti, G. Rinaldi, A branch-and-cut algorithm for the resolution of the equicut problem, Working Paper no. 361, IASI-CNR, Rome, 1993.
S. Chopra, M.R. Rao, On the multiway cut polyhedron, Networks 21 (1991) 51–89.
C.E. Ferreira, A. Martin, C.C. de Souza, R. Weismantel, L.A. Wolsey, The node capacitated graph partitioning problems: formulations and valid inequalities, Mathematical Programming 74 (1996) 247–267.
C.E. Ferreira, A. Martin, R. Weismantel, A cutting plane based algorithm for the multiple knapsack problem, SIAM J. on Optimization 6 (1996) 858–877.
C.M. Fiduccia, R.M. Mattheyses, A linear time heuristic for improving network partitionings, in: Proceedings of the 19th Design Automation Conference, Las Vegas, 1982, pp. 175–181.
M. Grötschel, Y. Wakbayashi, A cutting plane algorithm for a clustering problem, Mathematical Programming Series B 45 (1989) 59–96.
S. Holm, M.M. Sorensen, The optimal graph partitioning problem, OR Spektrum 15 (1993) 1–8.
D.S. Johnson, C.R. Aragon, L.A. McGeoch, C. Schevon, Optimization by simulated annealing: an experimental evaluation: Part I, Graph partitioning, Operations Research 37 (1989) 865–892.
E. Johnson, A. Mehrotra, G.L. Nemhauser, Min-cut clustering, Mathematical Programming 62 (1993) 133–152.
M. Jünger, A. Martin, G. Reinelt, R. Weismantel, Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits, Mathematical Programming 63 (1994) 257–279.
W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Systems Technical Journal 49 (2) (1970) 291–307.
T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley, New York, 1990.
M.W. Padberg, G. Rinaldi, A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review 33 (1991) 60–100.
H.L.G. Pina, An algorithm for frontwidth reduction, International Journal on Numerical Methods in Engineering 17 (1981) 1539–1546.
C.C. de Souza, The graph equipartition problem: optimal solutions, extensions and applications, Doctoral Thesis, Faculté des Sciences Appliquées, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1993.
C.C. de Souza, R. Keunings, L.A. Wolsey, O. Zone, A new approach to minimising the frontwidth in finite element calculations, Computer Methods in Applied Mechanics and Engineering 111 (1994) 323–334.
F. Vanderbeck, Decomposition and column generation for integer programs, Doctoral Thesis, Faculté des Sciences Appliquées, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1994.
R. Weismantel, Plazieren von Zellen: Theorie and Lösung eines quadratischen 0–1 Optimierungs-problem, Dissertation, Technische Universität, Berlin, 1992.