Tối ưu ASP theo mức ưu tiên và định danh bộ phạt

1. Khi mức ưu tiên và số lần vi phạm phải được tách rõ

Trong xếp lịch, một phương án có thể giảm số lần giảng viên đổi cơ sở nhưng tăng số lớp muộn. Nếu chính sách muốn xử lý đổi cơ sở trước, có thể mô hình hóa hai cấp tối ưu trong ASP. Cấp lớn được xét trước. Chỉ khi hai lịch bằng nhau ở cấp cao hơn, cấp thấp hơn mới quyết định thứ tự.

Xét lịch A có chi phí (0,4), B có (1,0) và C có (0,6). Nếu ưu tiên thành phần thứ nhất, A và C đứng trước B, rồi A đứng trước C. Nếu cộng hai thành phần với trọng số bằng nhau, B lại thắng. Khi báo cáo cần ghi rõ vector chi phí, thứ tự cấp và đơn vị của từng thành phần.

2. Vì sao hai vi phạm có thể bị cộng thành một?

Giả sử hai lớp L1 và L2 đều vi phạm một quy tắc, mỗi lớp bị phạt 1. Biểu thức #sum { W : phat(L,W) } chỉ dùng trọng số làm bộ giá trị của phần tử tổng. Hai vi phạm cùng tạo bộ (1), nên tổng bằng 1. Thêm mã lớp vào bộ giá trị, #sum { W,L : phat(L,W) }, tạo hai phần tử khác nhau và cho tổng 2.

Câu hỏi mô hình hóa nằm ở cụm “mỗi vi phạm”. Phạt theo lớp dùng mã lớp làm định danh. Phạt theo lớp và tuần phải đưa cả tuần vào khóa. Phạt một lần theo giảng viên và ngày cần hợp nhất nhiều buổi vào cùng một đơn vị trước khi cộng. Chọn khóa quá ngắn làm mất khoản phạt, còn khóa quá chi tiết làm phạt lặp cùng một sự kiện nghiệp vụ.

3. Chạy ví dụ có cả hai cơ chế

% Chạy: python -m clingo asp_uu_tien_va_tuple.lp 0
1 { chon(a); chon(b); chon(c) } 1.
chi_phi(a,0,4). chi_phi(b,1,0). chi_phi(c,0,6).

% Tối thiểu hóa P ở cấp 2, rồi Q ở cấp 1.
:~ chon(X), chi_phi(X,P,_). [P@2,X]
:~ chon(X), chi_phi(X,_,Q). [Q@1,X]

% Hai lớp khác nhau cùng chịu mức phạt 1.
phat(l1,1). phat(l2,1).
tong_thieu_khoa(S) :- S = #sum { W : phat(L,W) }.
tong_du_khoa(S) :- S = #sum { W,L : phat(L,W) }.
#show chon/1.
#show tong_thieu_khoa/1.
#show tong_du_khoa/1.

Chạy python -m clingo asp_uu_tien_va_tuple.lp 0. Tìm mô hình cuối đạt tối ưu và đọc vector chi phí. Lịch A được chọn với vector 0 4. Trong cùng mô hình, tong_thieu_khoa(1) và tong_du_khoa(2) minh họa hiệu ứng khóa định danh. Hai tổng minh họa được hiển thị để kiểm tra và không tham gia hàm mục tiêu của ví dụ.

Khi dùng ràng buộc mềm, các phần tử mục tiêu được xác định bằng trọng số, cấp và các thành phần định danh. Nếu hai nhóm quy tắc ở cùng cấp có thể sinh cùng khóa, thêm mã loại phạt để phân biệt chúng. Cách kiểm tra dễ nhất là xây một lịch nhỏ đồng thời vi phạm cả hai và đối chiếu điểm bằng tay.

4. Kiểm chứng điểm trước khi tối ưu trên quy mô lớn

1. Tạo lịch không vi phạm, lịch vi phạm một lần và lịch vi phạm hai lần cùng trọng số.
2. Tạo hai lịch có cùng điểm cấp cao nhưng khác điểm cấp thấp, rồi thử trường hợp đảo thứ tự ưu tiên.
3. Đối chiếu vector do bộ giải trả về với bộ chấm độc lập, giữ mã loại phạt và khóa từng khoản trong báo cáo.

Một câu hỏi nghiên cứu là cách chọn cấp ưu tiên ảnh hưởng tới độ ổn định của lịch khi điều kiện đầu vào thay đổi. Hãy giữ dữ liệu cố định khi so với tổng trọng số, rồi đổi từng nhóm dữ liệu trong thí nghiệm riêng. Đọc thêm về cú pháp ràng buộc mềm và tổng tại tài liệu ngôn ngữ Clingo.