Các bài báo kinh điển của KHMT (4)
Ngô Quang Hưng | 06 tháng 07, 2005 | 
Bản để in
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).
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.
Hi bac Hung,
Tui dang doc blog khoa hoc may tinh, rat thu vi.
Bai nay gioi thieu 1 cach rat ngan gon de hieu ve quy hoach tuyen tinh.
Neu co the, nen chang bac them vao phan cac phuong phap chinh xac de giai bai toan QHN thong qua QHTT nhu branch-and-bound, cutting-planes hay ket hop ca hai la branch-and-cut.
Chuc vui,
Hung
Viết bởi Hung
Dear bác Hùng,
Hay là bác viết một bài review về branch-and-cut rồi gửi cho một trong các bloggers (Xuân Long chẳng hạn), bác ấy sẽ post cho mọi người học hỏi.
Viết bởi Ngô Quang Hưng
Tôi cũng rất thích đọc tiếp về vấn đề này. Nếu bác Hùng viết bài review về branch-and-cut mà nhân tiện viết luôn một chút về column generation (branch-and-price?) thì tốt quá, tôi nghe nói đây là phương pháp độc lập hoặc bổ trợ cho branch-and-cut (row generation) trong việc tightening LP relaxation rất tốt. Có một số MILP encoding của planning problems (ngành tôi học) mà chỉ giải được hiệu quả bằng column generation.
Minh
Viết bởi Đỗ Bình Minh
Vang, toi se viet 1 bai khung roi gui cho cac bac.
Hy vong cac bac se giup do de hoan thien no.
Chuc vui.
Hung
Viết bởi Hung
Cháu đang tìm hiểu về thuật toán branch-and-price.
Các bác có thể viết một bài giới thiệu được không ạ?
Cảm ơn mọi người rất nhiều!
Hello Huy, bài báo này có giới thiệu tốt về branch and price. Khi nào rảnh rỗi rôi sẽ viết một bài giới thiệu.
Em là SV năm thứ nhất,chuyên ngành TOÁN _TIN ;năm đầu tiên học quy hoạc tuyến tính ,em thấy rất khó tìm tài liệu ,nhất là các tài liệu lại ko giải cụ thể, điều này gây rất nhiều bất lợi cho việc học hành của em,em rất mong các thầy và các bạn chỉ cho cách học cũng như các tài liệu tham khảo bổ ích, nhất là các tài liệu trên mạng,.Phần khó nhất trong chương trình chính là phương pháp đơn hình dạng bảng ;em ko hiểu các quy luật ,thời gian ở lớp lại có hạn nên em chưa hỏi được thầy giáo ;mọi người chỉ giùm em ,em xin cảm ơn!
Bài giới thiệu của GS về linear programming (http://www.cse.buffalo.edu/%7Ehungngo/classes/2005/594/notes/LP-intro.pdf) khi em click vào thì bị báo lỗi là “You don’t have permission to access /~hungngo/classes/2005/594/notes/LP-intro.pdf on this server.”. Mong GS cập nhật lại ạ, em xin cảm ơn nhiều !