• Tối ưu hoá số nguyên

Các bài toán tối ưu hoá tuyến tính yêu cầu một số biến phải là số nguyên được gọi là Chương trình số nguyên hỗn hợp (MIP).

Các biến này có thể phát sinh theo một số cách:

  • Biến số nguyên biểu thị số lượng mặt hàng, chẳng hạn như ô tô hoặc bộ TV, nhưng vấn đề là việc quyết định số lượng mặt hàng cần sản xuất để tối đa hoá lợi nhuận.
    Thông thường, những bài toán như vậy có thể được thiết lập dưới dạng bài toán tối ưu hoá tuyến tính tiêu chuẩn, kèm theo yêu cầu bổ sung là các biến phải là số nguyên. Phần tiếp theo cho thấy ví dụ về loại vấn đề này.

  • Biến Boolean biểu thị các quyết định có giá trị 0-1.
    Ví dụ: hãy cân nhắc một vấn đề liên quan đến việc chỉ định worker cho các nhiệm vụ (xem bài viết Chỉ định). Để thiết lập loại sự cố này, bạn có thể xác định các biến Boolean xi,j bằng 1 nếu worker i được gán cho tác vụ j và 0 nếu không.

Để có kiến thức cơ bản tốt về cách tối ưu hoá số nguyên, bạn nên tham khảo sổ tay lập mô hình Mosek.

Công cụ

Google cung cấp một số cách để giải quyết các vấn đề về MIP:

  • MPSolver: Một trình bao bọc cho một số trình phân giải MIP của bên thứ ba, sử dụng các kỹ thuật liên kết và nhánh tiêu chuẩn.
  • Trình giải CP-SAT: Trình giải lập trình hạn chế sử dụng các phương thức SAT (mức độ hài lòng).
  • Trình phân giải CP gốc: Trình giải quyết lập trình ràng buộc.

Tôi nên sử dụng trình giải toán nào?

Không có quy tắc ràng buộc nào khi quyết định sử dụng trình giải MIP hay trình giải CP-SAT. Đây là hướng dẫn sơ bộ:

  • Trình giải MIP phù hợp hơn cho các bài toán có thể được thiết lập dưới dạng LP tiêu chuẩn, nhưng với các biến số nguyên tuỳ ý, như ví dụ đầu tiên ở trên.
  • Trình phân giải CP-SAT phù hợp hơn cho các vấn đề trong đó hầu hết các biến đều là Boolean, như ví dụ thứ hai ở trên.

Đối với các MIP thông thường có cả biến số nguyên và biến Boolean, thường không có sự khác biệt rõ ràng về tốc độ giữa 2 trình phân giải. Vì vậy, bạn có thể lựa chọn theo sở thích cá nhân.

Để tham khảo ví dụ sử dụng cả bộ giải MIP và CP-SAT, hãy xem bài viết Giải quyết vấn đề về bài tập và các phần khác về bài tập.

Một cách khác để giải quyết các vấn đề về lập trình số nguyên là dùng trình giải luồng mạng.
Hãy xem bài viết Chỉ định dưới dạng vấn đề về luồng chi phí tối thiểu để tham khảo ví dụ.
Đối với một bài toán có thể được thiết lập dưới dạng luồng mạng, trình giải luồng chi phí tối thiểu có thể nhanh hơn trình giải MIP hoặc CP-SAT. Tuy nhiên, không phải MIP nào cũng có thể được thiết lập theo cách này.