Одной из наиболее известных задач комбинаторной оптимизации является задача о назначениях . Вот пример: предположим, что группе работников необходимо выполнить набор задач, и для каждого работника и задачи существует стоимость назначения работника для выполнения этой задачи. Проблема состоит в том, чтобы поручить каждому работнику не более одной задачи, при этом никакие два работника не будут выполнять одну и ту же задачу, при этом общая стоимость будет минимизирована.
Визуализировать эту проблему можно на графике ниже, на котором есть четыре работника и четыре задачи. Края представляют все возможные способы назначения работников на задачи. Метки по краям — это затраты на назначение работников на задачи.
Назначение соответствует подмножеству ребер, в котором каждый рабочий имеет не более одного исходящего ребра, и никакие два рабочих не имеют ребер, ведущих к одной и той же задаче. Ниже показано одно из возможных назначений.
Общая стоимость задания 70 + 55 + 95 + 45 = 265 .
В следующем разделе показано, как решить задачу о назначениях, используя как решатель MIP, так и решатель CP-SAT.
Другие инструменты для решения задач с заданиями
OR-Tools также предоставляет несколько других инструментов для решения задач о назначениях, которые могут быть быстрее, чем решатели MIP или CP:
Однако эти инструменты могут решать только простые типы задач назначения. Поэтому для общих решателей, которые могут решать широкий спектр задач (и достаточно быстры для большинства приложений), мы рекомендуем решатели MIP и CP-SAT.