Toán ứng dụng và Tính toán

Tối ưu rời rạc

Tối ưu trên một tập lựa chọn hữu hạn hoặc đếm được, ví dụ bài toán lập lịch hoặc định tuyến.

Trực giácTối ưu rời rạc là gì?

Hãy tưởng tượng bạn phải chọn tuyến đường cho một xe giao hàng, phân công công nhân vào các ca làm, hoặc chọn một tập hợp con dự án để tài trợ. Khác với đường cong trơn, các lựa chọn ở đây đến theo từng đơn vị nguyên vẹn, không thể chia nhỏ: xe hoặc đi qua một con phố hoặc không, công nhân hoặc có ca trực hoặc không. Tối ưu rời rạc là toán học của việc tìm lựa chọn tốt nhất trong một tập hợp $n$ khả năng rời rạc hữu hạn (hoặc đếm được), thay vì trượt liên tục dọc theo một đường cong.

Một mạng lưới giao hàng: các nút là điểm dừng, các cạnh là đường có chi phí. Đường được tô sáng cho thấy một lựa chọn rời rạc trong số hữu hạn tuyến đường có thể.

Phổ thôngTừ liên tục đến rời rạc: chọn nghiệm nguyên

Định nghĩa: Quy hoạch tuyến tính nguyên (ILP)

Một quy hoạch tuyến tính nguyên là bài toán tối đa hoá một hàm mục tiêu tuyến tính $c^T x$ với các ràng buộc tuyến tính $Ax \le b$ , trong đó mọi biến quyết định phải là số nguyên không âm: $x \in \mathbb{Z}^n_{\ge 0}$ . Nhiều bài toán thực tế — mua bao nhiêu xe tải, chọn dự án nào — vốn dĩ là số nguyên, nên làm tròn một nghiệm liên tục là chưa đủ tốt.

\max\ c^T x \ \text{s.t.}\ Ax \le b,\ x \in \mathbb{Z}^n_{\ge 0}

Ở đây $c^T x$ là giá trị mục tiêu (lợi nhuận, chi phí, độ phủ) cần tối đa hoá, $Ax \le b$ gói mọi giới hạn tài nguyên (ngân sách, năng lực, thời gian) vào một bất đẳng thức ma trận, và $x \in \mathbb{Z}^n_{\ge 0}$ nói rằng mọi toạ độ của vectơ nghiệm phải là số nguyên không âm. Bỏ điều kiện nguyên đi ta được phần nới lỏng tuyến tính (LP relaxation) bên dưới.

\max\ c^T x \ \text{s.t.}\ Ax \le b,\ x \in \mathbb{R}^n_{\ge 0}

So sánh ILP, LP relaxation và branch-and-bound
Phương pháp	Tập khả thi	Độ phức tạp
Quy hoạch nguyên	$x \in \mathbb{Z}^n_{\ge 0}$	NP-khó nói chung
LP relaxation	$x \in \mathbb{R}^n_{\ge 0}$	Đa thức (simplex/điểm trong)
Branch-and-bound	Chia LP relaxation thành các bài toán con	Trường hợp xấu nhất mũ, thực tế thường nhanh

Đại họcBảo đảm chính xác: Max-flow min-cut và cận của branch-and-bound

Định lý: Định lý Max-flow min-cut

Trong một mạng luồng bất kỳ với nguồn $s$ và đích $t$ cùng các dung lượng cạnh không âm, giá trị luồng lớn nhất từ $s$ đến $t$ bằng dung lượng nhỏ nhất trong số mọi lát cắt từ $s$ đến $t$ .

Vì sao đúng?

Định lý biến một bài toán tối đa hoá (tìm luồng lớn nhất) thành một bài toán tối thiểu hoá tương đương (tìm điểm nghẽn nhỏ nhất), nên chỉ một lát cắt cũng cho ta một chứng nhận tức thời, kiểm tra được rằng luồng đã tối ưu — cùng ý tưởng đối ngẫu gốc-đối ngẫu làm nền cho đối ngẫu LP và việc cắt tỉa trong branch-and-bound.

Chứng minh

Trước tiên là đối ngẫu yếu. Lấy một lát cắt $s$ - $t$ bất kỳ $S$ , $T$ với $s$ thuộc $S$ và $t$ thuộc $T$ , và một luồng khả thi bất kỳ $|f|$ . Mỗi đơn vị luồng rời khỏi $s$ cuối cùng phải đi từ $S$ sang $T$ để tới được $t$ , và theo tính bảo toàn, luồng ròng qua lát cắt bằng đúng tổng giá trị luồng. Vì các cạnh từ $T$ quay ngược về $S$ chỉ có thể làm giảm lượng ròng này, giá trị luồng không bao giờ vượt quá tổng dung lượng các cạnh rời khỏi $S$ , tức là $|f|$ luôn nhỏ hơn hoặc bằng $\mathrm{cap}(S,T)$ với mọi lát cắt.

Bây giờ chạy thuật toán Ford-Fulkerson đến khi kết thúc: lặp lại việc tìm một đường từ $s$ đến $t$ trong đồ thị thặng dư (dung lượng còn lại cộng với luồng có thể đảo ngược đã gửi) và đẩy thêm luồng đúng bằng cạnh hẹp nhất trên đường đó cho phép. Vì dung lượng được giả sử là số nguyên hoặc hữu tỉ và giảm chặt sau mỗi lần dùng đường tăng luồng, quá trình này kết thúc sau hữu hạn bước.

Khi kết thúc, không còn đường tăng luồng nào. Gọi $S$ là tập các nút có thể đến được từ $s$ trong đồ thị thặng dư cuối cùng, và $T$ là phần còn lại (vậy $t$ thuộc $T$ vì không có đường nào đến được nó). Mọi cạnh từ $S$ sang $T$ trong mạng gốc phải bão hoà hoàn toàn (nếu không nó vẫn còn dung lượng thặng dư, mở rộng thêm $S$ ), và mọi cạnh từ $T$ quay lại $S$ phải mang luồng bằng không (nếu không cạnh thặng dư ngược của nó sẽ mở rộng thêm $S$ ).

Cộng dồn tính bảo toàn luồng trên mọi nút trong $S$ cho thấy tổng giá trị luồng bằng đúng dung lượng của các cạnh thuận đã bão hoà trừ đi luồng ngược bằng không, chính là $\mathrm{cap}(S,T)$ cho lát cắt này. Kết hợp với cận trên ở đoạn đầu, lát cắt này đạt dung lượng nhỏ nhất có thể, nên giá trị luồng lớn nhất bằng đúng dung lượng lát cắt nhỏ nhất.

Định lý: Cận LP relaxation cho branch-and-bound

Với một quy hoạch tuyến tính nguyên dạng tối đa hoá, giá trị tối ưu của LP relaxation là một cận trên cho giá trị tối ưu của quy hoạch nguyên; do đó branch-and-bound có thể loại bỏ một bài toán con bất cứ khi nào cận LP relaxation của nó không tốt hơn nghiệm nguyên tốt nhất đã tìm được, mà không bao giờ loại mất nghiệm tối ưu thật sự.

Vì sao đúng?

Giải LP relaxation nhanh (thời gian đa thức), nên nó cho một cận trên rẻ để so sánh với nghiệm nguyên tốt nhất đã tìm được; nếu một nhánh không thể vượt qua cận đó, việc khám phá tiếp là lãng phí — đây chính là điều làm branch-and-bound khả thi trên các quy hoạch nguyên lớn.

Chứng minh

Gọi $x \in \mathbb{Z}^n_{\ge 0}$ là tập khả thi nguyên và $x \in \mathbb{R}^n_{\ge 0}$ là tập khả thi (lớn hơn) của LP relaxation với cùng ràng buộc $Ax \le b$ . Vì bỏ điều kiện nguyên chỉ loại bớt ràng buộc, mọi điểm khả thi nguyên cũng khả thi cho LP, nên tập khả thi nguyên là tập con của tập khả thi LP relaxation.

Vì cả hai bài toán tối đa hoá cùng một hàm mục tiêu tuyến tính $c^T x$ và tập khả thi của quy hoạch nguyên nằm trong tập khả thi của LP relaxation, giá trị tốt nhất đạt được trên tập con không thể vượt quá giá trị tốt nhất đạt được trên tập lớn hơn. Do đó giá trị tối ưu của LP relaxation là cận trên cho giá trị tối ưu của ILP.

Branch-and-bound xây một cây tìm kiếm bằng cách chọn một biến có giá trị phân số trong nghiệm LP relaxation hiện tại và tạo ra hai bài toán con thêm ràng buộc $x_1 \le 1$ hoặc $x_1 \ge 2$ ; mọi điểm khả thi nguyên thoả mãn đúng một trong hai điều kiện này, nên không có nghiệm nguyên nào bị mất qua phép chia này, và lặp lại phép chia tiếp tục phân hoạch không gian mà không để sót.

Tại mỗi nút, giải LP relaxation của bài toán con đó cho một cận trên cho mọi nghiệm nguyên còn có thể đạt tới bên dưới nó, theo cùng lập luận trên áp dụng cho tập ràng buộc nhỏ hơn. Nếu cận này không lớn hơn giá trị của nghiệm nguyên tốt nhất đã tìm được ở bất kỳ đâu trong cây, không nhánh con nào của nút này có thể cải thiện nghiệm tốt nhất hiện tại, nên toàn bộ nhánh con có thể bị cắt bỏ mà vẫn bảo đảm nghiệm tối ưu thật sự được tìm thấy ở nơi khác trong cây.

Đại họcỨng dụng thực tiễn và Ví dụ minh họa

Tối ưu rời rạc vận hành hậu cần của thế giới hiện đại: các hãng hàng không giải ILP xếp lịch phi hành đoàn mỗi ngày, nhà sản xuất chip dùng ý tưởng tô màu đồ thị và max-flow để đi dây, và các công ty giao hàng giải bài toán định tuyến xe vốn dĩ là tìm kiếm branch-and-bound trên một quy hoạch nguyên. Hai ví dụ dưới đây minh hoạ mẫu hình LP relaxation cộng phân nhánh, và mẫu hình max-flow min-cut.

Ví dụ: Branch-and-bound trên một ILP nhỏ

Tối đa hoá $x_1$ + $x_2$ với ràng buộc $2x_1 + x_2 \le 5$ và $x_1 + 2x_2 \le 5$ , với $x_1$ và $x_2$ là số nguyên không âm.

Lời giải

Bước 1: Giải LP relaxation. Hai ràng buộc chặt nhất tại giao điểm của chúng: giải đồng thời $2x_1 + x_2 = 5$ và $x_1 + 2x_2 = 5$ cho $x_1 = x_2 = \frac{5}{3}$ , với giá trị mục tiêu $\frac{10}{3} \approx 3.33$ .

Bước 2: Vì $x_1$ tối ưu của LP là số phân số, phân nhánh theo nó: một nhánh con thêm $x_1 \le 1$ , nhánh kia thêm $x_1 \ge 2$ .

Bước 3: Ở nhánh có $x_1 \le 1$ , các ràng buộc buộc $x_2$ lên tới $2$ khi $x_1$ = $1$ , cho điểm nguyên $x_1 = 1,\ x_2 = 2$ với $x_1 + x_2 = 3$ .

Bước 4: Ở nhánh có $x_1 \ge 2$ , các ràng buộc buộc $x_2$ xuống $1$ khi $x_1$ = $2$ , cho điểm nguyên $x_1 = 2,\ x_2 = 1$ , cũng với $x_1 + x_2 = 3$ .

Bước 5: Cả hai nhánh đều đã cho nghiệm nguyên với cùng giá trị mục tiêu, nên không cần phân nhánh thêm; nghiệm tối ưu của ILP là $3$ , nhỏ hơn hẳn cận LP relaxation $\frac{10}{3} \approx 3.33$ đúng như định lý dự đoán.

Ví dụ: Luồng lớn nhất trong một mạng vận chuyển nhỏ

Một mạng có các nút $s$ , a, b, $t$ với dung lượng cạnh $s$ →a: $10$ , $s$ →b: $5$ , a→b: $4$ , a→ $t$ : $8$ , b→ $t$ : $9$ . Tìm luồng lớn nhất từ $s$ đến $t$ .

Lời giải

Bước 1: Đẩy luồng theo $s$ →a→ $t$ . Điểm nghẽn là $\min(10,8)=8$ , nên gửi $8$ đơn vị; cạnh $s$ →a còn lại $2$ đơn vị dung lượng.

Bước 2: Đẩy luồng theo $s$ →b→ $t$ . Điểm nghẽn là $\min(5,9)=5$ , nên gửi $5$ đơn vị; cạnh b→ $t$ còn lại $4$ đơn vị.

Bước 3: Đẩy luồng theo $s$ →a→b→ $t$ dùng dung lượng còn lại: $\min(2,4,4)=2$ , nên gửi thêm $2$ đơn vị. Bây giờ cả hai cạnh ra khỏi $s$ đều dùng hết.

Bước 4: Tổng luồng đã gửi là $8+5+2=15$ .

Bước 5: Không còn đường tăng luồng nào vì cả hai cạnh rời $s$ đều bão hoà. Lát cắt tách riêng $s$ có dung lượng $10+5=15$ , khớp với luồng tìm được — theo định lý max-flow min-cut, điều này xác nhận $15$ là tối ưu.

Hiện trạng nghiên cứu tính đến năm 2026

Các bộ giải quy hoạch nguyên hỗn hợp hiện đại kết hợp branch-and-bound với các mặt phẳng cắt và, ngày càng nhiều, các suy nghiệm học máy dự đoán biến phân nhánh tốt để tăng tốc tìm kiếm trên các bài toán quy mô công nghiệp. Về mặt xấp xỉ, Karlin, Klein và Oveis Gharan năm 2021 đã đưa ra cải tiến đầu tiên sau nhiều thập kỷ so với tỉ lệ xấp xỉ 3/2 cổ điển cho bài toán TSP mêtric, và các công trình tiếp theo vẫn đang tiếp tục thu hẹp khoảng cách giữa tỉ lệ xấp xỉ tốt nhất đã biết và ngưỡng khó thật sự được phỏng đoán. Các phương pháp ủ (annealing) lượng tử và lấy cảm hứng từ lượng tử (ví dụ cho các bài toán tổ hợp dạng Ising) là một hướng nghiên cứu thực nghiệm đang hoạt động, dù việc tăng tốc chặt chẽ so với branch-and-bound cổ điển trên các thể hiện khó vẫn còn là câu hỏi mở.

Nếu LP relaxation của một ILP dạng tối đa hoá có giá trị tối ưu $42.3$ , ta có thể kết luận gì về giá trị tối ưu của ILP?

Một công ty chuyển phát phải quyết định, với mỗi tuyến đường ứng viên, có sử dụng nó hay không, để tối thiểu hoá tổng chi phí với các ràng buộc bao phủ. Mô hình nào phù hợp nhất?

Trong một mạng luồng, lát cắt $s$ - $t$ nhỏ nhất có dung lượng $15$ . Giá trị luồng lớn nhất là bao nhiêu?

Trong branch-and-bound cho một ILP dạng tối đa hoá, khi nào một nhánh con nên bị cắt tỉa?

Tài liệu tham khảo

Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan (2021). A (Slightly) Improved Approximation Algorithm for Metric TSP · arXiv:2007.01409