Giải tối ưu bài toán phân hoạch tập hợp kích thước lớn dùng tính toán song song

Tóm tắt

Nhiều ứng dụng thực tế trong những lĩnh vực khác nhau có thể được mô hình dưới dạng bài toán phân hoạch tập hợp. Thay vì thể hiện ứng dụng dưới dạng mô hình gán (assignment model), dạng các biến tương ứng với những ánh xạ từ yêu cầu đến tài nguyên, phương pháp được chọn là tạo ra tất cả những khả năng gán có thể một cách tường minh hoặc không tường minh trong một trình tự có hệ thống. Sau đó, cách tìm nghiệm được quy về bài toán tìm một tập con tốt nhất của chúng mà phủ tất cả những yêu cầu. Một trở ngại chính của bài toán phân hoạch tập hợp là nó thuộc nhóm NP-hard. Vì thế bài báo này sẽ giới thiệu một cách tiếp cận dùng máy tính song song để giải quyết trở ngại này. Một thư viện tuần tự sử dụng những phương pháp và kỹ thuật nâng cao trong thuật toán dựa trên nhánh-và-cắt được chuyển sang dạng song song. Kết quả tính toán trên những dữ liệu từ các ứng dụng thực tế khác nhau cho thấy nghiệm tối ưu của chúng có thể đạt được trong một thời gian tính toán hợp lý nếu sử dụng máy tính song song.