Какой алгоритм (ы) может решить эту проблему программирования ограничений?

Question

Мне нужно решить проблему с влиянием на работу, и я хотел бы найти, предпочтительно, эффективные алгоритмы для решения этой проблемы.

Допустим, есть некоторые работники, которые могут выполнять несколько видов задач. У нас также есть пул задач, которые должны выполняться каждую неделю. Каждая задача занимает некоторое время. Каждое задание должно быть принято кем-то. Каждый работник должен работать от N до P часов в неделю.

Эта первая часть проблемы кажется хорошим кандидатом на алгоритм программирования ограничений.

Но вот сложность: поскольку работник может выполнять разные задачи, у него также могут быть предпочтения (или желания). Если кто-то хочет удовлетворить все пожелания для всех, решение проблемы не существует (слишком много ограничений).

Так что мне нужен алгоритм для решения этой проблемы. Я не хочу изобретать велосипед, если идеальное колесо уже существует.

Алгоритм должен быть справедливым (если можно определить это слово), поэтому, например, я должен иметь возможность добавить ограничение типа «попытаться удовлетворить хотя бы одно желание на людей». Я не уверен, что эту проблему можно решить с помощью описанных здесь методов Иерархии ограничений: Иерархии ограничений . На самом деле я не уверен, что «справедливость» и пожелания могут быть выражены действительными ограничениями для этой категории алгоритмов.

Есть ли эксперт по программированию с ограничениями, чтобы дать мне несколько советов? Нужно ли разрабатывать новое колесо с некоторой эвристикой вместо использования эффективных алгоритмов CP?

Спасибо!

Answer 1

Ваша проблема достаточно сложна, поэтому для общего решения, вероятно, потребуется сформулировать ее как linear-integer . Если, с другой стороны, вы можете ослабить определенные требования, вы можете использовать более простой подход. Например, двустороннее сопоставление позволит вам запланировать несколько рабочих на несколько заданий, и даже может обрабатывать предпочтения, но не сможет навязывать общие ограничения «справедливости». Смотрите, например этот связанный с ним вопрос . Раскраска вершин имеет эффективные алгоритмы для применения ограничений разделения работ.

Другие авторы упоминали симплекс и график работы магазина . Simplex - это алгоритм оптимизации - он пересекает пространство решений, стремясь максимизировать некоторую целевую функцию. Формулировка целевой функции, безусловно, может быть выполнена, но нетривиальна. Классическое планирование работы, например, двухстороннее соответствие, может моделировать некоторые аспекты вашей проблемы, но не все. Например, нет ограничений на приоритет. Существуют расширенные версии, которые могут обрабатывать некоторые ограничения, например, устанавливать временные ограничения для задач.

Если вас интересуют существующие реализации, библиотека Python networkx имеет реализацию этого алгоритма сопоставления . Пример программы с открытым исходным кодом, которая может представлять интерес: Tablix .

Answer 2

Я согласен с тем, что было предложено здесь. Тем не менее, MIP (проблемы смешанного целочисленного программирования) очень большого размера (далеко за 30 переменных!) В настоящее время практически решаются благодаря коммерческим кодам (Xpress, Cplex, Gurobi) или с открытым исходным кодом (Coin-Or / Cbc). Кроме того, модные языки моделирования, такие как OPL Studio, GAMS, AMPL, Flop ..., позволяют легко писать математические модели вместо использования API.

Вы можете воспользоваться сервером NEOS (http://neos.mcs.anl.gov/neos/solvers/index.html)), чтобы попробовать очень разные MIP-файлы. Вы отправляете свою модель в формате AMPL. Хотя AMPL поставляется как бесплатная ограниченная версия, NEOS может обрабатывать неограниченное количество экземпляров.

Языки моделирования также существуют для CP (COMET / OPL Studio) и локального поиска (COMET).

Не стесняйтесь связаться со мной через мой веб-сайт www.rostudel.com (страница «Контакты»)

David

Answer 3

Я сделал хронометраж, который можно рассматривать как форму программирования ограничений. У вас есть жесткие (нерушимые) ограничения и мягкие ограничения (например, настройки интервала).

Линейное целочисленное программирование обычно становится бесполезным после более чем 30 переменных, и это также можно сказать о симплексе.

Именно с помощью доменной оптимизации эвристических алгоритмов было найдено решение.

Использовались эвристические алгоритмы имитация отжига , генетические алгоритмы , метаэвристические алгоритмы и аналогичные, но в итоге лучший результат был обеспечен "интеллектуальным "домен настроен алгоритм жадного поиска .

В принципе, вы можете получить некоторые приличные результаты с помощью одной из эвристик, но главная проблема в том, что вы можете различить, когда проблема слишком ограничена.

Отличным инструментом для исследования с открытым исходным кодом является HeuristicLab .

Answer 4

Это звучит как планирование работы магазина .