Tối ưu hoá quy tắc ràng buộc hay lập trình quy tắc ràng buộc (CP), là cái tên được đặt để xác định các giải pháp khả thi trong số một nhóm đề xuất rất lớn, trong đó vấn đề có thể được mô hình hoá theo các quy tắc ràng buộc tuỳ ý. Các vấn đề về CP phát sinh trong nhiều lĩnh vực khoa học và kỹ thuật. (Từ "lập trình" là một cách hiểu nhầm, tương tự như "máy tính" từng có nghĩa là "một người tính toán". Ở đây, "lập trình" là sự sắp xếp một kế hoạch, thay vì lập trình bằng ngôn ngữ máy tính.)
CP dựa trên tính khả thi (tìm một giải pháp khả thi) thay vì tối ưu hoá (tìm một giải pháp tối ưu) và tập trung vào các quy tắc ràng buộc và biến thay vì hàm mục tiêu. Trên thực tế, bài toán CP có thể thậm chí không có hàm mục tiêu – mục tiêu có thể là thu hẹp một tập hợp rất lớn các giải pháp khả thi cho một tập hợp con dễ quản lý hơn bằng cách thêm các điều kiện ràng buộc vào bài toán đó.
Một ví dụ về một vấn đề phù hợp với CP là việc lập lịch biểu nhân viên.
Vấn đề phát sinh khi các công ty hoạt động liên tục (chẳng hạn như nhà máy) cần tạo lịch biểu hằng tuần cho nhân viên. Sau đây là một ví dụ rất đơn giản: một công ty điều hành 3 ca làm việc 8 giờ mỗi ngày và phân công 3 trong số 4 nhân viên của công ty làm ca làm việc khác nhau mỗi ngày, trong khi cho ngày nghỉ thứ 4. Ngay cả trong trường hợp nhỏ như vậy, số lượng lịch biểu có thể rất lớn: mỗi ngày có 4! = 4 * 3 * 2 * 1 = 24 lượt phân công nhân viên, vậy nên số lượng lịch biểu hằng tuần có thể là 247, tức là hơn 4, 5 tỷ.
Thông thường sẽ có những hạn chế khác làm giảm số lượng giải pháp khả thi, ví dụ: mỗi nhân viên làm việc ít nhất số ngày tối thiểu mỗi tuần. Phương thức CP theo dõi xem giải pháp nào vẫn khả thi khi bạn thêm các quy tắc ràng buộc mới. Điều này khiến phương thức này trở thành công cụ mạnh mẽ để giải quyết các vấn đề lớn về việc lập lịch trong thực tế.
CP có một cộng đồng rộng lớn và hoạt động rất tích cực trên khắp thế giới với những tạp chí khoa học, hội thảo chuyên sâu và kho vũ khí gồm nhiều kỹ thuật giải quyết khác nhau. CP đã được áp dụng thành công trong việc lập kế hoạch, lên lịch và nhiều miền khác có các quy tắc ràng buộc không đồng nhất.
Công cụ
Google đưa ra một số cách để giải quyết các vấn đề về CP:
- Trình giải CP-SAT: Một trình giải lập trình ràng buộc sử dụng các phương thức SAT (mức độ hài lòng).
- Trình giải CP gốc: Một trình giải lập trình quy tắc ràng buộc dùng trong thư viện định tuyến.
Nếu có thể mô hình hoá bài toán bằng mục tiêu tuyến tính và các điều kiện ràng buộc tuyến tính, thì bạn có vấn đề về lập trình tuyến tính và nên cân nhắc sử dụng MPSolver. (Tuy nhiên, các vấn đề về định tuyến thường được giải quyết tốt nhất bằng thư viện định tuyến xe của chúng tôi, ngay cả khi các vấn đề đó có thể được biểu thị bằng mô hình tuyến tính.)
Ví dụ
Phần tiếp theo mô tả về trình giải CP-SAT, trình phân giải OR-Tools chính để lập trình quy tắc ràng buộc. (SAT là viết tắt của satisfiability (Khả năng hài lòng): trình giải toán sử dụng các kỹ thuật để giải các bài toán SAT cùng với các phương thức CP.)
Dưới đây là một số ví dụ về các bài toán lên lịch rất phù hợp với trình giải CP-SAT:
Hai bài toán CP kinh điển là bài toán N-queens và câu đố số học.