Một trong những vấn đề phổ biến nhất về tối ưu hoá tổ hợp là bài toán chỉ định. Dưới đây là ví dụ: giả sử một nhóm trình thực thi cần thực hiện một nhóm tác vụ và đối với mỗi trình thực thi và tác vụ, sẽ có chi phí để chỉ định trình thực thi vào tác vụ. Vấn đề là chỉ định mỗi trình thực thi cho tối đa một tác vụ, trong đó không có hai trình thực thi nào thực hiện cùng một tác vụ, đồng thời giảm thiểu tổng chi phí.
Bạn có thể hình dung vấn đề này bằng biểu đồ bên dưới, trong đó có 4 worker và 4 tác vụ. Các cạnh thể hiện tất cả các cách có thể dùng để chỉ định trình thực thi cho các tác vụ. Nhãn ở các cạnh là chi phí giao nhân viên cho các nhiệm vụ.
Một bài tập tương ứng với một tập hợp con các cạnh, trong đó mỗi trình thực thi có ít nhất một cạnh hướng ra trước và không có hai trình thực thi nào có các cạnh dẫn đến cùng một tác vụ. Dưới đây là một bài tập khả thi.
Tổng chi phí của việc chỉ định này là 70 + 55 + 95 + 45 = 265.
Mục tiếp theo trình bày cách giải một bài tập về bài tập bằng cách sử dụng cả trình giải MIP lẫn trình giải CP-SAT.
Các công cụ khác để giải bài tập về bài tập
OR-Tools cũng cung cấp một số công cụ khác giúp giải bài tập về bài tập, có thể nhanh hơn trình giải quyết MIP hoặc CP:
Tuy nhiên, các công cụ này chỉ có thể giải quyết các loại bài tập đơn giản. Vì vậy, đối với những trình giải toán nói chung có thể xử lý nhiều vấn đề (và đủ nhanh cho hầu hết các ứng dụng), bạn nên sử dụng trình giải MIP và CP-SAT.