Biên Pareto và giới hạn của tổng trọng số trong lập lịch

1. Một lịch tốt có nhất thiết là lịch thắng theo một bộ trọng số?

Phòng đào tạo cân nhắc hai mục tiêu: X là số thay đổi so với lịch tham chiếu, Y là số buổi muộn. Cả hai đều cần giảm. Nếu chọn sẵn một tổng có trọng số, bộ giải trả phương án tốt nhất theo đúng tổng đó. Nhưng người duyệt lịch có thể muốn xem các đánh đổi trước khi chốt trọng số. Một lịch không thắng với các bộ trọng số đã thử chưa chắc là lịch kém về mọi mặt.

Bài này dùng bốn phương án giả định đã được coi là khả thi: A có cặp chi phí (0,6), B là (2,5), C là (4,0), D là (3,6). Chương trình ASP chỉ chọn một trong bốn phương án và xuất cặp chi phí. Bảng không phải kết quả thực nghiệm trên một trường đại học. Nó được thiết kế để kiểm tra chính xác sự khác nhau giữa quan hệ trội, tổng trọng số, tối ưu từ điển và cách đặt ngưỡng một mục tiêu.

2. Định nghĩa quan hệ trội trên cùng tập khả thi

Với hai lịch p và q, p trội q khi p không kém ở mọi mục tiêu và tốt hơn ít nhất một mục tiêu. Trong bài tối thiểu hai thành phần, điều đó có nghĩa Xp ≤ Xq, Yp ≤ Yq và có ít nhất một bất đẳng thức nghiêm. Lịch không bị bất kỳ lịch khả thi nào trội thuộc biên Pareto. Việc so sánh chỉ có nghĩa khi hai lịch dùng cùng định nghĩa mục tiêu, đơn vị và tập ràng buộc cứng.

A và B không trội nhau: A ít thay đổi hơn, B ít buổi muộn hơn. B và C cũng đánh đổi hai thành phần. D bị A trội vì A có ít thay đổi hơn và cùng số buổi muộn; D còn bị B trội ở cả hai thành phần. Vì vậy biên gồm A, B và C. Trong bài có nhiều lịch cùng vector chi phí, cần phân biệt số điểm Pareto với số lịch thuộc các điểm đó.

3. Vì sao tổng trọng số dương bỏ lỡ B?

Xét hàm w1 × X + w2 × Y với w1 và w2 đều dương. Muốn B có điểm không lớn hơn A, cần 2w1 + 5w2 ≤ 6w2, tức w1/w2 ≤ 1/2. Muốn B đồng thời không kém C, cần 2w1 + 5w2 ≤ 4w1, tức w1/w2 ≥ 5/2. Hai yêu cầu không thể cùng đúng. Do đó không có cặp trọng số dương nào làm B trở thành nghiệm tối ưu của tổng trên tập bốn phương án.

B vẫn không bị trội. Phản ví dụ cho thấy quét rất nhiều trọng số dương chưa bảo đảm tìm đủ mọi điểm Pareto của một tập phương án rời rạc. Tăng số lần thử có thể giúp khám phá thêm lịch, nhưng không khắc phục được giới hạn cấu trúc này. Cũng không nên kết luận mọi tổng trọng số đều vô ích: nếu chính sách đã chốt một tỷ lệ đánh đổi, tối ưu đúng tỷ lệ đó vẫn là một mục tiêu rõ ràng.

4. Đặt ngưỡng cho Y rồi tối ưu X

Một cách khác là quy định Y ≤ ε và tối thiểu X trên tập còn lại. Với ε = 5, A và D bị loại vì có sáu buổi muộn. C vẫn khả thi nhưng X = 4, trong khi B có X = 2. Bộ giải chọn B. Với ε = 0 chỉ C còn lại; với ε = 6, A có X nhỏ nhất. Ba ngưỡng này đủ lấy ba điểm biên của bảng ví dụ.

Đối với dữ liệu lớn, muốn gọi kết quả là biên đầy đủ phải mô tả cách duyệt ngưỡng, các giá trị chi phí có thể có và trạng thái chứng minh ở mỗi lượt. Nếu một lượt chỉ tìm được nghiệm tạm rồi hết thời gian, tập điểm thu được là tập phương án đang biết. Một điểm có vẻ không bị trội trong tập đó vẫn có thể bị một nghiệm chưa tìm thấy trội. Khi hai phương án cùng X dưới ngưỡng, cần xét tiếp Y nếu muốn loại các điểm yếu do hòa ở mục tiêu đang tối ưu.

5. Liệt kê tập nhỏ, lọc quan hệ trội, chạy một ngưỡng

Cài python -m pip install "clingo==5.8.3", sau đó chạy python asp_bien_pareto.py. Lượt đầu liệt kê đủ bốn ứng viên, sao chép ba giá trị L, X, Y trong callback rồi lọc cặp trội bằng Python. Chương trình kiểm tra rằng tập biên đúng bằng ba phần tử đã dự đoán. Nó còn kiểm tra hai cận tỷ lệ trọng số bằng phân số chính xác để không đưa sai số dấu phẩy động vào lập luận.

"""Biên Pareto chính xác trên tập ứng viên nhỏ, không dùng thêm thư viện."""
from fractions import Fraction
import clingo

PROGRAM = r"""
cost(a,0,6). cost(b,2,5). cost(c,4,0). cost(d,3,6).
1 { choose(L) : cost(L,X,Y) } 1.
point(L,X,Y) :- choose(L), cost(L,X,Y).
#show point/3.
"""

def solve(extra="", optimize=False):
    args = ["0", "--opt-mode=optN"] if optimize else ["0"]
    ctl = clingo.Control(args)
    ctl.add("base", [], PROGRAM + extra)
    ctl.ground([("base", [])])
    found = set()
    def collect(model):
        if optimize and not model.optimality_proven:
            return  # Chỉ lấy giai đoạn liệt kê nghiệm đã chứng nhận tối ưu.
        for atom in model.symbols(shown=True):
            l, x, y = atom.arguments
            found.add((str(l), x.number, y.number))
    result = ctl.solve(on_model=collect)
    assert result.exhausted and not result.interrupted
    return found

points = solve()
def dominates(p, q):
    return p[1] <= q[1] and p[2] <= q[2] and (p[1] < q[1] or p[2] < q[2])
front = {p for p in points if not any(dominates(q, p) for q in points)}
assert front == {("a", 0, 6), ("b", 2, 5), ("c", 4, 0)}
# Để B thắng A cần w1/w2 <= 1/2; để B thắng C cần >= 5/2.
assert Fraction(5, 2) > Fraction(1, 2)  # Không có tỉ lệ dương thỏa cả hai.
bounded = solve(":- point(L,X,Y), Y > 5.\n#minimize { X,L : point(L,X,Y) }.", True)
assert bounded == {("b", 2, 5)}
print("Biên Pareto:", sorted(front))
print("Giới hạn mục tiêu Y <= 5, tối ưu X:", sorted(bounded))

Lượt có tối ưu dùng --opt-mode=optN. Chương trình chỉ lấy mô hình được đánh dấu optimality_proven, tránh trộn các ứng viên đang được cải thiện với giai đoạn liệt kê tối ưu. Sau khi giải xong, nó kiểm tra trạng thái đã xét hết phạm vi cần giải và xác nhận nghiệm dưới ngưỡng Y ≤ 5 là B. Mô hình được sao chép trong callback; không giữ đối tượng Model để dùng khi lần gọi giải đã kết thúc.

6. Biên Pareto khác thứ tự ưu tiên tuyệt đối

Nếu chính sách nói giảm X trước rồi mới xét Y, tối ưu từ điển chọn A vì không có phương án nào có ít hơn 0 thay đổi. Nếu ưu tiên Y trước, nó chọn C. Cả hai đều là lựa chọn theo chính sách, nhưng không trả lời câu hỏi người dùng còn những đánh đổi nào. Chọn biên để trình bày và chọn một lịch cuối cùng là hai bước có thể tách ra trong quy trình điều phối.

Biên cũng không có nghĩa mọi điểm đáng trình bày ngang nhau. Người dùng có thể đặt giới hạn số buổi muộn, mức xáo trộn chấp nhận được hoặc tiêu chí công bằng theo giảng viên. Các giới hạn đó cần được công bố trước khi lọc. Nếu bổ sung một mục tiêu thứ ba, một điểm từng bị trội trên hai mục tiêu có thể trở thành không bị trội trong không gian ba mục tiêu. Tập mục tiêu là một phần của đặc tả, không chỉ là cột thêm vào báo cáo.

7. Từ ví dụ bốn điểm tới thực nghiệm lập lịch

Vét cạn mọi lịch phù hợp với mô hình nhỏ, nhưng số lịch có thể tăng rất nhanh. Với một bộ dữ liệu lớn, nên báo thời gian đến điểm không bị trội đầu tiên, số vector khác nhau đang biết, khoảng ngưỡng đã giải xong và chi phí tính toán. Khi so hai phương pháp, dùng cùng ngân sách, bộ kiểm chứng và các phép chuẩn hóa chi phí. Một phương pháp in nhiều answer set có thể chỉ lặp cùng vài vector mục tiêu.

Bài tập: thêm E = (1,5) rồi tính lại biên trước khi chạy. Kiểm tra B có còn không bị trội hay không. Tiếp theo thêm F có cùng vector với A nhưng khác phòng; so số điểm và số lịch. Cuối cùng, thay Y bằng tổng số phút muộn thay vì số buổi muộn, giải thích tại sao không được dùng lại nguyên các trọng số cũ mà không xác định chính sách đổi đơn vị.

Nguồn về mục tiêu nhiều cấp và cách đọc mô hình: Potassco Guide dòng 5: optimization; Clingo 5.8 Python API: Model và trạng thái giải. Phần lập luận Pareto và dữ liệu bốn điểm trong bài là ví dụ tự xây dựng. Đọc cùng Trọng số phạt hay thứ tự ưu tiên?.