Các bài báo kinh điển của KHMT (4)

Năm 2005 là năm đáng tiếc của ngành optimization. Hai người khổng lồ của môn quy hoạch tuyến tính ( linear programming) mất trong vòng hai tuần: giáo sư Leonid Khachiyan mất ngày 29 tháng 4, và giáo sư George Dantzig mất ngày 13 tháng 5. Nhân dịp này, tôi xin đề cập đến các bài báo kinh điển của họ.

Tôi có một lecture note giới thiệu sơ bộ về linear programming ở dạng PDF. Các bạn có thể tham khảo thêm.

Bài báo hôm nay là bài

Dantzig, G. B. Maximization of a linear function of variables subject to linear inequalities, Activity Analysis of Production and Allocation, Koopman (Ed.), Cowles Commission Monograph, 13, John Wiley and Sons, New York, (1951).

của George Dantzig.

Bài báo này có thể xem là khởi nguồn của môn quy hoạch tuyến tính (QHTT) và phương pháp đơn hình (simplex method ). QHTT là bài toán tối ưu các hàm tuyến tính dưới các ràng buộc là một hệ phương trình/bất phương trình tuyến tính.

Giáo sư Alexander Schrijver trong quyển "Theory of Linear and Integer Programming" cho biết nhà toán học Joseph Fourier đã có các ý tưởng khởi điểm của phương pháp đơn hình, và chính George Dantzig cũng cho biết các thảo luận với John von Neumann đã giúp ông phần nào trong khám phá này. Các chi tiết này hoàn toàn không có nghĩa là đóng góp của George Dantzig cho quy hoạch tuyến tính là nhỏ bé. Ta có thể xem Dantzig chính là cha đẻ của môn QHTT.

Năm 1980, tiến sĩ Laci Lovasz từng nói: "nếu ta thống kê bài toán nào lấy nhiều thời gian máy tính nhất (không kể các vấn đề tìm kiếm trong cơ sở dữ liệu), thì có lẽ nó phải là bài toán quy hoạch tuyến tính ".

Ý tưởng căn bản của phương pháp đơn hình (PPĐH) rất đơn giản. Một hệ phương trình hoặc bất phương trình tuyến tính nói chung định nghĩa một đa diện ( polyhedron) trong không gian n chiều:

(ảnh này tôi link từ Mathworld).

Ta cần tìm một điểm trong hoặc trên đa diện này tối ưu một hàm tuyến tính nào đó. Có thể chứng minh được rằng ta chỉ cần tìm điểm tối ưu trong các đỉnh của đa diện (nếu hệ phương trình được viết theo một dạng chuẩn nhất định). Để tìm đỉnh này thì ta bắt đầu từ một đỉnh bất kỳ và di chuyển từ đỉnh này sang đỉnh kia dọc theo các cạnh kề đỉnh đang xét, mỗi lần ta chuyển đến đỉnh ưu việt hơn. Khi không di chuyển được nữa thì ta tìm được đỉnh tối ưu.

Xếp bài báo này vào dạng kinh điển của KHMT thì hơi có vẻ "thấy người sang bắt quàng làm họ", vì quy hoạch tuyến tính và phương pháp đơn hình có ứng dụng cực kỳ rộng rãi ở khắp mọi nơi: kinh tế học, vận trù học, hình học, vân vân. Cần vài chục quyển sách mới nói hết được tầm ảnh hưởng rộng rãi của quy hoạch tuyến tính.

Để biện hộ cho vụ "quàng làm họ" này, tôi sẽ chỉ đề cập ở đây các ứng dụng của quy hoạch tuyến tính trong việc thiết kế các thuật toán xấp xỉ cho các bài toán NP-hard. Ứng dụng của quy hoạch tuyến tính trong KHMT dĩ nhiên là không chỉ giới hạn ở đó.

Như đã viết , ta không hy vọng có thuật toán hiệu quả để giải các vấn đề NP-hard. Một trong những lối thoát là, thay vì tìm nghiệm tối ưu, ta tìm một nghiệm càng gần tối ưu càng tốt trong thời gian đa thức. Đây là đối tượng của nhánh nghiên cứu các giải thuật xấp xỉ ( approximation algorithms).

Rất nhiều các bài toán NP-hard có thể được chuyển về dạng quy hoạch nguyên ( integer programming). Quy hoạch nguyên (QHN) giống như QHTT, chỉ khác ở chỗ các biến bị ràng buộc phải là biến nguyên. Về mặt hình học thì ta phải tìm một điểm tối ưu trong đa diện với các tọa độ nguyên. Có hai cách phổ biến dùng QHTT để tìm nghiệm xấp xỉ một bài toán QHN:

• Tìm đỉnh tối ưu của đa diện (dùng PPĐH chẳng hạn), sau đó bằng một phương pháp làm tròn (rounding) nào đó, ta chuyển đỉnh này về một điểm P trong đa diện với các tọa độ nguyên. Điểm P không nhất thiết là điểm tối ưu của bài toán QHN, nhưng nếu ta làm tròn một cách thông minh thì P sẽ rất gần với điểm tối ưu, và vì thế ta có một xấp xỉ tốt. Cách này thường được gọi là phương pháp nới lỏng và làm tròn (relaxation and rounding).
• Cách thứ hai áp dụng một khái niệm rất sâu sắc trong toán tối ưu, gọi là khái niệm đối ngẫu (duality). Phương pháp primal-dual là một trong những phương pháp hiện đại nhất để thiết kế các thuật toán xấp xỉ.

Gần đây nhất, một bài báo (tôi chưa đọc) với tựa đề "Error correcting codes via linear programming " của Candes, Rudelson, Tao, và Vershynin sẽ xuất hiện ở hội nghị FOCS 2005.

Tôi tạm dừng ở đây, dù mới chỉ chạm đến chóp của tảng băng QHTT khổng lồ mà Dantzig để lại cho chúng ta.