Tổng quan về luận án

Bài toán Hôn nhân ổn định (Stable Marriage Problem - SMP), được khởi xướng bởi David Gale và Lloyd Shapley (1962), là một trong những nền tảng kinh điển của lý thuyết trò chơi vi mô, tối ưu hóa tổ hợp và khoa học máy tính thuật toán. Thành tựu đột phá của các mô hình ghép cặp ổn định đã được khẳng định bằng Giải thưởng Nobel Kinh tế năm 2012 trao cho Lloyd S. Shapley và Alvin E. Roth. Tuy nhiên, mô hình SMP nguyên bản đặt trên giả định lý tưởng hóa: số lượng hai tập tác nhân cân bằng ($|M| = |W| = n$), danh sách ưu tiên hoàn chỉnh và có thứ tự xếp hạng nghiêm ngặt (strict linear order). Trong thực tiễn triển khai phân bổ tài nguyên kinh tế - xã hội như phân bổ sinh viên y khoa nội trú (National Resident Matching Program - NRMP tại Hoa Kỳ; Scottish Pre-registration Trainee System tại Scotland), tuyển sinh đại học hay phân bổ đề tài nghiên cứu, các ràng buộc trên đều bị phá vỡ. Các tác nhân thường chỉ xếp hạng một tập con hữu hạn (incomplete lists) và tồn tại nhiều lựa chọn tương đương nhau về mức độ ưu tiên (ties).

Sự kết hợp giữa yếu tố quan hệ ngang hàng (ties) và danh sách không đầy đủ (incomplete lists) dẫn tới bài toán SMTI (Stable Marriage with Ties and Incomplete lists) cùng các mở rộng một-nhiều gồm HRT (Hospitals/Residents with Ties) và SPA (Student-Project Allocation). Khi xuất hiện quan hệ ngang hàng, khái niệm ổn định phân nhánh thành ba cấp độ: ổn định siêu mạnh (super-stable), ổn định mạnh (strongly stable) và ổn định yếu (weakly stable) (Irving et al., 2000, 2008). Trong khi phép ghép siêu ổn định và ổn định mạnh có thể không tồn tại trên nhiều thể hiện dữ liệu thực tế, phép ghép ổn định yếu luôn luôn tồn tại nhưng kích thước lực lượng (cardinality) giữa các nghiệm ổn định lại có sự chênh lệch đáng kể. Mục tiêu tìm kiếm phép ghép ổn định yếu có kích thước tối đa (MAX-SMTI, MAX-HRT, MAX-SPA) đã được Manlove et al. (2002) chứng minh là bài toán thuộc lớp NP-khó (NP-hard), thậm chí không thể đạt tỷ lệ xấp xỉ nhỏ hơn $21/19 - \epsilon$ trừ khi $\text{P} = \text{NP}$ (Halldórsson et al., 2007).

Nghiên cứu sinh Nguyễn Thị Uyên, dưới sự hướng dẫn của PGS. Hoàng Hữu Việt và PGS.TS. Nguyễn Long Giang tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam (chuyên ngành Khoa học Máy tính, Mã số: 9 48 01 01), đã hoàn thành luận án tiến sĩ với đề tài: "Nghiên cứu một số biến thể của bài toán hôn nhân ổn định theo tiếp cận heuristic". Luận án giải quyết triệt để research gap lớn trong tối ưu hóa tổ hợp: sự bế tắc của các thuật toán xấp xỉ truyền thống (vốn bị chặn ở tỷ lệ xấp xỉ $3/2$ và cho ra tỷ lệ ghép hoàn chỉnh thấp) và sự bùng nổ không gian trạng thái của các thuật toán tìm kiếm cục bộ trước đây (như LTIU của Gelain et al., 2010 với độ phức tạp $O(n^2)$ cho mỗi bước lân cận). Bằng cách khai thác thuộc tính hình thức của Cặp chặn trội nhất (Undominated Blocking Pairs - UBP), luận án đã thiết lập 6 thuật toán heuristic đột phá: MCS, HR cho MAX-SMTI; MCA, HS cho MAX-HRT; SPA-P-heuristic và HAG cho MAX-SPA. Hệ thống thuật toán được kiểm chứng trên các không gian dữ liệu mở rộng với quy mô lên tới $n = 10.000$ tác nhân, khẳng định bước tiến vượt bậc về cả chất lượng nghiệm tối đa lẫn hiệu năng thời gian xử lý.

                  +-------------------------------------------------------------+
                  |                 KHUNG NGHIÊN CỨU LUẬN ÁN                    |
                  +-------------------------------------------------------------+
                                                 |
         +---------------------------------------+---------------------------------------+
         |                                       |                                       |
+------------------+                   +------------------+                    +------------------+
|     MAX-SMTI     |                   |     MAX-HRT      |                    |     MAX-SPA      |
| One-to-One Ties  |                   | One-to-Many Ties |                    | 3-Tier Multi-Cap |
+------------------+                   +------------------+                    +------------------+
         |                                       |                                       |
   +-----+-----+                           +-----+-----+                           +-----+-----+
   |           |                           |           |                           |           |
+------+   +------+                    +------+   +------+                    +------+   +------+
| MCS  |   |  HR  |                    | MCA  |   |  HS  |                    |SPA-P |   | HAG  |
|Alg.  |   | Alg. |                    | Alg. |   | Alg. |                    | Heur.|   | Alg. |
+------+   +------+                    +------+   +------+                    +------+   +------+

Literature Review và Positioning

Lịch sử phát triển của lý thuyết ghép cặp ổn định ghi nhận cột mốc khởi nguyên từ thuật toán chấp nhận trì hoãn (Deferred Acceptance) của Gale và Shapley (1962), giải quyết bài toán SMP trong thời gian $O(n^2)$. Thuật toán GS nguyên bản tạo ra phép ghép tối ưu cực đoan cho một phía: hoặc tối ưu cho nam giới (man-optimal) - nơi người đề xuất đạt được lựa chọn tốt nhất có thể trong tập nghiệm ổn định, hoặc tối ưu cho nữ giới (woman-optimal) - nơi phía nhận đề xuất phải chấp nhận phương án tồi nhất. Khi mở rộng sang bài toán có danh sách không đầy đủ (SMI), Gale-Shapley vẫn tìm được phép ghép ổn định trong thời gian tuyến tính và mọi phép ghép ổn định đều có cùng kích thước lực lượng (Gale & Sotomayor, 1985).

Tuy nhiên, bước ngoặt lý thuyết xuất hiện khi Irving (1994) và sau đó là Iwama et al. (1999) đưa quan hệ ngang hàng vào mô hình (SMT và SMTI). Sự xuất hiện của các khối ưu tiên bằng nhau (indifference/ties) phá vỡ cấu trúc đại số dạng lưới (distributive lattice) của tập hợp các phép ghép ổn định. Irving et al. (2000, 2008) chỉ ra rằng bài toán phân tách thành ba khái niệm ổn định:

  • Ổn định yếu (Weak stability): Không tồn tại cặp $(m_i, w_j)$ nào mà cả hai cùng nghiêm ngặt thích nhau hơn người phối ngẫu hiện tại.
  • Ổn định mạnh (Strong stability): Không tồn tại cặp $(m_i, w_j)$ mà một bên nghiêm ngặt thích hơn, còn bên kia thích ít nhất là bằng người hiện tại.
  • Siêu ổn định (Super stability): Không tồn tại cặp $(m_i, w_j)$ mà cả hai cùng thích nhau ít nhất là bằng người phối ngẫu hiện tại.

Về phương diện độ phức tạp tính toán, Manlove et al. (2002) đã chứng minh định lý nền tảng: bài toán tìm phép ghép ổn định yếu có kích thước lớn nhất (MAX-SMTI) và bài toán phân bổ bác sĩ - bệnh viện có liên kết ngang hàng (MAX-HRT) là NP-khó, ngay cả khi quan hệ ngang hàng chỉ xuất hiện ở một phía tác nhân hoặc danh sách ưu tiên bị giới hạn nghiêm ngặt. Điều này dẫn tới hai luồng nghiên cứu đối trọng trong y văn quốc tế:

Luồng nghiên cứu thứ nhất tập trung vào thuật toán xấp xỉ đa thức với việc chứng minh chặn trên lý thuyết. Halldórsson et al. (2003, 2007) đề xuất các thuật toán xấp xỉ với tỷ lệ ban đầu $2 - c\frac{\log n}{n}$, sau đó cải tiến lên $13/7 \approx 1.857$. McDermid (2009) tạo nên đột phá khi đưa tỷ lệ xấp xỉ về $3/2$ với độ phức tạp $O(n^{3/2}L)$, sử dụng kỹ thuật mở rộng danh sách kết hợp phạt trạng thái. Tiếp đó, Király (2013) và Paluch (2014) hoàn thiện thuật toán $3/2$-approximation với thời gian tuyến tính thông qua biến thể Gale-Shapley cho phép người đề xuất kích hoạt lại danh sách ưu tiên khi bị từ chối lần đầu (thuật toán GSA2 cho MAX-SMTI và HP cho MAX-HRT). Đối với bài toán SPA-ST, Cooper và Manlove (2018) đã đề xuất thuật toán APX đạt tỷ lệ xấp xỉ $3/2$. Mặc dù đạt được chặn trên lý thuyết xuất sắc, hạn chế cốt tử của luồng tiếp cận xấp xỉ là chất lượng nghiệm thực tế trong các mô phỏng quy mô lớn còn cách xa nghiệm hoàn chỉnh ($|M| = n$), tỷ lệ bỏ sót tác nhân chưa ghép cặp vẫn ở mức cao.

Luồng nghiên cứu thứ hai khai thác các kỹ thuật Heuristic, Metaheuristic và Quy hoạch ràng buộc (Constraint Programming - CP). Gelain et al. (2010, 2013) phát triển thuật toán tìm kiếm cục bộ LTIU khởi tạo từ một phép ghép ngẫu nhiên, sinh ra toàn bộ không gian hoán vị lân cận và đánh giá hàm mục tiêu chi phí. Tuy nhiên, việc quét không gian lân cận của LTIU đòi hỏi chi phí $O(n^2)$ cho mỗi bước lặp, khiến thuật toán cạn kiệt tài nguyên tính toán khi kích thước mẫu $n > 200$. Munera et al. (2015) mô hình hóa MAX-SMTI thành bài toán thỏa mãn ràng buộc (CSP) và giải bằng thuật toán tìm kiếm thích nghi (Adaptive Search - AS), lựa chọn biến có độ lỗi cao nhất để hoán đổi và kết hợp cơ chế tái khởi động (resets) khi rơi vào cực tiểu cục bộ. Dù vượt trội hơn LTIU và thuật toán xấp xỉ của McDermid (2009), AS vẫn bộc lộ độ trễ lớn và suy giảm tỷ lệ ghép hoàn chỉnh khi xác suất quan hệ ngang hàng $p_2 \to 1$. Các hướng tiếp cận quy hoạch nguyên (ILP) của Kwanashie et al. (2013, 2020), Delorme et al. (2019) hay mô hình SAT của Drummond et al. (2015, 2020) cho nghiệm chính xác nhưng bị quá tải bộ nhớ trên các không gian bài toán quy mô công nghiệp.

Vị trí học thuật của luận án Nguyễn Thị Uyên được xác lập chính xác tại giao điểm giữa tối ưu hóa tổ hợp và trí tuệ nhân tạo: thay vì sinh lân cận mù quáng ($O(n^2)$) như LTIU hoặc giải tỏa xung đột từng biến đơn lẻ như AS, tác giả xây dựng lý thuyết tập hợp Cặp chặn trội nhất (Undominated Blocking Pairs - UBP), từ đó thiết kế các toán tử heuristic có khả năng triệt tiêu đồng thời toàn bộ các chuỗi xung đột phụ thuộc, mở rộng phạm vi xử lý thực nghiệm vượt xa các công bố quốc tế đương thời.

Tiêu chí so sánh Thuật toán GS (Gale & Shapley, 1962) Thuật toán GSA2 / HP (Király, 2013) Thuật toán LTIU (Gelain et al., 2010) Thuật toán AS (Munera et al., 2015) Luận án Nguyễn Thị Uyên (MCS / HS / HAG, 2023)
Phạm vi mô hình SMP (Strict, Complete) MAX-SMTI / MAX-HRT MAX-SMTI MAX-SMTI / MAX-HRT MAX-SMTI, MAX-HRT, MAX-SPA-P, MAX-SPA-ST
Bản chất thuật toán Khớp nối chính xác 1 phía Xấp xỉ đa thức ($3/2$-approx) Tìm kiếm cục bộ (Local Search) Tìm kiếm thích nghi (Adaptive Search) Heuristic khai thác xung đột cực đại (UBP-based)
Xử lý quan hệ ngang hàng Không hỗ trợ Phá vỡ ties tĩnh / ngẫu nhiên Tìm kiếm lân cận toàn phần Hàm lỗi CSP Cặp chặn trội nhất (Undominated Blocking Pair)
Độ phức tạp bước lặp $O(1)$ mỗi đề xuất Tuyến tính $O(L)$ $O(n^2)$ sinh lân cận $O(n)$ cập nhật biến lỗi $O(|X|)$ co cụm tập UBP
Quy mô thực nghiệm $n \le 1.000$ Mô phỏng giới hạn $n \le 200$ $n \le 500$ $n \le 10.000$; $m \le 200$; $q \le 1.000$

Đóng góp lý thuyết và khung phân tích

+-----------------------------------------------------------------------------------+
|               ĐÓNG GÓP LÝ THUYẾT & KHUNG PHÂN TÍCH TOÁN HỌC                       |
+-----------------------------------------------------------------------------------+
| 1. Bổ đề Triệt tiêu Cặp chặn:                                                     |
|    Loại bỏ (m_i, w_j) \in UBP_M  ==>  Mọi (m_i, w_k) bị triệt tiêu trong M'       |
|                                                                                   |
| 2. Hàm Heuristic Tuyến tính hóa:                                                 |
|    h(m_i) = n * ubp(w_j) - rank(w_j, m_i)                                         |
|                                                                                   |
| 3. Chuyển vị Trạng thái Đa cấp:                                                   |
|    Cân bằng đồng thời ràng buộc hạn ngạch đề tài (c_j) và giảng viên (d_k)       |
+-----------------------------------------------------------------------------------+

Đóng góp cho lý thuyết

Luận án đóng góp trực tiếp vào lý thuyết tối ưu hóa tổ hợp thông qua việc hình thức hóa các định lý và cấu trúc triệt tiêu xung đột trong bài toán ghép cặp có liên kết ngang hàng:

  1. Khái niệm và Tính chất Cặp chặn Trội nhất (Undominated Blocking Pair - UBP): Trong một thể hiện SMTI với phép ghép không ổn định $M$, một cặp chặn $(m_i, w_j) \in M \times W$ được định nghĩa là vượt trội (dominate) cặp chặn $(m_i, w_k)$ theo thứ tự ưu tiên của $m_i$ nếu $\text{rank}(m_i, w_j) < \text{rank}(m_i, w_k)$. Cặp $(m_i, w_j)$ là Cặp chặn trội nhất ($UBP$) nếu không tồn tại bất kỳ cặp chặn $(m_i, w_k)$ nào thỏa mãn $\text{rank}(m_i, w_k) < \text{rank}(m_i, w_j)$. Luận án chứng minh chặt chẽ tính chất toán học: "Nếu ta xóa một cặp chặn trội nhất $(m_i, w_j)$ khỏi phép ghép $M$ để thu được phép ghép mới $M'$ (trong đó gán $M'(m_i) = w_j$, chuyển các đối tác cũ $M(m_i)$ và $M(w_j)$ về trạng thái tự do $\emptyset$), thì toàn bộ các cặp chặn khác được hình thành bởi $m_i$ sẽ bị xóa bỏ hoàn toàn trong $M'$". Điều này tạo ra một cơ chế suy giảm đơn điệu bậc cao số lượng xung đột trong mạng ghép cặp.

  2. Hàm Heuristic Trọng số hóa Tác động Xung đột cực đại: Để định lượng mức độ giải phóng không gian tìm kiếm, luận án xây dựng hàm đánh giá heuristic $h(m_i)$ trên tập hợp các cặp chặn trội nhất $X = {(m_i, w_j) \mid m_i \in M, w_j \in W}$: $$h(m_i) = n \times ubp(w_j) - \text{rank}(w_j, m_i)$$ Trong đó $ubp(w_j)$ là tổng số lần người nữ $w_j$ tham gia vào các cặp chặn trội nhất trong tập $X$, và $n$ là quy mô của thể hiện. Việc nhân hệ số quy mô $n$ với $ubp(w_j)$ đảm bảo thuật toán luôn ưu tiên chọn các nút thắt xung đột mang tính nút mạng (hub-conflicts) - tức những tác nhân nữ bị cạnh tranh gay gắt nhất, đồng thời cực tiểu hóa mức độ thất vọng của đối tác thông qua đại lượng $\text{rank}(w_j, m_i)$.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp sâu sắc ba hệ thống lý thuyết: Lý thuyết Ghép cặp ổn định kinh điển (Gale-Shapley Stability Theory), Lý thuyết Thỏa mãn Ràng buộc (Constraint Satisfaction Framework) và Lý thuyết Tìm kiếm Heuristic cục bộ có cấu trúc (Structured Heuristic Local Search).

Sự độc đáo trong khung phân tích của tác giả thể hiện qua các chiều cạnh:

  • Cơ chế thu hẹp không gian tìm kiếm: Thay vì duyệt qua toàn bộ $O(n^2)$ cấu hình lân cận như các phương pháp metaheuristic thông thường, thuật toán co cụm không gian trạng thái về tập nghiệm thỏa hiệp chỉ chứa các cặp thuộc $UBP$.
  • Cơ chế chuyển tiếp trạng thái đa cấp cho SPA: Đối với mô hình 3 tác nhân trong bài toán SPA (Sinh viên $S$, Đề tài $P$, Giảng viên $L$), khung phân tích thiết lập điều kiện biên kép (dual boundary conditions): kiểm soát đồng thời hạn ngạch đề tài $c_j$ ($|M(p_j)| \le c_j$) và hạn ngạch giảng viên $d_k$ ($|M(l_k)| \le d_k$). Cặp chặn trong SPA-ST được hình thức hóa thành các biểu thức logic phân tầng, cho phép toán tử heuristic HAG cập nhật trạng thái gán ghép mà không làm vi phạm tính khả thi toàn cục.

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Nghiên cứu tuân thủ chặt chẽ lập trường thực chứng luận (positivism paradigm) với tư duy duy lý toán học kết hợp phương pháp thực nghiệm tính toán (computational experimental method). Thiết kế nghiên cứu được cấu trúc thành hệ thống 3 pha tương hỗ:

+---------------------------------------------------------------------------------+
|                         THIẾT KẾ NGHIÊN CỨU 3 PHA RIGOROUS                      |
+---------------------------------------------------------------------------------+
|  PHA 1: Toán học hóa và Xây dựng Thuật toán                                    |
|  - Định nghĩa không gian trạng thái, quan hệ trội UBP, hàm Heuristic h(m_i).   |
|  - Thiết kế 6 thuật toán: MCS, HR, MCA, HS, SPA-P-heuristic, HAG.               |
+---------------------------------------------------------------------------------+
                                       |
                                       v
+---------------------------------------------------------------------------------+
|  PHA 2: Sinh dữ liệu Chuẩn hóa Phổ biến (Gent et al. Protocol)                  |
|  - Tham số hóa: (n, p_1, p_2) cho SMTI; (n, m, p_1, p_2, c_j) cho HRT.          |
|  - Đa biến: (n, m, q, p_1, p_2, c_j, d_k) cho SPA-P và SPA-ST.                 |
+---------------------------------------------------------------------------------+
                                       |
                                       v
+---------------------------------------------------------------------------------+
|  PHA 3: Khảo sát Thực nghiệm, Benchmarking Đối chứng Đa chiều                   |
|  - Đo lường: Thời gian CPU (s), Tỷ lệ ổn định (%), Tỷ lệ hoàn chỉnh (|M|=n).    |
|  - Đối chứng trực tiếp: LTIU, AS, GSA2, GS, HP, APX trên MATLAB 2019a.         |
+---------------------------------------------------------------------------------+

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu triển khai giao thức kiểm soát biến số thực nghiệm nghiêm ngặt dựa trên quy chuẩn của Gent et al. (2001, 2002):

  • Giao thức sinh dữ liệu SMTI: Bộ sinh ngẫu nhiên thiết lập trên vector bộ ba $(n, p_1, p_2)$. Trong đó $n$ đại diện quy mô mẫu ($n \in [100, 700]$ cho các so sánh chi tiết và lên tới $n = 10.000$ cho kiểm tra độ co giãn); $p_1 \in [0, 1]$ là xác suất tạo danh sách không đầy đủ; $p_2 \in [0, 1]$ là xác suất hình thành quan hệ ngang hàng (ties). Mọi thể hiện sinh ra đều đảm bảo tính chấp nhận hai chiều: $\text{rank}(m_i, w_j) > 0 \iff \text{rank}(w_j, m_i) > 0$.
  • Giao thức sinh dữ liệu HRT: Thiết lập trên bộ tham số $(n, m, p_1, p_2, c_j)$ với $n$ sinh viên, $m$ doanh nghiệp/bệnh viện, năng lực tiếp nhận $c_j = n/m$ hoặc $c_j$ biến thiên ngẫu nhiên theo phân phối đều.
  • Giao thức sinh dữ liệu SPA-P và SPA-ST: Tích hợp 7 tham số $(n, m, q, p_1, p_2, c_j, d_k)$ phản ánh chính xác cấu trúc thực tế của trường đại học, trong đó $q$ là số lượng đề tài, $d_k$ là trần tiếp nhận của giảng viên $l_k$ thỏa mãn $\sum c_j \ge \sum d_k \ge n$.
  • Độ tin cậy và Tính lặp lại (Reliability & Triangulation): Mỗi điểm thực nghiệm với bộ tham số cố định được lặp lại độc lập từ 100 đến 1.000 thể hiện ngẫu nhiên khác nhau để triệt tiêu sai số phương sai. Các chỉ số đo lường bao gồm:
    1. Thời gian thực hiện trung bình (Execution Time - tính bằng giây).
    2. Phần trăm tìm thấy phép ghép ổn định (Percentage of Stable Matchings).
    3. Phần trăm tìm thấy phép ghép hoàn chỉnh (Percentage of Complete Matchings - $|M| = n$).
    4. Số bước lặp trung bình và số lần gọi hàm khởi tạo lại (Resets).

Data và phân tích

Toàn bộ hệ thống thuật toán đề xuất cùng các thuật toán đối chứng chuẩn quốc tế đều được lập trình đồng nhất trên nền tảng MATLAB 2019a, thực thi trên cùng một môi trường phần cứng chuẩn tắc: máy tính cá nhân trang bị bộ vi xử lý Intel Core i7-8550U 1.8GHz, 16 GB RAM, hệ điều hành Linux/Windows. Việc cô lập hoàn toàn môi trường tính toán đảm bảo tính khách quan tuyệt đối cho các chỉ số so sánh hiệu năng CPU time.

Dữ liệu thực nghiệm phân tích sâu cấu trúc ma trận chuyển trạng thái, theo dõi động lực học hội tụ của hàm heuristic $h(m_i)$, biểu đồ hóa tương quan giữa mức độ liên kết ngang hàng $p_2$ và độ suy giảm tài nguyên tính toán.

Phát hiện đột phá và implications

Những phát hiện then chốt

Kết quả thực nghiệm mô phỏng trên hàng triệu lượt chạy dữ liệu đã đem lại các phát hiện đột phá:

+-----------------------------------------------------------------------------------+
|                     TỔNG HỢP CÁC PHÁT HIỆN THỰC NGHIỆM ĐỘT PHÁ                    |
+-----------------------------------------------------------------------------------+
|  1. Giải quyết bài toán "Thắt nút cổ chai" của LTIU:                              |
|     Khi n = 100, p_2 = 1.0: LTIU mất 178.6s | MCS chỉ mất 0.042s (Nhanh gấp 4200x)|
|                                                                                   |
|  2. Đột phá Tỷ lệ Hoàn chỉnh (|M| = n) tại vùng cực hạn p_2 = 1.0:               |
|     Thuật toán AS: Đạt 0% phép ghép hoàn chỉnh                                    |
|     Thuật toán MCS / HR: Đạt xấp xỉ 100% phép ghép hoàn chỉnh                    |
|                                                                                   |
|  3. Vượt trội Thuật toán Xấp xỉ Tốt nhất (GSA2, HP, APX):                         |
|     - HR vượt GSA2 từ 5% đến 18% về tỷ lệ hoàn chỉnh trên mọi dải p_1, p_2.        |
|     - HAG giảm số sinh viên mất lượt gán ghép về tiệm cận 0 khi n = 10.000.      |
|                                                                                   |
|  4. Năng lực Khả năng Mở rộng Quy mô Vượt bậc:                                    |
|     HAG xử lý bài toán SPA-ST quy mô khổng lồ (n=10000, m=200, q=1000)            |
|     chỉ trong thời gian trung bình < 3.2 giây.                                    |
+-----------------------------------------------------------------------------------+

  1. Phá vỡ điểm nghẽn thời gian tính toán của tiếp cận Tìm kiếm cục bộ: Đối với bài toán MAX-SMTI, khi so sánh trực tiếp với thuật toán tìm kiếm cục bộ LTIU (Gelain et al., 2010), thuật toán MCS thể hiện sự vượt trội mang tính hủy diệt về tốc độ hội tụ. Ở quy mô $n = 100$ và tham số $p_2 = 1.0$, LTIU tiêu tốn trung bình 178.6 giây và tỷ lệ tìm thấy phép ghép hoàn chỉnh suy giảm, trong khi thuật toán MCS chỉ mất 0.042 giây (nhanh hơn gấp hơn 4.200 lần) và luôn đạt tỷ lệ tìm thấy phép ghép hoàn chỉnh tuyệt đối $100%$.

  2. Khắc phục triệt để hiện tượng kẹt cực tiểu cục bộ của Thuật toán Tìm kiếm Thích nghi (AS): Khi tham số quan hệ ngang hàng đạt cực đại ($p_2 = 1.0$, tức mức độ xung đột lợi ích cao nhất), thuật toán AS của Munera et al. (2015) hoàn toàn mất khả năng tìm thấy phép ghép hoàn chỉnh (tỷ lệ đạt 0%) do bị rơi vào bẫy cực tiểu địa phương liên tục và phải kích hoạt hàng ngàn lần hàm tái khởi tạo (resets). Ngược lại, thuật toán MCS và HR do tác giả đề xuất duy trì tỷ lệ tìm thấy phép ghép hoàn chỉnh xấp xỉ $100%$, với số bước lặp hội tụ trung bình ít hơn AS tới $95%$.

  3. Chất lượng nghiệm vượt trội so với các Thuật toán Xấp xỉ $3/2$ tốt nhất thế giới: Khi đối chứng với thuật toán GSA2 của Király (2013) trên bài toán MAX-SMTI và thuật toán HP trên bài toán MAX-HRT, thuật toán sửa đổi Heuristic Repair (HR) và Heuristic Search (HS) của luận án đạt tỷ lệ kích thước phép ghép cao hơn vượt bậc. Cụ thể, trong các thể hiện dày đặc quan hệ ngang hàng, GSA2 chỉ đạt tỷ lệ hoàn chỉnh từ $82% - 94%$, trong khi HR đạt từ $98% - 100%$. Tương tự, đối với bài toán MAX-SPA-ST, thuật toán HAG áp đảo thuật toán xấp xỉ APX của Cooper và Manlove (2018): APX để lại số lượng sinh viên chưa được ghép trung bình từ $12 - 28$ sinh viên trên mỗi thể hiện $n = 500$, trong khi HAG giải quyết triệt để, đưa số lượng sinh viên không được ghép về tiệm cận $0$.

  4. Năng lực mở rộng quy mô siêu lớn (Scalability): Luận án thực hiện các kiểm thử chưa từng có tiền lệ trong các nghiên cứu trước đây về SPA-ST với kích thước mẫu lên tới $n = 10.000$ sinh viên, $m = 200$ giảng viên, $q = 1.000$ đề tài. Thuật toán HAG hoàn thành việc tìm kiếm phép ghép ổn định hoàn chỉnh chỉ trong thời gian trung bình dưới 3.2 giây, mở ra khả năng ứng dụng trực tiếp trong thời gian thực (real-time matching engines).

Implications đa chiều

  • Về mặt Lý thuyết Thuật toán: Chứng minh rằng trong các bài toán tối ưu hóa tổ hợp NP-khó có cấu trúc ràng buộc phân tầng, việc định hướng toán tử heuristic dựa trên tính vượt trội của xung đột (Dominated Conflict Analysis) mang lại hiệu quả vượt trội so với việc tìm kiếm ngẫu nhiên có định hướng hoặc giải quyết ràng buộc thuần túy.
  • Về mặt Phương pháp luận: Cung cấp khung phương pháp luận hoàn chỉnh kết hợp giữa khai phá cấu trúc toán học trừu tượng (đồ thị phân đôi, quan hệ thứ tự bán phần) với thuật giải tìm kiếm heuristic, đóng vai trò như một cẩm nang thiết kế thuật toán cho các biến thể mở rộng khác như ghép cặp có nhóm tác nhân (Couples Matching) hay ghép cặp đa chiều.
  • Về mặt Ứng dụng Thực tiễn và Quản trị: Cung cấp giải pháp tối ưu cho các hệ thống phần mềm chuyển đổi số quốc gia:
    1. Y tế: Phân bổ chính xác hàng chục nghìn bác sĩ thực tập vào các bệnh viện trung ương và địa phương theo đúng năng lực chuyên môn và hạn ngạch khoa phòng.
    2. Giáo dục đại học: Tự động hóa hoàn toàn quy trình phân công đồ án tốt nghiệp cho sinh viên tại các đại học quy mô lớn, thỏa mãn tối đa nguyện vọng học thuật của người học và định hướng nghiên cứu của giảng viên.
    3. Kinh tế - Viễn thông: Ứng dụng trong việc phân bổ tài nguyên băng thông, ghép nối máy chủ biên (Edge Computing) và tối ưu hóa các yêu cầu dịch vụ Internet (QoS Routing).

Limitations và Future Research

Mặc dù đạt được những bước tiến vượt bậc, luận án cũng ghi nhận một số giới hạn học thuật mang tính khách quan:

  • Giới hạn về Chặn dưới Lý thuyết: Thuật toán heuristic MCS, HR, HS, HAG mang bản chất xấp xỉ kinh nghiệm (empirical heuristics), do đó chưa thiết lập được chứng minh toán học hình thức về tỷ lệ xấp xỉ cận dưới xấu nhất (worst-case approximation bound) như các thuật toán giải tích thuần túy ($3/2$-approximation).
  • Phạm vi Ràng buộc Phi tuyến tính: Nghiên cứu tập trung vào các ràng buộc hạn ngạch cứng cố định ($c_j, d_k$) và ưu tiên đơn chiều; chưa tích hợp các ràng buộc động phức tạp như cặp đôi phụ thuộc (Couples Matching with interdependent preferences) - nơi hai tác nhân mong muốn được phân bổ cùng một vị trí địa lý.
  • Phân phối Dữ liệu: Các thực nghiệm chủ yếu dựa trên bộ dữ liệu sinh ngẫu nhiên chuẩn hóa theo phân phối đều của Gent et al.; cấu trúc tương quan sở thích thực tế (correlated/master preferences) trong các thị trường cụ thể có thể tạo ra các phân phối cụm (clustered preferences) cần được khảo sát sâu hơn.

Chương trình nghiên cứu tương lai (Future Research Agenda) mở ra 4 hướng đi chiến lược:

  1. Nghiên cứu kết hợp cơ chế học tăng cường (Reinforcement Learning) để tự động điều chỉnh siêu tham số hàm heuristic $h(m_i)$ theo thời gian thực dựa trên đồ thị xung đột của từng thể hiện cụ thể.
  2. Mở rộng khung thuật toán sang bài toán ghép cặp có ràng buộc hạn ngạch dưới (Lower Quota Bounds) và bài toán ghép cặp cặp đôi (Stable Marriage with Couples - SMC), vốn là thách thức lớn nhất trong hệ thống ghép cặp y khoa Hoa Kỳ.
  3. Song song hóa thuật toán trên kiến trúc GPU/Phân tán (Distributed High-Performance Computing) để xử lý các bài toán ghép cặp thị trường lao động quy mô hàng triệu tác nhân.
  4. Xây dựng chứng minh lý thuyết xác định chặn xấp xỉ trung bình (average-case approximation ratio) cho thuật toán MCS trên các không gian dữ liệu ngẫu nhiên.

Tác động và ảnh hưởng

Luận án của NCS Nguyễn Thị Uyên mang lại giá trị tác động toàn diện:

  • Tác động Học thuật: Các kết quả cốt lõi của luận án đã được công bố trên các tạp chí và hội thảo chuyên ngành quốc tế uy tín, bao gồm tạp chí thuộc danh mục SCIE Q2 (Journal of Heuristics, IF = 2.247) và các kỷ yếu hội nghị quốc tế uy tín thuộc danh mục Scopus như Australasian Joint Conference on Artificial Intelligence (AJCAI), International Conference on Computing and Communication Technologies (RIVF), Computational Data and Social Networks (CSoNet). Công trình tạo tiền đề trích dẫn quan trọng cho cộng đồng tối ưu hóa tổ hợp và trí tuệ nhân tạo trong và ngoài nước.
  • Tác động Chuyển đổi Số Giáo dục & Y tế: Cung cấp thuật toán lõi có thể nhúng trực tiếp vào các hệ thống ERP quản lý đào tạo đại học (giải quyết bài toán phân công đề tài tốt nghiệp cho hàng vạn sinh viên mỗi học kỳ) và hệ thống phân bổ nhân lực y tế tuyến đầu, loại bỏ hoàn toàn sự can thiệp cảm tính, tối đa hóa tính minh bạch và công bằng xã hội.
  • Tác động Kinh tế - Xã hội: Tối ưu hóa việc phân bổ nguồn lực giúp giảm thiểu lãng phí nhân lực trình độ cao, nâng cao chỉ số hài lòng của các tác nhân tham gia thị trường ghép cặp (market design efficiency).

Đối tượng hưởng lợi

  • Nghiên cứu sinh & Giới Viện - Trường (Academic Researchers): Tiếp cận một khung phân tích heuristic đột phá dựa trên lý thuyết Cặp chặn trội nhất (UBP); kế thừa tập mã nguồn và giao thức sinh dữ liệu chuẩn mực để phát triển các bài toán tối ưu tổ hợp phức tạp hơn.
  • Bộ phận Quản lý Đào tạo Đại học (University Academic Affairs): Sở hữu giải pháp công nghệ tự động hóa tối ưu cho quy trình phân bổ đồ án/khóa luận tốt nghiệp sinh viên (SPA), cân bằng hoàn hảo giữa năng lực hướng dẫn của giảng viên và sở thích nghiên cứu của sinh viên.
  • Cơ quan Quản lý Y tế & Bệnh viện (Healthcare Administration): Ứng dụng mô hình HRT để điều phối bác sĩ nội trú, nhân viên y tế vào các cơ sở khám chữa bệnh dựa trên năng lực và nhu cầu thực tế mà không gây quá tải hạn ngạch chuyên môn.
  • Kỹ sư R&D Doanh nghiệp Công nghệ (Tech R&D Teams): Ứng dụng thuật giải phân bổ tài nguyên tối ưu trong các hệ thống mạng phân tán, định tuyến điện toán đám mây, các nền tảng tuyển dụng lao động thông minh và các sàn giao dịch việc làm trực tuyến.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và nó mở rộng lý thuyết nào?

Đóng góp lý thuyết độc đáo nhất của luận án là việc hình thức hóa cấu trúc toán học của Cặp chặn trội nhất (Undominated Blocking Pair - UBP) và chứng minh định lý triệt tiêu chuỗi xung đột: loại bỏ một cặp UBP $(m_i, w_j)$ sẽ xóa bỏ toàn bộ các cặp chặn liên kết do tác nhân $m_i$ tạo ra trong không gian lân cận. Khám phá này mở rộng trực tiếp Lý thuyết Ghép cặp ổn định của Gale và Shapley (1962) cũng như Lý thuyết Tính ổn định yếu trong SMTI của Irving et al. (2000, 2008), chuyển hóa việc giải quyết bài toán NP-khó từ duyệt tìm lân cận toàn phần ($O(n^2)$) sang việc điều hướng xung đột cục bộ có mục tiêu chính xác ($O(|X|)$).

2. Sự đổi mới về phương pháp luận của luận án so với ít nhất 2 nghiên cứu quốc tế tiền nhiệm?

So với thuật toán tìm kiếm cục bộ LTIU của Gelain et al. (2010), phương pháp luận của luận án đổi mới bằng cách loại bỏ hoàn toàn việc sinh $O(n^2)$ trạng thái lân cận mù quáng, thay thế bằng toán tử chọn lọc UBP có định hướng, giúp giảm thời gian thực thi hàng nghìn lần (từ 178.6s xuống 0.042s khi $n=100, p_2=1.0$). So với thuật toán tìm kiếm thích nghi AS của Munera et al. (2015), luận án đổi mới hàm đánh giá heuristic $h(m_i) = n \times ubp(w_j) - \text{rank}(w_j, m_i)$ tích hợp trọng số mạng lưới, giải quyết triệt để tình trạng kẹt cực tiểu cục bộ khi $p_2 \to 1$ (nơi AS rơi vào tỷ lệ hoàn chỉnh 0%, còn MCS đạt ~100%).

3. Phát hiện thực nghiệm nào gây bất ngờ nhất và có minh chứng định lượng cụ thể?

Phát hiện bất ngờ nhất nằm ở năng lực duy trì chất lượng nghiệm hoàn hảo tại vùng biên khắc nghiệt nhất: khi xác suất quan hệ ngang hàng đạt tối đa ($p_2 = 1.0$) - trạng thái vốn làm tê liệt hầu hết các thuật toán trước đó. Trong điều kiện này, thuật toán Heuristic Repair (HR) và MCS của luận án vẫn đạt tỷ lệ tìm thấy phép ghép hoàn chỉnh xấp xỉ 100%, trong khi thuật toán xấp xỉ tiên tiến GSA2 (Király, 2013) chỉ đạt khoảng $85%$ và AS (Munera et al., 2015) đạt $0%$.

4. Luận án có cung cấp giao thức tái lập thực nghiệm (Replication Protocol) hoàn chỉnh không?

Luận án cung cấp giao thức thực nghiệm cực kỳ chi tiết và minh bạch:

  • Giao thức sinh dữ liệu ngẫu nhiên dựa trên thuật toán hình thức của Gent et al. (2001) được mô tả đầy đủ mã giả tại Phụ lục A.2.
  • Đặc tả chính xác các không gian tham số: vector $(n, p_1, p_2)$ cho SMTI; $(n, m, p_1, p_2, c_j)$ cho HRT; $(n, m, q, p_1, p_2, c_j, d_k)$ cho SPA.
  • Cấu hình phần cứng thực thi (CPU Intel Core i7-8550U 1.8GHz, 16GB RAM) và môi trường phần mềm (MATLAB 2019a) được công bố rõ ràng, cho phép bất kỳ nhóm nghiên cứu độc lập nào cũng có thể tái lập chính xác các kết quả thực nghiệm.

5. Chương trình nghiên cứu 10 năm (10-year Research Agenda) được phác thảo như thế nào?

Chương trình nghiên cứu dài hạn định hướng chuyển dịch từ các mô hình heuristic tĩnh sang:

  • Xây dựng hệ thống giải thuật Ghép cặp Tự thích ứng điều khiển bởi AI (AI-driven Self-Adaptive Matching), tích hợp Graph Neural Networks (GNN) và Reinforcement Learning để tự động học biểu diễn không gian xung đột.
  • Giải quyết bài toán ghép cặp đa chiều động (Dynamic Multi-sided Matching) có tính đến yếu tố thời gian và sự thay đổi sở thích liên tục của các tác nhân.
  • Hoàn thiện khung chứng minh toán học cho chặn xấp xỉ trung bình và xây dựng nền tảng phần mềm mã nguồn mở chuẩn quốc tế phục vụ bài toán ghép cặp tài nguyên quy mô quốc gia.

Kết luận

  1. Giải quyết toàn diện 3 bài toán NP-khó cốt lõi: Luận án đã nghiên cứu và giải quyết trọn vẹn bài toán tìm phép ghép ổn định yếu có kích thước tối đa cho ba mô hình biến thể quan trọng nhất: MAX-SMTI, MAX-HRT và MAX-SPA (bao gồm cả MAX-SPA-P và MAX-SPA-ST).
  2. Đề xuất hệ thống 6 thuật toán heuristic đột phá: Xây dựng thành công các thuật toán MCS, HR, MCA, HS, SPA-P-heuristic và HAG; chứng minh tính ưu việt tuyệt đối về cả thời gian chạy CPU và kích thước phép ghép ổn định so với các thuật toán xấp xỉ và tìm kiếm cục bộ hàng đầu thế giới (GS, GSA2, HP, APX, LTIU, AS).
  3. Đóng góp lý thuyết Cặp chặn trội nhất (UBP): Xác lập bổ đề triệt tiêu xung đột UBP và hàm mục tiêu heuristic tích hợp trọng số quy mô $h(m_i)$, cung cấp một công cụ giải tích sắc bén giúp thu hẹp đột phá không gian tìm kiếm tổ hợp.
  4. Mở rộng quy mô khảo sát thực nghiệm kỷ lục: Thực nghiệm thành công trên không gian dữ liệu khổng lồ với quy mô lên tới $n = 10.000$ tác nhân, khẳng định năng lực ứng dụng thực tế vượt bậc trong các bài toán chuyển đổi số phân bổ y tế và giáo dục.
  5. Mở ra 3 luồng nghiên cứu mới: Đặt nền móng cho các hướng phát triển tiếp theo về: ghép cặp có ràng buộc cặp đôi (Couples Matching), ghép cặp tối ưu bằng Trí tuệ nhân tạo/Học tăng cường, và thuật toán song song hóa trên kiến trúc tính toán hiệu năng cao.
  6. Giá trị công bố quốc tế vững chắc: Toàn bộ các thuật toán cốt lõi đều đã được phản biện độc lập và công bố trên các tạp chí quốc tế chuyên ngành danh giá thuộc hệ thống SCIE (Q2) và các kỷ yếu hội nghị quốc tế uy tín thuộc danh mục Scopus, khẳng định chất lượng khoa học và vị thế học thuật của luận án.