Tối ưu hoá 4 — Solver & thực hành mô hình hoá

Từ mô hình trên giấy tới nghiệm chạy được

Ba bài trước dạy cách mô hình hoá: dịch bài toán kinh doanh thành biến, mục tiêu, ràng buộc — LP, MILP. Nhưng một mô hình viết đẹp trên giấy chưa mang lại quyết định nào. Bài này khép vòng: làm sao để một chương trình máy tính nhận mô hình đó và trả về con số phân bổ cụ thể, trên dữ liệu thật của ngân hàng, chạy được định kỳ.

Có hai mảnh ghép cần phân biệt rạch ròi, và người mới hay nhầm:

• Solver — phần mềm giải bài toán tối ưu. Nó nhận một mô hình đã chuẩn hoá (ma trận hệ số, vector mục tiêu, các ràng buộc) và chạy thuật toán (Simplex, interior point, branch-and-bound...) để trả về nghiệm tối ưu cùng trạng thái. Solver là "động cơ".
• Modeling layer (lớp mô hình hoá / modeling API) — thư viện giúp bạn viết mô hình bằng ngôn ngữ lập trình quen thuộc (thường là Python), gần với cách bạn nghĩ về bài toán, rồi tự động dịch sang định dạng solver hiểu. Modeling layer là "vô-lăng và cần số".

Sự tách bạch này cực kỳ quan trọng: bạn viết mô hình một lần bằng PuLP, và có thể đổi solver bên dưới (CBC → HiGHS → Gurobi) chỉ bằng một tham số, không viết lại mô hình. Chọn công cụ vì thế là chọn cả hai lớp cho phù hợp bài toán và túi tiền.

1. Solver là gì và phân loại

Về bản chất, solver là một chương trình chuyên biệt cài đặt các thuật toán tối ưu ở mức tối ưu hoá kỹ thuật cao (số học ma trận thưa, xử lý số ổn định, song song hoá). Bạn không nên tự viết Simplex cho việc thật — solver trưởng thành nhanh hơn code tự viết hàng trăm lần và xử lý đúng các ca số học hóc búa.

Phân loại solver theo lớp bài toán giải được và mô hình cấp phép:

Điểm cần nắm để chọn:

• Mã nguồn mở (CBC, HiGHS, SCIP): miễn phí, không lo bản quyền, tích hợp thoải mái vào sản phẩm. Đủ tốt cho phần lớn bài toán vừa và nhỏ. Với MILP lớn, chúng có thể chậm hoặc không đóng được khe tối ưu (gap) trong thời gian cho phép.
• Thương mại (Gurobi, CPLEX, Xpress): có thể nhanh hơn OSS hàng chục tới hàng trăm lần trên bài MILP lớn nhờ tiền xử lý (presolve), cắt mặt (cutting planes) và heuristic tinh vi. Đổi lại là chi phí bản quyền đáng kể. Cả ba đều có bản học thuật miễn phí cho nghiên cứu — hữu ích để học và benchmark, nhưng không dùng cho sản xuất thương mại.

Nguyên tắc thực dụng ở ngân hàng: bắt đầu với CBC/HiGHS. Chỉ khi bài toán thật lớn tới mức OSS không giải kịp cửa sổ thời gian batch (ví dụ tối ưu phân bổ toàn danh mục hàng đêm) mới cân nhắc đầu tư solver thương mại — quyết định dựa trên benchmark thực, không dựa trên đồn đoán.

2. Modeling layer — viết mô hình bằng Python

Modeling layer cho phép bạn diễn đạt mô hình gần với toán học, tách khỏi solver. Các lựa chọn phổ biến:

Cách chọn nhanh:

• Bài LP/MILP thẳng thớm, cần lên nhanh → PuLP (dễ nhất) hoặc Python-MIP.
• Bài lập lịch / phân công / tổ hợp nhiều ràng buộc logic → OR-Tools CP-SAT (xem bài 6).
• Bài lồi/phi tuyến như tối ưu danh mục có ma trận hiệp phương sai → CVXPY (xem bài 5).
• Cần biểu đạt mô hình phức tạp, nhiều solver, cả phi tuyến → Pyomo.

Trong loạt bài này ta dùng PuLP làm ngôn ngữ minh hoạ vì nó gần toán nhất và ít rào cản.

3. Quy trình thực hành 6 bước

Giải một bài tối ưu thật không phải "gọi solver rồi xong". Đây là quy trình end-to-end mà một cán bộ dữ liệu ngân hàng nên theo, mỗi bước có cạm bẫy riêng.

Bước 1 — Hiểu và phát biểu bài toán

Trước khi viết dòng code nào, trả lời bằng lời: ta điều khiển được gì (biến), muốn tối đa/tối thiểu gì (mục tiêu), bị bó buộc bởi gì (ràng buộc)? Nói chuyện với người nghiệp vụ để bắt đúng ràng buộc "ngầm" — ví dụ trần rủi ro theo quy định nội bộ, tỷ trọng tối thiểu cho một phân khúc. Bỏ sót một ràng buộc → nghiệm đẹp trên máy nhưng không dùng được.

Bước 2 — Mô hình hoá bằng PuLP

Ví dụ nhỏ đầy đủ để chạy được: phân bổ vốn 300 tỷ cho 3 sản phẩm (Tiêu dùng, Thẻ, Mua nhà) tối đa lợi nhuận biên, có trần hấp thụ mỗi sản phẩm và trần tỷ trọng nhóm rủi ro cao.

# Minh hoạ mô hình MILP-nhẹ bằng PuLP (Python — KHÔNG chạy trên sandbox SQL)
from pulp import (LpProblem, LpMaximize, LpVariable, lpSum,
                  value, LpStatus, PULP_CBC_CMD)

# --- Dữ liệu đầu vào (bước 3 sẽ lấy từ SQL, đây minh hoạ) ---
loi_nhuan_bien = {"TD": 0.090, "TTD": 0.070, "MN": 0.045}   # /tỷ vốn
tran_hap_thu   = {"TD": 150,   "TTD": 100,   "MN": 250}      # tỷ
TONG_VON  = 300          # tỷ khả dụng
TRAN_RUIRO_CAO = 0.40    # TD (rủi ro cao) tối đa 40% tổng giải ngân

sp = list(loi_nhuan_bien)                 # ["TD","TTD","MN"]

# --- Khai báo mô hình ---
prob = LpProblem("phan_bo_von_quy", LpMaximize)
x = {s: LpVariable(f"von_{s}", lowBound=0, upBound=tran_hap_thu[s]) for s in sp}

# Mục tiêu: tối đa tổng lợi nhuận biên
prob += lpSum(loi_nhuan_bien[s] * x[s] for s in sp), "tong_loi_nhuan"

# Ràng buộc
prob += lpSum(x[s] for s in sp) <= TONG_VON,               "tran_tong_von"
prob += x["TD"] <= TRAN_RUIRO_CAO * lpSum(x[s] for s in sp), "tran_rui_ro_cao"

# --- Giải: đặt time limit & gap để an toàn ---
prob.solve(PULP_CBC_CMD(msg=False, timeLimit=30, gapRel=0.01))

# --- Bước 4: đọc trạng thái ---
print("Trang thai:", LpStatus[prob.status])   # Optimal / Infeasible / ...
if LpStatus[prob.status] == "Optimal":
    for s in sp:
        print(f"  {s}: {value(x[s]):.1f} ty")
    print("Loi nhuan bien =", round(value(prob.objective), 3))

Nghiệm tối ưu ở đây: dồn tối đa vào sản phẩm lời nhất trong giới hạn trần rủi ro và trần hấp thụ — TD bị chặn bởi trần 40% và trần hấp thụ 150, phần còn lại chảy sang TTD rồi MN. Con số cụ thể phụ thuộc dữ liệu; điểm mấu chốt là mô hình được viết một lần, chạy lại được với bất kỳ bộ dữ liệu nào.

Bước 3 — Nạp dữ liệu đầu vào từ warehouse

Đây là bước hay bị xem nhẹ nhưng quyết định độ tin cậy. Các hệ số loi_nhuan_bien, tran_hap_thu, TONG_VON không được gõ tay — chúng phải rút từ dữ liệu thật của kho dữ liệu (transactions, accounts...) và cập nhật mỗi kỳ. Về chuẩn bị dữ liệu bằng SQL, xem đưa mô hình vào sản xuất.

Ví dụ chuẩn bị giới hạn nguồn vốn khả dụng — tổng số dư khả dụng theo loại tiền, làm đầu vào cho vế phải TONG_VON:

-- ▶ Chạy được
SELECT
    a.currency,
    COUNT(DISTINCT a.customer_id)                 AS so_khach,
    ROUND(SUM(a.balance)::numeric, 2)             AS tong_so_du
FROM accounts a
JOIN customers c ON c.id = a.customer_id
GROUP BY a.currency
ORDER BY tong_so_du DESC;

Ví dụ chuẩn bị hệ số hiệu quả theo nhóm — ước lượng lợi nhuận/chi phí ròng theo nhóm khách (city) từ dòng tiền giao dịch 12 tháng gần nhất, làm đầu vào cho vector mục tiêu c và các trần theo nhóm:

-- ▶ Chạy được
WITH dong_tien AS (
    SELECT
        a.customer_id,
        SUM(CASE WHEN t.kind = 'credit' THEN t.amount ELSE 0 END) AS tong_vao,
        SUM(CASE WHEN t.kind = 'debit'  THEN t.amount ELSE 0 END) AS tong_ra,
        COUNT(*)                                                  AS so_gd
    FROM transactions t
    JOIN accounts a ON a.id = t.account_id
    WHERE t.created_at >= NOW() - INTERVAL '12 months'
    GROUP BY a.customer_id
)
SELECT
    c.city                                                  AS nhom_kh,
    COUNT(*)                                                AS so_khach,
    ROUND(SUM(d.tong_vao)::numeric, 2)                      AS tong_dong_vao,
    ROUND(SUM(d.tong_ra)::numeric, 2)                       AS tong_dong_ra,
    ROUND((SUM(d.tong_vao) - SUM(d.tong_ra))::numeric, 2)   AS rong,
    ROUND(AVG(d.so_gd)::numeric, 1)                         AS gd_tb
FROM dong_tien d
JOIN customers c ON c.id = d.customer_id
GROUP BY c.city
HAVING SUM(d.tong_vao) - SUM(d.tong_ra) <> 0
ORDER BY rong DESC;

Kết quả hai truy vấn này (số dư khả dụng, dòng tiền ròng theo nhóm) là các bảng số đưa thẳng vào Python để lấp vào TONG_VON, loi_nhuan_bien, tran_hap_thu. Chuẩn bị dữ liệu sạch, đúng đơn vị ở bước này quan trọng ngang việc mô hình hoá.

Bước 4 — Giải và đọc trạng thái

Solver trả về trạng thái, và bạn bắt buộc kiểm tra trước khi tin nghiệm:

Với MILP, gặp time-limit là bình thường trên bài lớn: solver có nghiệm tốt nhưng chưa đóng được gap. Đọc gapRel — nếu khe còn 0.5% mà nghiệp vụ chấp nhận được, dừng là hợp lý.

Bước 5 — Trích và diễn giải nghiệm cho nghiệp vụ

Nghiệm thô (TD = 120, TTD = 100, MN = 80) chưa có giá trị cho lãnh đạo. Phải dịch ngược sang ngôn ngữ quyết định: "quý này nên rót 120 tỷ vào Tiêu dùng, kịch trần rủi ro cho phép; 100 tỷ vào Thẻ; 80 tỷ vào Mua nhà; lợi nhuận biên kỳ vọng X tỷ". Kèm shadow price của ràng buộc tổng vốn để trả lời "huy động thêm 1 tỷ vốn đáng giá bao nhiêu" (xem duality trong bài LP). Đây là phần biến kết quả toán thành khuyến nghị.

Bước 6 — Kiểm định và đưa vào quyết định

Trước khi cam kết vốn thật: sanity check nghiệm (tổng có đúng ngân sách? có vi phạm ràng buộc ngầm nào không?), chạy phân tích độ nhạy với vài kịch bản hệ số, và đối chiếu với phán đoán chuyên gia. Nghiệm tối ưu là đầu vào cho quyết định, không thay thế hội đồng. Sau khi được duyệt, đưa vào vòng lặp: mỗi kỳ nạp dữ liệu mới (bước 3) và chạy lại.

4. Mẹo thực chiến

Những điều solver không tự lo, bạn phải lo:

• Đơn vị nhất quán. Chọn một đơn vị (tỷ đồng, hay đồng) và dùng xuyên suốt. Trộn tỷ với đồng trong cùng mô hình là nguồn lỗi số 1.
• Scaling (co giãn hệ số). Nếu hệ số trải quá rộng — có số cỡ 1e-3 bên cạnh số cỡ 1e9 — solver dễ mất ổn định số học. Chia tỷ lệ cho các con số về cùng bậc độ lớn (ví dụ đổi đồng sang tỷ) giúp giải nhanh và ổn định hơn.
• Time limit và gap limit. Luôn đặt timeLimit và gapRel cho bài MILP để không treo vô hạn. Thà lấy nghiệm cách tối ưu 1% trong 30 giây còn hơn chờ nghiệm hoàn hảo 2 giờ.
• Warm start. Khi chạy lại mô hình với dữ liệu chỉ đổi nhẹ (batch hàng ngày), cho solver nghiệm cũ làm điểm khởi đầu — nhiều solver (Gurobi/CPLEX, một số qua OR-Tools) tăng tốc đáng kể nhờ warm start.
• Ràng buộc mềm và phạt (soft constraint / penalty). Ràng buộc "nên có nhưng không cứng" (ví dụ: ưu tiên tỷ trọng bán lẻ ≥ 60%, nhưng vi phạm được nếu cần) → không đặt thành ràng buộc cứng (dễ gây infeasible), mà đưa vào mục tiêu với biến vi phạm bị phạt: max lợi_nhuận − M·thiếu_hụt. Điều này giữ mô hình luôn có nghiệm.
• Gỡ infeasible bằng cách nới ràng buộc. Khi solver báo INFEASIBLE, đừng đoán mò. Kỹ thuật: thêm biến chùng (slack) có phạt vào từng ràng buộc nghi ngờ, giải lại; ràng buộc nào có slack > 0 chính là ràng buộc gây mâu thuẫn. Nhiều solver cũng có tính năng tính IIS (tập ràng buộc mâu thuẫn nhỏ nhất) để chỉ đích danh.

5. Tích hợp vào hệ thống

Một mô hình tối ưu chỉ tạo giá trị khi chạy đều đặn trên dữ liệu mới, không phải một lần trong notebook. Hai hình thái triển khai:

• Batch định kỳ. Phổ biến nhất ở ngân hàng. Một job (điều phối bởi Airflow — xem tổng quan Airflow) chạy theo lịch: (1) truy vấn dữ liệu đầu vào từ warehouse bằng SQL, (2) dựng mô hình PuLP, (3) gọi solver, (4) ghi nghiệm và trạng thái vào bảng kết quả, (5) cảnh báo nếu INFEASIBLE hoặc gap vượt ngưỡng. Ví dụ: tối ưu phân bổ hạn mức tín dụng toàn danh mục chạy hàng đêm.
• Service (dịch vụ theo yêu cầu). Khi cần nghiệm tức thời cho một truy vấn (ví dụ: gợi ý phân bổ khi cán bộ nhập tham số qua giao diện), đóng gói mô hình sau một API. Lưu ý solver có thể mất giây tới phút, nên với bài nặng vẫn nên chạy bất đồng bộ và trả kết quả sau.

Dù batch hay service, hãy log lại: phiên bản mô hình, dữ liệu đầu vào (hoặc hash của nó), trạng thái, thời gian giải, giá trị mục tiêu. Khi nghiệm gây tranh cãi, log cho phép tái lập chính xác — quan trọng trong môi trường ngân hàng có kiểm toán.

6. Solver chính xác vs heuristic — khi nào dùng gì

Không phải bài nào cũng đáng dùng solver "chính xác" (exact — có bảo đảm tối ưu):

• Dùng solver chính xác khi: bài toán vào được lớp LP/MILP/CP mà solver giải kịp thời gian; bạn cần chứng minh tối ưu hoặc cận sai lệch (gap) rõ ràng; các quyết định có giá trị lớn cần biện minh chặt chẽ (phân bổ vốn, hạn mức). Đây là mặc định nên thử trước.
• Dùng heuristic / metaheuristic (tham lam, tabu search, di truyền, simulated annealing) khi: bài toán quá lớn hoặc quá phi tuyến/phi cấu trúc để solver chính xác giải kịp; chỉ cần nghiệm "đủ tốt" nhanh; không đòi hỏi chứng minh tối ưu. Đánh đổi: mất bảo đảm tối ưu, nghiệm có thể kém xa mà không biết kém bao nhiêu.

Lời khuyên: luôn thử solver chính xác trên OSS trước. Chỉ chuyển sang heuristic khi có bằng chứng nó không kịp — và ngay cả khi dùng heuristic, hãy giải một phiên bản nhỏ bằng solver chính xác để có mốc so sánh chất lượng.

Use case thực tế

Bối cảnh: pipeline tối ưu phân bổ hạn mức sản phẩm hàng tuần tại NCB

Khối Kinh doanh cần phân bổ quỹ vốn giải ngân 300 tỷ/tuần cho 3 nhóm sản phẩm sao cho tối đa lợi nhuận biên, dưới ràng buộc rủi ro. Trước đây làm bằng Excel thủ công, mất nửa ngày và không tối ưu. Ta dựng pipeline tự động:

1. Thứ Hai 02:00 — Airflow kích một job. Bước đầu chạy hai truy vấn SQL (mục 3) trên kho dữ liệu để lấy: tổng số dư khả dụng theo loại tiền (→ ngân sách vốn TONG_VON) và dòng tiền ròng theo nhóm khách (→ ước lượng lợi nhuận biên và trần hấp thụ mỗi nhóm).
2. Dựng mô hình PuLP như mục 2 với hệ số vừa lấy; đặt timeLimit=30, gapRel=0.01.
3. Giải bằng CBC. Với quy mô 3 nhóm, bài giải xong dưới 1 giây, trạng thái Optimal. (Nếu mở rộng ra hàng chục sản phẩm × phân khúc, vẫn nằm trong tầm CBC/HiGHS.)
4. Kiểm trạng thái: nếu Infeasible (ví dụ tổng trần hấp thụ < ngân sách bắt buộc giải ngân), job gửi cảnh báo cho cán bộ thay vì âm thầm cho nghiệm sai.
5. Ghi kết quả vào bảng phan_bo_von_tuan: mỗi nhóm bao nhiêu tỷ, lợi nhuận biên kỳ vọng, và shadow price của ràng buộc tổng vốn (cho biết huy động thêm 1 tỷ đáng bao nhiêu — đầu vào cho Khối Nguồn vốn).
6. Cán bộ nghiệp vụ nhận báo cáo, sanity-check, điều chỉnh nếu có yếu tố ngoài mô hình, rồi phê duyệt. Thời gian từ nửa ngày xuống còn vài phút xem xét.

Kết quả: quyết định phân bổ nhất quán, tái lập được, có log kiểm toán, và mỗi tuần tự cập nhật theo dữ liệu mới nhất — đúng tinh thần đưa mô hình tối ưu vào vận hành thật.

Ghi nhớ

• Phân biệt solver (động cơ giải — CBC, HiGHS, Gurobi...) với modeling layer (lớp viết mô hình bằng Python — PuLP, OR-Tools, Pyomo, CVXPY). Viết mô hình một lần, đổi solver bằng một tham số.
• Mã nguồn mở (CBC, HiGHS, SCIP) miễn phí, đủ cho bài vừa; thương mại (Gurobi, CPLEX, Xpress) nhanh hơn nhiều cho MILP lớn, có bản học thuật. Bắt đầu với OSS, chỉ nâng cấp khi benchmark chứng minh cần.
• Chọn modeling API theo bài: PuLP/Python-MIP cho LP/MILP; OR-Tools CP-SAT cho lập lịch/tổ hợp; CVXPY cho lồi/danh mục; Pyomo cho mô hình phức tạp/phi tuyến.
• Quy trình 6 bước: phát biểu → mô hình hoá → nạp dữ liệu (SQL) → giải & đọc trạng thái → diễn giải nghiệm → kiểm định & quyết định. Nạp dữ liệu và diễn giải quan trọng ngang mô hình hoá.
• Luôn kiểm trạng thái trước khi tin nghiệm: Optimal / time-limit (đọc gap) / Infeasible / Unbounded — hai cái sau thường là lỗi mô hình.
• Mẹo thực chiến: đơn vị nhất quán, scaling hệ số về cùng bậc, đặt time/gap limit, warm start cho batch, dùng ràng buộc mềm + phạt thay ràng buộc cứng dễ vỡ, gỡ infeasible bằng slack có phạt / IIS.
• Tích hợp: batch định kỳ (Airflow) là hình thái chủ đạo ở ngân hàng; log lại phiên bản/dữ liệu/trạng thái để kiểm toán và tái lập.
• Solver chính xác khi cần bảo đảm tối ưu và giải kịp; heuristic khi bài quá lớn/phi cấu trúc và chỉ cần "đủ tốt" — luôn thử exact trước.