Phân Rã Benders Phần II: Cắt Feasibility và Bổ Đề Farkas

Trong phần đầu tiên của loạt bài này, chúng ta đã khám phá phân rã Benders trong bối cảnh đơn giản nhất: bài toán chủ đưa ra quyết định chiến lược, bài toán con đánh giá hậu quả vận hành và mọi lời giải của bài toán chủ đều tạo ra một kế hoạch vận hành khả thi.

Tuy nhiên, nhiều bài toán tối ưu không "hợp tác" như vậy. Bài viết này sẽ giải quyết tình huống quan trọng: khi quyết định từ bài toán chủ khiến bài toán con không thể thực hiện được. Chúng ta sẽ dùng bổ đề Farkas để tạo ra cắt feasibility (feasibility cuts) – một công cụ toán học mạnh mẽ giúp thuật toán học từ thất bại và hội tụ về lời giải tối ưu.

Khi nào cần cắt Feasibility?

Hãy xem xét bài toán định vị cơ sở (facility location) với năng lực sản xuất giới hạn. Bài toán chủ quyết định mở cơ sở nào, còn bài toán con phải phân bổ nhu cầu khách hàng đến các cơ sở đó. Bài toán chủ có thể chọn cơ sở rẻ nhất với chi phí cố định hấp dẫn, nhưng bài toán con lại phát hiện cơ sở đó không đủ năng lực phục vụ tất cả khách hàng.

Trong trường hợp này, nếu chỉ có cắt optimality (optimality cuts), bài toán con không thể cho bài toán chủ biết quyết định đó đắt đến mức nào, bởi vì không tồn tại giải pháp vận hành khả thi. Vấn đề không còn là chi phí vận hành bị đánh giá thấp – mà là quyết định chiến lược đó hoàn toàn không thể thực hiện.

Bổ Đề Farkas: Chứng Chỉ Không Khả Thi

Bổ đề Farkas là một định lý về các lựa chọn thay thế (theorem of alternatives) cho hệ bất phương trình tuyến tính. Nó phát biểu rằng: hoặc hệ ràng buộc tuyến tính có nghiệm, hoặc tồn tại một vector khác chứng minh rằng không có nghiệm nào tồn tại. Cả hai không thể xảy ra đồng thời.

Xét hệ phương trình dạng By ≥ h và y ≥ 0. Nếu hệ này không khả thi, Farkas đảm bảo tồn tại vector r thỏa mãn:

• r ≥ 0
• B^T r ≤ 0
• h^T r > 0

Vector r này được gọi là chứng chỉ không khả thi (Farkas certificate) hay dual ray. Nó cung cấp bằng chứng toán học về lý do tại sao hệ không có nghiệm, và quan trọng hơn, có thể được biến đổi thành một ràng buộc mới cho bài toán chủ.

Điểm mấu chốt: Một cắt feasibility mạnh không chỉ đơn thuần loại bỏ lời giải hiện tại. Nó nắm bắt được lý do cấu trúc của sự thất bại và có thể loại bỏ nhiều quyết định khác gây ra cùng một sự bất khả thi về vận hành.

Ví Dụ Minh Họa: Bài Toán Đồ Chơi

Để hiểu rõ cơ chế, chúng ta xét một bài toán đơn giản. Giả sử cần đáp ứng nhu cầu 6 đơn vị với hai tài nguyên. Tài nguyên 1 có thể cung cấp tối đa 6 đơn vị nhưng chi phí hoạt động cao. Tài nguyên 2 rẻ hơn nhưng chỉ cung cấp được tối đa 4 đơn vị.

Bài toán chủ ban đầu nhận thấy tài nguyên 2 rẻ nhất (chi phí kích hoạt là 1 so với 5 của tài nguyên 1), nên quyết định chỉ kích hoạt tài nguyên 2. Tuy nhiên, khi gửi quyết định này xuống bài toán con, nguyên bài toán con trở nên không khả thi: tài nguyên 2 tối đa chỉ 4 đơn vị, không đủ đáp ứng nhu cầu 6.

Áp dụng bổ đề Farkas cho bài toán con này, ta xây dựng chứng chỉ r = (1, 1, 1) cho các ràng buộc tương ứng. Chuyển chứng chỉ này thành cắt feasibility, ta được ràng buộc:

6x_1 + 4x_2 ≥ 6

Ràng buộc này có ý nghĩa trực quan: tổng năng lực của các tài nguyên được kích hoạt phải đủ lớn để đáp ứng nhu cầu. Lời giải hiện tại x = (0, 1) vi phạm cắt này vì 6(0) + 4(1) = 4 < 6.

Minh họa quá trình phân rã Benders với feasibility cuts

Bài Toán Định Vị Cơ Sở Có Năng Lực Hạn Chế

Sau khi hiểu cơ chế với bài toán đơn giản, chúng ta mở rộng sang bài toán thực tế hơn: bài toán định vị cơ sở có năng lực (capacitated facility location problem).

Khác với mô hình không giới hạn năng lực ở Phần I, việc mở ít nhất một cơ sở không còn đảm bảo mọi khách hàng đều được phục vụ. Bài toán chủ quyết định mở cơ sở nào (x_i), còn bài toán con phải phân bổ luồng hàng (y_ij) từ cơ sở đến khách hàng sao cho đáp ứng nhu cầu và không vượt quá năng lực.

Cấu trúc bài toán con:

• Biến: y_ij – lượng hàng vận chuyển từ cơ sở i đến khách hàng j
• Ràng buộc về nhu cầu: tổng lượng hàng đến khách hàng ≥ nhu cầu
• Ràng buộc về năng lực: tổng lượng hàng từ cơ sở ≤ năng lực × biến mở cơ sở

Khi bài toán chủ chọn mở quá ít cơ sở hoặc chọn sai tổ hợp, bài toán con sẽ không khả thi. Lúc này, chúng ta giải một bài toán phụ (auxiliary problem) để tìm chứng chỉ Farkas, sau đó chuyển thành cắt feasibility.

Triển Khai Python với Pyomo và HiGHS

Chúng ta sẽ triển khai toàn bộ thuật toán bằng Python, sử dụng thư viện pyomo để mô hình hóa và bộ giải nguồn mở HiGHS. Mô hình bao gồm 5 cơ sở tiềm năng và 20 khách hàng, với 57 cung vận chuyển cho phép.

Các bước chính:

1. Khởi tạo bài toán chủ: Chỉ có biến mở cơ sở và biến theta (ước lượng chi phí vận hành), chưa có bất kỳ ràng buộc vận hành nào
2. Giải bài toán chủ: Nhận lời giải sơ bộ về việc mở cơ sở nào
3. Kiểm tra tính khả thi: Cố định lời giải, chạy bài toán phụ Farkas
4. Tạo cắt phù hợp: Nếu không khả thi → tạo cắt feasibility; nếu khả thi → giải bài toán đối ngẫu để tạo cắt optimality
5. Lặp lại: Thêm ràng buộc mới vào bài toán chủ, giải lại, tiếp tục đến khi cận dưới và cận trên hội tụ

# Mã giả cho vòng lặp chính
for iteration in range(max_iterations):
    # Giải bài toán chủ
    solver.solve(master)
    x_bar = {i: round(value(master.x[i])) for i in facilities}
    theta = value(master.theta)
    
    # Kiểm tra tính khả thi bằng bài toán Farkas
    farkas = build_farkas_subproblem(x_bar)
    solver.solve(farkas)
    certificate = value(farkas.Violation)
    
    if certificate > tolerance:
        # Tạo cắt feasibility
        r_solution = {j: value(farkas.r[j]) for j in customers}
        s_solution = {i: value(farkas.s[i]) for i in facilities}
        master.FeasibilityCuts.add(
            sum(capacity[i]*s_solution[i]*master.x[i] for i in facilities)
            >= sum(demand[j]*r_solution[j] for j in customers)
        )
    else:
        # Bài toán con khả thi, tạo cắt optimality
        dual = build_dual_subproblem(x_bar)
        solver.solve(dual)
        # ... thêm cắt optimality vào master

Kết Quả và Ý Nghĩa

Khi chạy toàn bộ thuật toán, chúng ta quan sát thấy sự hội tụ: cận dưới (từ bài toán chủ) tăng dần và cận trên (từ bài toán con) giảm dần, cho đến khi chúng gặp nhau tại lời giải tối ưu. Với bài toán mẫu 5×20, lời giải tối ưu mở 4 cơ sở (F1, F3, F4, F5) với tổng chi phí 14,757 (gồm 9,300 chi phí mở cơ sở và 5,457 chi phí vận chuyển) – trùng khớp với kết quả khi giải bài toán gốc trực tiếp, xác nhận tính đúng đắn của thuật toán.

Sự Khác Biệt Giữa Hai Loại Cắt

Cắt Optimality	Cắt Feasibility
Cho biết quyết định khả thi nhưng đắt hơn dự kiến	Cho biết quyết định hoàn toàn không thể thực hiện
Cải thiện ước lượng chi phí vận hành	Loại bỏ các quyết định không khả thi
Từ nghiệm của bài toán đối ngẫu	Từ chứng chỉ Farkas

Hướng Phát Triển Tiếp Theo

Bài viết này mới chỉ giải quyết trường hợp bài toán con là quy hoạch tuyến tính liên tục. Nếu cố định biến của bài toán chủ mà vẫn còn bài toán con là quy hoạch nguyên hoặc hỗn hợp nguyên, chúng ta không thể dùng đối ngẫu LP để tạo cắt. Đây là lúc cần đến Logic-Based Benders Decomposition (LBBD) – phân rã Benders dựa trên logic, sử dụng cấu trúc và logic của bài toán con để truyền thông tin về bài toán chủ, thay vì dựa vào đối ngẫu tuyến tính.

Bài tiếp theo của loạt bài sẽ giới thiệu LBBD qua bài toán lập lịch trên máy song song với thời gian thiết lập phụ thuộc trình tự – một bài toán khó xuất hiện nhiều trong sản xuất và chế tạo.

---

Toàn bộ mã nguồn và dữ liệu sử dụng trong bài viết có thể tìm thấy trên kho GitHub kèm theo. Hy vọng bài viết giúp bạn hiểu rõ hơn về cắt feasibility và bổ đề Farkas.