Tối ưu hoá 3 — Quy hoạch nguyên & MILP

Khi "một nửa quyết định" là vô nghĩa

Trong bài về LP chúng ta giả định biến quyết định nhận giá trị liên tục — có thể là 3.7 hay 128.45. Với nhiều bài toán điều đó hợp lý: phân bổ 3.7 tỷ đồng vốn, sản xuất 128.45 tấn xi măng. Nhưng vô số quyết định thực tế không chia nhỏ được:

• Có mở chi nhánh ở quận này không? — chỉ có mở hoặc không, không có "mở 0.6 chi nhánh".
• Đặt bao nhiêu máy ATM tại một điểm? — phải là số nguyên: 0, 1, 2, 3.
• Chọn dự án đầu tư nào trong danh mục dưới ngân sách cố định? — mỗi dự án chọn hoặc bỏ.
• Gán ai làm việc gì (RM nào chăm khách VIP nào)? — một cặp gán hoặc không.

Khi biến buộc phải nguyên, bài toán rời khỏi thế giới êm ả của LP và bước vào quy hoạch nguyên (Integer Programming — IP). Nếu có cả biến nguyên lẫn biến liên tục trong cùng một mô hình tuyến tính, ta gọi là Mixed-Integer Linear Programming (MILP) — dạng phổ biến nhất và có sức biểu diễn cực mạnh. Bài này đi vào: vì sao cần biến nguyên/nhị phân, cách dùng biến 0/1 để mô hình hoá logic, các bài toán kinh điển, tại sao IP khó hơn LP rất nhiều, và trực giác thuật toán branch-and-bound mà mọi solver hiện đại đều dùng.

1. Phân loại: IP, MILP, BIP

Cùng có dạng tuyến tính như LP, nhưng khác ở tính nguyên của biến:

Dạng MILP tổng quát:

max   cᵀx + dᵀy
s.t.  A·x + B·y ≤ b
      x ≥ 0            (biến liên tục)
      y ≥ 0, y nguyên   (biến nguyên; nếu y ∈ {0,1} → nhị phân)

Chỉ cần thêm điều kiện "y nguyên" — một câu ngắn — nhưng nó phá vỡ toàn bộ tính chất đẹp của LP (xem mục 5). Đổi lại, biến nhị phân cho ta khả năng mô hình hoá quyết định logic mà LP thuần không làm được.

2. Biến nhị phân — mô hình hoá logic

Đây là kỹ năng cốt lõi của MILP. Một biến nhị phân y ∈ {0,1} biểu diễn một quyết định yes/no:

y = 1  ⇔  "có" (mở chi nhánh, chọn dự án, gán nhân sự)
y = 0  ⇔  "không"

Sức mạnh nằm ở chỗ: bằng các ràng buộc tuyến tính trên biến 0/1, ta biểu diễn được đủ loại quan hệ logic. Dưới đây là bộ công cụ mô hình hoá phải nắm:

Ràng buộc số lượng (chọn đúng k trong n)

Σ yᵢ = k        (chọn đúng k phương án)
Σ yᵢ ≤ k        (chọn tối đa k)
Σ yᵢ ≥ 1        (chọn ít nhất 1)

Ví dụ: mở đúng 3 chi nhánh mới trong 12 vị trí ứng viên → Σ yᵢ = 3.

Loại trừ (mutual exclusion)

y_A + y_B ≤ 1   (A và B không thể cùng chọn)

Ví dụ: hai vị trí ATM quá gần nhau, chỉ đặt một trong hai.

Ràng buộc nếu-thì (implication)

y_A ≤ y_B       ("nếu chọn A thì phải chọn B")

Nếu y_A = 1 thì buộc y_B ≥ 1 = 1. Ví dụ: nếu mở phòng giao dịch A thì phải mở kho quỹ B đi kèm.

Big-M — nối biến nhị phân với biến liên tục

Đây là mẹo quan trọng nhất. Muốn ràng buộc "chỉ được phân bổ vốn x cho chi nhánh nếu chi nhánh đó được mở (y=1)":

x ≤ M · y

với M là một hằng số đủ lớn (upper bound của x). Khi y = 0 → x ≤ 0 → buộc x = 0 (không mở thì không rót vốn). Khi y = 1 → x ≤ M (ràng buộc nới lỏng, x tự do trong giới hạn thật). Đây là linh hồn của MILP: dùng 0/1 để bật/tắt cả một khối ràng buộc hoặc chi phí.

Cảnh báo big-M: chọn M càng sát cận trên thật càng tốt. M quá lớn làm LP relaxation lỏng lẻo, solver chậm hẳn (xem mục 5-6). Đừng đặt M = 10⁹ cho đại — hãy đặt M bằng giá trị lớn nhất x thực sự có thể đạt.

Chi phí cố định (fixed charge)

Kết hợp big-M cho phép mô hình hoá chi phí cố định: mở chi nhánh tốn phí cố định f bất kể quy mô, cộng chi phí biến đổi theo x. Hàm mục tiêu có số hạng −f·y (chỉ tính khi y=1) — điều LP thuần không biểu diễn được vì hàm chi phí có bước nhảy tại 0.

3. Các bài toán MILP kinh điển

Nhận diện bài toán thực về một khuôn mẫu chuẩn giúp ta mô hình hoá nhanh và mượn được thuật toán đã tối ưu sẵn.

Knapsack — chọn danh mục dưới ngân sách

Rất hay gặp trong ngân hàng. Có n phương án, mỗi phương án i có giá trị v_i (lợi nhuận kỳ vọng) và chi phí c_i; ngân sách tổng là B. Chọn tập phương án tối đa hoá tổng giá trị mà không vượt ngân sách:

max   Σ vᵢ·xᵢ
s.t.  Σ cᵢ·xᵢ ≤ B
      xᵢ ∈ {0,1}

Ví dụ: có ngân sách marketing 5 tỷ, mỗi nhóm khách hàng có chi phí tiếp cận và giá trị kỳ vọng khác nhau → chọn nhóm nào để tiếp cận.

Assignment — gán 1-1

Có n nhân viên (RM) và n khách hàng VIP, chi phí (hoặc điểm phù hợp âm) c_ij khi gán RM i cho khách j. Mỗi RM đúng một khách, mỗi khách đúng một RM:

min   Σᵢ Σⱼ c_ij·x_ij
s.t.  Σⱼ x_ij = 1   ∀i   (mỗi RM 1 khách)
      Σᵢ x_ij = 1   ∀j   (mỗi khách 1 RM)
      x_ij ∈ {0,1}

Điểm thú vị: ma trận ràng buộc của bài assignment thuần là totally unimodular — nghĩa là LP relaxation của nó tự cho nghiệm nguyên, giải bằng LP thường (hoặc thuật toán Hungarian) là đủ. Nhưng thêm bất kỳ ràng buộc phụ nào (RM i không được gán quá 2 khách VIP...) là mất tính chất đó, quay về MILP thật.

Facility location — đặt chi nhánh/ATM ở đâu

Bài toán "hai tầng quyết định" điển hình, minh hoạ sức mạnh MILP: tầng trên là mở cơ sở nào (nhị phân), tầng dưới là phục vụ khách nào từ cơ sở nào (có thể liên tục hoặc 0/1), nối với nhau qua big-M.

min   Σⱼ fⱼ·yⱼ          +  Σᵢ Σⱼ d_ij·x_ij
      (chi phí mở cơ sở)     (chi phí phục vụ)
s.t.  Σⱼ x_ij = 1        ∀i     (mỗi khách được phục vụ)
      x_ij ≤ yⱼ          ∀i,j   (chỉ phục vụ từ cơ sở đã mở)
      yⱼ ∈ {0,1};  x_ij ≥ 0

Ràng buộc x_ij ≤ y_j chính là big-M với M=1 — thể hiện logic "không mở cơ sở j thì không khách nào được gán về j".

4. Ví dụ mô hình MILP + pseudocode

Mô hình hoá bài knapsack chọn chiến dịch bằng PuLP (Python). Đây là minh hoạ pseudocode, không phải SQL chạy được trên sandbox:

# MINH HOẠ (PuLP) — không phải SQL sandbox
import pulp

nhom   = ["A", "B", "C", "D", "E"]
gia_tri = {"A": 900, "B": 650, "C": 1200, "D": 400, "E": 750}  # triệu, lợi nhuận kỳ vọng
chi_phi = {"A": 500, "B": 300, "C": 800, "D": 200, "E": 450}   # triệu, chi phí tiếp cận
NGAN_SACH = 1500  # triệu

m = pulp.LpProblem("chon_chien_dich", pulp.LpMaximize)
x = pulp.LpVariable.dicts("chon", nhom, cat="Binary")   # biến nhị phân 0/1

# Mục tiêu: tối đa tổng giá trị
m += pulp.lpSum(gia_tri[i] * x[i] for i in nhom)
# Ràng buộc ngân sách
m += pulp.lpSum(chi_phi[i] * x[i] for i in nhom) <= NGAN_SACH

m.solve()
chon = [i for i in nhom if x[i].value() == 1]
print("Chọn:", chon, "| Giá trị:", pulp.value(m.objective))

Cùng bài toán bằng OR-Tools (CP-SAT hoặc SCIP backend) khi cần scale lớn hơn:

# MINH HOẠ (OR-Tools) — không phải SQL sandbox
from ortools.linear_solver import pywraplp
s = pywraplp.Solver.CreateSolver("SCIP")   # backend MILP
x = {i: s.IntVar(0, 1, f"x_{i}") for i in nhom}
s.Add(sum(chi_phi[i]*x[i] for i in nhom) <= NGAN_SACH)
s.Maximize(sum(gia_tri[i]*x[i] for i in nhom))
s.Solve()

Chi tiết so sánh solver (CBC, SCIP, Gurobi, CP-SAT) sẽ bàn ở bài công cụ solver.

Chuẩn bị dữ liệu đầu vào từ kho dữ liệu

Trước khi feed vào solver, ta thường tổng hợp gia_tri và chi_phi theo nhóm khách từ dữ liệu giao dịch. Ví dụ tính "giá trị" (tổng số dư đại diện tiềm năng) và "chi phí" (đại diện bằng số lượng tài khoản cần chăm) theo từng thành phố — feed vào knapsack:

-- ▶ Chạy được
SELECT
  c.city,
  COUNT(DISTINCT c.id)                            AS so_khach,
  COUNT(a.id)                                      AS so_tai_khoan,   -- ~ chi phí tiếp cận
  ROUND(SUM(a.balance)::numeric, 2)                AS gia_tri_sodu,   -- ~ giá trị
  ROUND((SUM(a.balance) / NULLIF(COUNT(a.id),0))::numeric, 2) AS gia_tri_tren_tk
FROM customers c
JOIN accounts a ON a.customer_id = c.id
GROUP BY c.city
HAVING SUM(a.balance) > 0
ORDER BY gia_tri_sodu DESC;

Kết quả bảng này (mỗi thành phố = một "món" trong ba lô) chính là input để giải knapsack: chọn tập thành phố ưu tiên triển khai chiến dịch dưới ngân sách nhân lực cố định.

5. Vì sao IP khó hơn LP rất nhiều

LP giải nhanh vì miền khả thi là đa diện lồi (convex polytope) và nghiệm tối ưu luôn nằm ở đỉnh — Simplex chỉ cần đi men theo các đỉnh. IP đánh mất cả hai tính chất đó:

• Không lồi: tập các điểm nguyên hợp lệ là một "lưới điểm" rời rạc, không phải hình khối liền. Không thể "đi men cạnh" nữa.
• Bùng nổ tổ hợp: với n biến nhị phân, có 2ⁿ tổ hợp khả dĩ. n=50 cho hơn 10¹⁵ tổ hợp — không thể duyệt hết. IP tổng quát là NP-hard: chưa ai biết thuật toán chạy nhanh (đa thức) cho mọi trường hợp.

Cám dỗ đầu tiên là "cứ giải LP rồi làm tròn". Đừng. Làm tròn nghiệm LP có thể cho kết quả vi phạm ràng buộc (vượt ngân sách) hoặc xa nghiệm tối ưu. Ví dụ knapsack nhỏ: LP chọn "0.7 món C", làm tròn thành 1 → vượt ngân sách; làm tròn thành 0 → bỏ mất giá trị lớn. Nghiệm nguyên tối ưu có thể là một tổ hợp hoàn toàn khác.

LP relaxation & gap

Dù không dùng để làm tròn, LP vẫn cực kỳ hữu ích. LP relaxation là bài toán IP nhưng bỏ điều kiện nguyên (cho biến chạy liên tục). Vì miền khả thi của relaxation rộng hơn miền nguyên, nghiệm của nó là một cận (bound) cho IP:

• Với bài max, LP relaxation cho cận trên — IP không thể tốt hơn.
• Khoảng cách giữa nghiệm relaxation và nghiệm nguyên tốt nhất tìm được gọi là gap (optimality gap). Solver dừng khi gap đủ nhỏ (ví dụ ≤ 1%).

Chính cận này là nền tảng của thuật toán chủ lực: branch-and-bound.

6. Branch-and-bound — chia & cận

Đây là thuật toán "xương sống" mọi solver MILP dùng. Ý tưởng: chia không gian nghiệm thành các nhánh nhỏ hơn, dùng LP relaxation để tính cận cho mỗi nhánh, và cắt bỏ (prune) những nhánh không thể chứa nghiệm tốt hơn nghiệm đã có. Ba bước lặp:

1. Relax & solve: giải LP relaxation của bài toán hiện tại. Nếu nghiệm đã nguyên → là nghiệm nguyên hợp lệ, cập nhật kỷ lục (incumbent).
2. Branch (nhánh): nếu một biến ra giá trị phân số, ví dụ y = 3.4, tách thành hai bài con: một buộc y ≤ 3, một buộc y ≥ 4. Với biến nhị phân: y = 0 và y = 1.
3. Bound & prune (cận & cắt): nếu cận của một nhánh (nghiệm LP relaxation của nó) tệ hơn incumbent hiện tại → nhánh đó vô vọng, cắt bỏ cả cây con, không cần khám phá.

Chính nhờ cắt nhánh mà thực tế ta không phải duyệt 2ⁿ khả năng — solver chỉ khám phá một phần nhỏ cây. Mô hình hoá tốt (cận relaxation sát) giúp cắt được nhiều nhánh hơn → nhanh hơn nhiều lần.

Cutting planes & branch-and-cut

Solver hiện đại còn dùng cutting planes (mặt phẳng cắt): thêm các ràng buộc tuyến tính mới không loại bỏ điểm nguyên hợp lệ nào nhưng cắt bớt vùng phân số của miền relaxation, làm cận chặt hơn. Kết hợp branch-and-bound với cutting planes gọi là branch-and-cut — mặc định trong CBC, SCIP, Gurobi. Người dùng không cần cài đặt thủ công, nhưng hiểu để biết vì sao "ràng buộc chặt" lại quan trọng.

7. Mẹo mô hình hoá cho solver chạy nhanh

MILP nhạy cảm với cách viết mô hình hơn LP rất nhiều. Cùng một bài toán, mô hình khéo có thể giải trong giây, mô hình vụng chạy hàng giờ.

• Ràng buộc càng chặt càng tốt (tight formulation): viết ràng buộc sao cho miền LP relaxation sát với bao lồi của các điểm nguyên. Cận sát → cắt nhánh nhiều → nhanh.
• Big-M nhỏ nhất có thể: như đã cảnh báo, M đúng bằng cận trên thật của biến. M phồng làm relaxation lỏng, cận yếu.
• Phá đối xứng (symmetry breaking): nếu nhiều nghiệm hoán vị nhau tương đương (ví dụ các thùng giống hệt trong bin packing), thêm ràng buộc thứ tự để solver không duyệt lại các bản sao.
• Cung cấp cận trên/dưới & warm start: đưa một nghiệm khả thi ban đầu (dù chưa tối ưu) giúp cắt nhánh sớm.
• Chấp nhận gap: đặt gap ≤ 1–5% khi cần đáp án "đủ tốt" nhanh, thay vì tối ưu tuyệt đối.

Khi bài toán quá lớn → gần đúng

Khi số biến lên tới hàng trăm nghìn và branch-and-cut không kịp, ta chuyển sang heuristic / metaheuristic (tham lam, local search, di truyền, tabu, simulated annealing) để có nghiệm tốt (không đảm bảo tối ưu) trong thời gian chấp nhận được. Đây là chủ đề của bài liên hệ trong series về lịch biểu & mạng lưới và các cách tiếp cận nâng cao ở bài stochastic/robust.

Use case thực tế

Bối cảnh: Khối Khách hàng Cá nhân NCB có ngân sách chiến dịch cross-sell quý III là 1.500 triệu đồng. Đội phân tích đã phân khúc khách theo thành phố và ước tính, cho mỗi phân khúc: giá trị kỳ vọng (lợi nhuận biên nếu chiến dịch thành công) và chi phí tiếp cận (nhân lực + kênh). Mỗi phân khúc chỉ có thể triển khai hoặc không (chi phí là trọn gói, không chia nhỏ) — đúng bài knapsack 0/1.

Dữ liệu (minh hoạ):

Bước 1 — Chuẩn bị input: tổng hợp giá trị/chi phí theo phân khúc từ kho dữ liệu (câu SQL "Chạy được" ở mục 4 là bản rút gọn dùng số dư và số tài khoản làm đại diện).

Bước 2 — Giải MILP knapsack (mã PuLP mục 4). Solver duyệt: tổng ngân sách chỉ 1.500 nên không thể chọn hết. Nghiệm tối ưu: chọn A + B + D (chi phí 500+300+200 = 1.000 ≤ 1.500; giá trị 900+650+400 = 1.950). Phương án tham lam theo giá trị tuyệt đối (chọn C trước, chi 800, rồi A hết 1.300, dừng) chỉ cho 2.100 nhưng nếu thử C+E = chi 1.250, giá trị 1.950 — solver so sánh mọi tổ hợp qua branch-and-bound và trả về tối ưu thật (ở đây A+C = chi 1.300, giá trị 2.100 mới là max). Điểm mấu chốt: đừng làm tròn hay tham lam bằng tay — chênh lệch giá trị hàng trăm triệu.

Bước 3 — Đưa gap = 0 (bài nhỏ, giải tối ưu tuyệt đối trong mili-giây), xuất danh sách phân khúc chọn cho đội vận hành. Với bài lớn hơn (hàng nghìn khách cá thể thay vì phân khúc), đặt gap ≤ 2% và giới hạn thời gian.

Mở rộng: thêm ràng buộc "phải phủ ít nhất 1 phân khúc mỗi vùng miền" (Σ y_{miền} ≥ 1) hay "A và C loại trừ do trùng đội bán" (y_A + y_C ≤ 1) — chỉ là vài dòng ràng buộc nhị phân, minh hoạ vì sao MILP linh hoạt hơn hẳn heuristic thủ công.

Ghi nhớ

• IP/MILP = LP nhưng buộc một số (IP) hoặc vài (MILP) biến nhận giá trị nguyên; BIP dùng biến nhị phân {0,1}. Cần khi quyết định không chia nhỏ được: mở/không mở, chọn/bỏ, số nguyên máy, gán 1-1.
• Biến nhị phân là công cụ mô hình hoá logic: ràng buộc số lượng (Σyᵢ=k), loại trừ (y_A+y_B≤1), nếu-thì (y_A≤y_B), và big-M (x ≤ M·y) để bật/tắt cả khối ràng buộc/chi phí cố định.
• Thuộc lòng các khuôn mẫu kinh điển: assignment (gán RM-khách), knapsack (chọn chiến dịch dưới ngân sách), set covering / facility location (đặt ATM/chi nhánh), bin packing, scheduling.
• IP NP-hard: miền không lồi, tổ hợp bùng nổ (2ⁿ). KHÔNG giải LP rồi làm tròn — dễ vi phạm ràng buộc hoặc trật xa tối ưu.
• LP relaxation cho cận (bài max → cận trên); khoảng cách tới nghiệm nguyên là gap. Đây là nền tảng của branch-and-bound: relax → nhánh trên biến phân số → cắt nhánh khi cận thua incumbent.
• Solver hiện đại = branch-and-cut (thêm cutting planes làm cận chặt). Mô hình hoá tốt — ràng buộc chặt, big-M nhỏ, phá đối xứng — giúp solver nhanh gấp nhiều lần.
• Khi quá lớn → chấp nhận gap hoặc chuyển sang heuristic/gần đúng. Chi tiết công cụ ở bài solver.