Series: Khóa luận tốt nghiệp và những câu chuyện

Phần: 4 / 5

Khóa luận tốt nghiệp và những câu chuyện - Phần 1: Giới thiệu
Khóa luận tốt nghiệp và những câu chuyện - Phần 2: Định nghĩa bài toán
Khóa luận tốt nghiệp và những câu chuyện - Phần 3: Mô hình hóa bài toán
Khóa luận tốt nghiệp và những câu chuyện - Phần 4: Vấn đề tràn bộ nhớ và cải thiện mô hình
Khóa luận tốt nghiệp và những câu chuyện - Phần 5: Một số thành tựu và cảm nhận cá nhân

1. Vấn đề tràn bộ nhớ#

Mô hình hoàn chỉnh ở phần trước mô tả đúng bài toán, nhưng với dữ liệu thật của một học kỳ thì mô hình có từ 1.3 đến 1.5 triệu biến và 1.7 đến 2 triệu ràng buộc. Mình đã từng lập trình mô hình này và để cho máy tính giải, treo máy qua đêm, hôm sau ngủ dậy thấy máy tính đã chạy được hơn 8 tiếng sau đó bị dừng vì tràn bộ nhớ và quan trọng nhất là vẫn chưa có một nghiệm chấp nhận nào được tìm thấy.

Phản ứng đầu tiên của mình khi đó là chạy lại 1 lần nữa - kết quả vẫn như vậy. Sau đó mình lục tung đống code xem có bug ở đâu không - không tìm thấy gì cả. Vậy là mình ngồi xem lại mô hình - không thấy gì, mô hình đã mô tả rất đúng bài toán, thậm chí còn được thu gọn vì đã phá tính đối xứng rồi.

Cuối cùng mình nhận ra không có gì sai cả, chỉ là kích cỡ bài toán lớn quá không thể giải quyết chỉ trong 1 lần giải được. Và một cách giải quyết rất tự nhiên thôi, to quá không giải quyết được thì chẻ nhỏ ra và giải từng phần một.

2. Chia bài toán thành hai giai đoạn#

Thay vì giải một mô hình khổng lồ duy nhất, bài toán được tách thành 2 giai đoạn và giải lần lượt.

2.1. Số phòng yêu cầu tối thiểu#

Tách giai đoạn dễ khiến giai đoạn 1 xếp thời gian xong nhưng giai đoạn 2 lại không đủ phòng để xếp. Để tránh việc này, định nghĩa số phòng yêu cầu tối thiểu $n_e$ của môn thi $e$ là số phòng ít nhất cần có để chắc chắn đủ chỗ cho môn đó.

Ví dụ với 6 phòng thi sức chứa $10, 10, 20, 20, 30, 30$ , môn thi có $60$ sinh viên cần ít nhất $4$ phòng ( $n_e = 4$ ), vì bất kỳ 4 phòng nào trong 6 phòng trên cũng đủ chỗ. Chỉ cần đảm bảo tại mỗi ca thi, tổng số phòng yêu cầu không vượt quá tổng số phòng thi tối đa $M_r$ thì giai đoạn 2 chắc chắn xếp đủ phòng.

2.2. Mô hình xếp thời gian cho môn thi#

Giữ nguyên biến $x(e, p)$ , $t(e', e, n)$ và hàm mục tiêu ở Phần 3, bỏ hết biến/ràng buộc liên quan đến phòng thi, thêm ràng buộc về số phòng yêu cầu tối thiểu

\begin{aligned} \text{minimize} \quad & \alpha \sum \limits_{s \in S} \sum \limits_{\substack{e \neq e' \\ e, e' \in E_s}} \sum \limits_{n = f(k_e)}^{g(e) - 1} \gamma^{g(e) - n} \cdot t(e', e, n) + \beta \sum \limits_{p \in P_l} \sum \limits_{\substack{e \in E \\ k_e \geq \sigma}} k_e \cdot q_e \cdot x(e, p) \\[0.9em] \text{subject to} \quad & \sum \limits_{p \in P} x(e, p) = 1, \quad \forall e \in E \\[0.6em] & \sum \limits_{e \in E_s} x(e, p) \leq 1, \quad \forall s \in S, p \in P \\[0.6em] & x(e, p) = 0, \quad \forall e \in E, p \in P_e \\[0.6em] & x(e, p) + \sum \limits_{q \in P(p, f(k_e))} x(e', q) \leq 1, \quad \forall s \in S, e \neq e' \in E_s, p \in P \\[0.6em] & \sum \limits_{e \in E} n_e \cdot x(e, p) \leq M_r, \quad \forall p \in P \\[0.6em] & x(e', p) + x(e, p + n) \leq 1 + t(e', e, n), \quad \forall p, p + n \in P, s \in S, e \neq e' \in E_s, f(k_e) \leq n < g(e) \\[0.6em] & x(e, p) \in \{0, 1\}, \quad \forall e \in E, p \in P \\[0.6em] & t(e', e, n) \in \{0, 1\}, \quad \forall s \in S, e \neq e' \in E_s, f(k_e) \leq n < g(e) \end{aligned}

2.3. Mô hình xếp phòng cho môn thi#

Sau khi giải xong giai đoạn 1, với mỗi ca thi $p$ ta có tập $E_p$ các môn thi được xếp vào ca đó. Giai đoạn này chỉ còn cần xếp phòng, với thêm mục tiêu hạn chế tổng số phòng sử dụng (vì $n_e$ luôn $\geq$ số phòng thật sự cần dùng)

\begin{aligned} \text{minimize} \quad & \sum \limits_{r \in R} \sum \limits_{e \in E} y(e, r) \\[0.9em] \text{subject to} \quad & y(e, r) = 0, \quad \forall e \in E, r \in R_e \\[0.6em] & \sum \limits_{r \in R} c_r \cdot y(e, r) \leq q_e, \quad \forall e \in E \\[0.6em] & \sum \limits_{e \in E_p} y(e, r) \leq 1, \quad \forall r \in R, p \in P \\[0.6em] & y(e, r) \in \{0, 1\}, \quad \forall e \in E, r \in R \end{aligned}

2.4. Đánh đổi cho việc chia nhỏ#

Nếu để ý kỹ bạn sẽ thấy việc sử dụng "số phòng yêu cầu tối thiểu" đã khiến mô hình có một lỗ hổng, đó là một số môn sẽ yêu cầu quá nhiều phòng. Hãy xem lại ví dụ với 6 phòng thi sức chứa $10, 10, 20, 20, 30, 30$ , môn thi có $60$ sinh viên. Tất nhiên với 4 phòng thi bất kỳ kiểu gì cũng xếp được môn này nhưng có thể môn này chỉ cần 2 phòng (30, 30) hoặc 3 phòng (10, 20, 30) thôi là đủ rồi.

Mình hoàn toàn nhận thức được điều đó nhưng sau nhiều thử nghiệm với nhiều cách khác nhau mình vẫn chọn làm cách này vì hai lý do sau:

Số lượng phòng trong bộ dữ liệu mình làm việc là dư thừa (tức là mình có thể phân chia phòng thoải mái)
Mối quan tâm chính của bài toán này tại trường Đại học Khoa học Tự nhiên là các vấn đề về thời gian

Sau khi đã chia nhỏ, giai đoạn 2 giải rất nhanh (dưới 1 giây), nhưng giai đoạn 1 vẫn chạy chậm và nghiệm chưa đủ tốt - đó là lý do cho phần tiếp theo.

3. Cải thiện mô hình bằng tìm kiếm địa phương#

Ý tưởng: giải giai đoạn 1 đến khi có một nghiệm khởi tạo chấp nhận được, sau đó lặp lại một khung chung để cải thiện dần - thu hẹp không gian tìm kiếm quanh nghiệm hiện tại theo một "quy tắc riêng" và giải lại, lặp lại quá trình cho đến khi không tìm được nghiệm tốt hơn.

3.1. Kỹ thuật thứ nhất - thu hẹp không gian quanh mỗi môn thi#

Với nghiệm hiện tại, môn thi $e$ đang xếp ở ca thi $p$ . Xây dựng tập $C(e, \rho)$ gồm các ca thi cách $p$ không quá $\rho$ ca ( $\rho$ cho trước) rồi giới hạn mỗi môn thi chỉ được xếp trong tập này. Ví dụ $e$ ở ca $6$ , $\rho = 3$ thì $C(e, 3) = \{3, ..., 9\}$ . Đây chính là "quy tắc riêng" điền vào khung chung ở trên:

3.2. Kỹ thuật thứ hai - cố định các môn đã "ổn"#

Môn thi $e$ được gọi là có thời gian ôn tập tốt nếu mọi sinh viên đăng ký $e$ đều có thời gian ôn tập môn $e$ lớn hơn ngưỡng $\sigma$ cho trước. "Quy tắc riêng" của kỹ thuật này là một phép phân loại cho từng môn thi:

3.3. Thuật toán xếp lịch thi hoàn chỉnh#

Toàn bộ các bài toán quy hoạch hỗn hợp nguyên ở từng bước được giải bằng Gurobi 10.0.

4. Kết luận#

Trên đây là thuật toán cốt lõi cho nghiên cứu của bọn mình, tuy nhiên đây mới chỉ là lý thuyết trên giấy và để có thể đem lại kết quả tốt vẫn cần rất nhiều những kỹ thuật khác liên quan đế cấu trúc dữ liệu và lập trình. Nhưng mình sẽ không trình bày ở đây vì đó là phần mà Quý Anh và Quân đảm nhận. Phần sau sẽ là phần cuối của series, mình sẽ trình bày về các kết quả đạt được của dự án này và một chút cảm nhận cá nhân.

Đọc tiếp Phần 5