- Lập trình tuyến tính nguyên (MILP) đã trở thành công cụ cốt lõi trong nhiều lĩnh vực công nghiệp
- Nhờ hiệu quả tính toán của các solver hiện đại được cải thiện, ngay cả những bài toán trước đây khó giải cũng có thể nhanh chóng tìm được nghiệm tối ưu
- Bài viết này tập trung giải thích những phát triển thực tiễn gần đây của các phương pháp giải MILP và các cải thiện về hiệu năng tính toán
- Các phương pháp chính được giới thiệu gồm branch-and-cut, phân rã Dantzig-Wolfe, phân rã Benders
- Các thách thức liên tục của lĩnh vực MILP và cơ hội cho nghiên cứu tương lai cũng được tóm lược
Giới thiệu
- Lập trình tuyến tính nguyên hỗn hợp (MILP) là một công cụ thiết yếu trong nghiên cứu tác nghiệp và đã được ứng dụng thành công trong nhiều lĩnh vực công nghiệp khác nhau
- Các solver MILP hiện đại nay có thể tìm nghiệm tối ưu cho cả những bài toán quy mô lớn mà trước đây là bất khả thi chỉ trong vài giây
- Nhờ đó, việc ứng dụng MILP đã được mở rộng sang nhiều lĩnh vực như vận tải, chuỗi cung ứng, quản lý doanh thu, tài chính, viễn thông, sản xuất
- Tuy vậy, vẫn còn những vấn đề chưa được giải quyết và các thách thức mới, nên nghiên cứu về MILP vẫn đang tiếp tục diễn ra sôi nổi
Tổng quan nội dung chính
- Bài báo này phân tích những tiến bộ gần đây của các phương pháp giải MILP và các cải thiện hiệu năng thực tiễn, tập trung vào việc mỗi kỹ thuật đã thực sự đóng góp thế nào cho việc nâng cao hiệu năng tính toán
- Trong khối lượng tài liệu đồ sộ, bài viết ưu tiên xem xét các nghiên cứu dựa trên thực nghiệm tính toán
- Nội dung được tổ chức quanh ba lĩnh vực cốt lõi của phương pháp giải MILP
- Phương pháp Branch-and-Cut: cách giải MILP tiêu biểu kết hợp kỹ thuật phân nhánh nút và kỹ thuật cutting plane
- Phân rã Dantzig-Wolfe: cách tiếp cận phân rã chia bài toán quy mô lớn thành các bài toán con nhỏ hơn để xử lý hiệu quả
- Phân rã Benders: phương pháp giảm gánh nặng tính toán trong các cấu trúc phức tạp bằng cách tách biến và ràng buộc rồi giải lặp lại
Kết luận: thách thức và triển vọng tương lai
- Phần cuối bài báo nhìn lại các thách thức còn tồn tại của MILP và các cơ hội nghiên cứu trong tương lai
- Những bài toán công nghiệp thực tế ngày càng phức tạp, quy mô dữ liệu mở rộng và giới hạn hiệu năng của solver sẽ là các chủ đề nghiên cứu quan trọng trong thời gian tới
- Trong tương lai, lĩnh vực MILP được kỳ vọng sẽ tiếp tục phát triển cùng với tiến bộ thuật toán, sự phát triển của phần cứng và sự mở rộng của các miền ứng dụng mới
1 bình luận
Ý kiến trên Hacker News
Có người bày tỏ thắc mắc liệu ai đó có thể giải thích vì sao các solver ILP thương mại như Gurobi lại vượt trội hơn hẳn so với solver miễn phí/mã nguồn mở, liệu điều đó là do độ khó nội tại của ILP, hay vì solver tốt nhất thực chất là tập hợp khổng lồ các heuristic cho những bài toán con cụ thể, nên nhìn chung các chiến lược “tốt” vẫn chưa có trong miền công cộng
Có nhắc rằng các solver thương mại phần lớn làm việc rất sát với khách hàng để triển khai các kỹ thuật tăng tốc chuyên biệt theo từng bài toán, sở hữu know-how tích lũy suốt 10~20 năm; trong lĩnh vực MILP, họ tận dụng các heuristic tốt (chọn điểm khởi đầu cho branch-and-bound, cắt tỉa cây hiệu quả) và các custom cut (loại bỏ nghiệm bộ phận một cách hiệu quả). Ngoài ra, các nhà nghiên cứu OR nếu tự chọn bài toán và tự viết custom cut cùng heuristic thì cũng thường đạt kết quả tốt hơn cả solver thương mại; tuy nhiên các công ty làm solver thuê đội ngũ tiến sĩ để triển khai điều đó một cách ổn định và theo dõi cải tiến trên dữ liệu bài toán thực tế từ rất nhiều khách hàng.
Solver thương mại có thể đầu tư lượng thời gian và tài nguyên khổng lồ vào việc tinh chỉnh khả năng giải vì có khách hàng thực sự quan tâm và sẵn sàng hỗ trợ; ngoài heuristic còn bao gồm cả quá trình nhận diện các bài toán con đơn giản hoặc bài toán xấp xỉ rồi phản hồi kết quả đó vào bài toán tổng thể. Solver mã nguồn mở bị giới hạn vì (1) rào cản gia nhập để phát triển optimizer hiện đại là rất cao (ít người giỏi cả toán lẫn lập trình), (2) nếu có trình độ như vậy thì thường sẽ theo đuổi sự nghiệp kiếm được nhiều tiền hơn, (3) trong cấu trúc mã nguồn mở, khách hàng gần như không cung cấp các ca cải tiến, dữ liệu hiệu năng hay profiling để phục vụ tối ưu hóa. Ngoại lệ có những trường hợp như SNOPT, mang tính thương mại nhưng phát triển thương mại không theo lối truyền thống; còn solver học thuật thì thường tập trung vào một lĩnh vực ứng dụng cụ thể nên thiếu tính đa dụng. Ở các lĩnh vực khác đôi khi có các công ty lớn như Google mua lại hoặc hỗ trợ để nuôi hệ sinh thái, nhưng trong mảng solver thì chi phí đầu tư để xây toàn bộ stack ngay từ đầu là quá lớn.
Solver thương mại có thể xác định được thủ thuật nào sẽ hiệu quả cho từng bài toán thông qua vô số mẹo và cơ chế phát hiện mẫu; nếu hiểu rất rõ cấu trúc bài toán thì có thể còn làm nhanh hơn solver thương mại, nhưng với bài toán ngẫu nhiên thì gần như không có cửa thắng.
Có ý kiến cho rằng “solver = tập hợp nhiều heuristic cho các bài toán con chuyên biệt”, và chỉ ra rằng với các bài toán NP-Hard thì gần như mọi thứ đều có cấu trúc như vậy; ILP tương đương SAT nên lập luận tương tự cũng áp dụng được.
Quy mô thương mại và vấn đề tốc độ cũng rất quan trọng: đa số các công ty giao dịch định lượng chạy những bài toán tối ưu hóa cực lớn với tần suất cao nhất có thể, trong khi solver mã nguồn mở thường hoặc là không giải nổi, hoặc gặp lỗi hết bộ nhớ; khoảng cách lớn đến mức đó.
Có người hồi tưởng trải nghiệm dùng thư viện IBM ILOG MILP để xây công cụ phân bổ tài nguyên: nếu giải cùng một loại bài toán cách đây 20 năm thì đến giờ bài toán hiện nay giải trong 5 phút khi đó có lẽ vẫn còn đang chạy. Hiệu năng máy tính đã tăng gấp nghìn lần, thuật toán cũng tốt hơn gấp nghìn lần, tổng cộng thành cải thiện một triệu lần; đây là câu chuyện đáng suy ngẫm khi dự đoán tương lai. Nhân tiện, “tài nguyên” ở đây là kim cương.
Có người thắc mắc trên thực tế các công cụ này được dùng như thế nào, liệu tối ưu số cuối cùng có thường bị giới hạn bởi các vấn đề quen thuộc của cách tiếp cận dựa trên dữ liệu (độ tin cậy, vấn đề dữ liệu, v.v.) nên rốt cuộc người quan trọng vẫn quyết định bằng “cảm giác” hay không.
Có người cho biết công ty họ dùng solver trên toàn bộ stack: tối ưu lịch cho pin gia dụng và EV, tối ưu lịch tốt nhất cho danh mục hàng trăm nghìn hộ gia đình, rồi cả giao dịch danh mục đó cũng dùng solver; ngay cả giá điện spot ở EU cũng được quyết định bằng một lần chạy của solver khổng lồ duy nhất tên là Euphemia. Nói chung, ở đâu có mục tiêu tối ưu rõ ràng gắn trực tiếp với tiền thì ở đó solver được dùng rất rộng rãi.
Một ví dụ ứng dụng thực tế tại công ty FMCG: (1) lập kế hoạch tuyến đường cho nhân viên bán hàng và giao hàng, (2) lên lịch máy móc, nhân lực, vật tư cho sản xuất, (3) xác định mức tồn kho phù hợp tại kho và trung tâm phân phối; do khó khăn trong dự báo nhu cầu nên vẫn chưa thể tự động hóa hoàn toàn.
Chia sẻ các liên kết case study đáng tham khảo: Gurobi case studies, CPLEX case studies, Hexaly (trước đây là LocalSolver) case studies
Có người nói nghe bảo Gurobi khá đắt nên hỏi liệu có thể chia sẻ thông tin giá thực tế hay không.
Giá cụ thể không được công khai, nhưng nếu mục đích là thực hành MIP thì khuyến nghị không cần mua solver thương mại như XPRESS/Gurobi/CPLEX mà có thể dùng giấy phép sinh viên miễn phí hoặc các solver MIP mã nguồn mở miễn phí cho mục đích phi thương mại, ví dụ: HiGHS, SCIP
Theo những gì có người nghe được thì cách định giá ở mức “gọi điện để thương lượng”, và thực tế là nhìn vào việc khách hàng kiếm được bao nhiêu tiền rồi định mức giá tương ứng.
Có nhấn mạnh rằng nó vẫn rẻ hơn rất nhiều so với những quyết định chậm chạp và kém tối ưu; với bài toán nhỏ thì solver miễn phí (như GLPK) là đủ, nhưng với các bài toán lớn trong môi trường kinh doanh thì gần như không thể có đáp án đúng hạn, vì vậy solver cao cấp hoàn toàn xứng đáng với chi phí.
Có người nhớ khoảng 10 năm trước mức giá cỡ 100.000 USD cho giấy phép dùng trên vài server, dù không nhớ chính xác giới hạn số người dùng hay số server; trong ngành thì mức giá đó được xem là hoàn toàn xứng đáng.
Gurobi cũng cung cấp dịch vụ đám mây tính phí theo giờ, và giấy phép phi học thuật thì rất đắt.
Có người từng tự triển khai Gomory cutting hyperplane vào thập niên 1990 và ngạc nhiên trước mức độ tiến bộ của lĩnh vực này. Ngày xưa giải một bài toán LP mất hai tháng, giờ chỉ cần 1 giây. Trong nghiên cứu của Bixby có báo cáo rằng từ 1990 đến 2020, CPLEX và Gurobi đã nhanh hơn gần 4 triệu lần, không phụ thuộc vào hiệu năng máy.
Từ 1988 đến 2004, phần cứng nhanh hơn 1.600 lần, solver LP nhanh hơn 3.300 lần; ngay thời điểm đó mức tăng tốc cộng dồn đã vượt 5 triệu lần. Từ 2001 đến 2020, các solver MILP thương mại cũng nhanh hơn hơn 1.000 lần (thuật toán đóng góp 50, máy tính đóng góp 20). Có người tò mò nếu gom các dữ liệu tăng tốc theo từng lĩnh vực như vậy rồi tách riêng phần đóng góp của thuật toán và máy tính thì sẽ ra sao; trong lĩnh vực compiler cũng có kết quả như “định luật Proebsting”, cho rằng cứ 18 năm thì tiến bộ compiler mang lại hiệu quả tương đương việc tăng gấp đôi sức mạnh tính toán.
Có cảm giác các cách tiếp cận ML/AI hóa ra lại không được dùng nhiều cho loại bài toán này. Có các bài báo thử dùng RL/GNN cho bài toán quy mô nhỏ, nhưng rốt cuộc có vẻ mua giấy phép Gurobi vẫn là lựa chọn tốt nhất. Gần đây có người làm tối ưu scheduling cũng xem các ví dụ RL nhưng hiệu năng thực tế chưa đạt; với bài toán lớn thì thuật toán tiến hóa là tốt nhất. Cuối cùng, nếu có thể mô hình hóa bài toán tốt thì cách tiếp cận dựa trên OR dường như vẫn hiệu quả nhất.
Tùy vào loại bài toán. Ví dụ, quyết định bật/tắt nhà máy điện (unit commitment) cực kỳ phức tạp, nhưng solver MILP có thể nhanh chóng tìm nghiệm tối ưu toàn cục; thuật toán di truyền thì không có gì đảm bảo thoát được local minima và tốc độ chạy cũng có thể chậm. Mạng nơ-ron cũng luôn cho nghiệm dưới tối ưu.
SAT là một bài toán GOFAI truyền thống, và hoàn toàn có thể viết SAT solver bằng mọi ngôn ngữ trong họ ML/AI, nên thực ra cách tiếp cận “ML/AI” không phải là không áp dụng được.
Có bình luận rằng nên thêm ký hiệu pdf vào tiêu đề.
Liên kết đó không dẫn tới pdf mà là tới phần abstract.
Có thể thêm trực tiếp tham chiếu pdf của bài báo: https://inria.hal.science/hal-04776866v1/document
Có ý kiến cho rằng integer linear programming trông không có vẻ quá phức tạp.
Graph 3-coloring (G3C) thuộc NP và cũng là NP-Hard nên là NP-Complete, và đã có kết quả cho thấy nếu giải được ILP tổng quát thì cũng giải được G3C. SAT cũng là NP-Complete; nếu giải được SAT thì giải được G3C, và nếu giải được G3C thì có thể giải được integer factorization (FAC). FAC không phải NPC nhưng cực kỳ quan trọng trong môi trường tính toán hiện nay. Nói cách khác, nếu giải được ILP tùy ý thì có thể phá vỡ các thuật toán mật mã chủ chốt, từ đó suy ra ILP là bài toán rất khó. Điều khiến nhiều người dễ nhầm là với các bài toán NPC, các instance ngẫu nhiên thường lại khá dễ giải; tỷ lệ instance thực sự khó thậm chí còn giảm khi kích thước bài toán tăng lên.
Travelling Salesperson Problem (TSP) cũng có thể được mã hóa thành ILP, cho thấy độ khó đáng kể của nó.
Ta phải tìm các số nguyên thỏa mãn điều kiện tốt nhất; trông có vẻ giống số thực nhưng về bản chất hoàn toàn khác. Không có lời giải tổng quát, chỉ có các heuristic (rất tốt) cho những trường hợp đặc biệt.
Đây là bài toán khó hơn linear programming.
Hoặc có thể xem đây là một bài toán rất thực tế.