Библиотека расписаний/расписаний

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

Я рассмотрел несколько решателей ограничений (Sat4j, clasp, Glucose, GlueMiniSat и т. д.), но из того, что я видел, кажется, что все они имеют дело только с фиксированными ограничениями, и настройка предпочтений будет нетривиальной.

Меня не слишком волнует, на какой технологии/языке он написан — я с удовольствием напишу вокруг него обертку.


constraint-programming
person ajnatural    schedule 12.11.2015    source источник
comment
Не по теме в текущей форме, но может быть переформулирован как решение проблемы с гибкими ограничениями. Для последней цели в настоящее время это слишком расплывчато. Я понятия не имею, что означает кодировать атрибуты в предпочтения, т.е. что такое переменные и функция оптимизации.   -  person ivan_pozdeev    schedule 16.11.2015
comment
Если это проблема удовлетворения ограничений, то ее можно решить с помощью решатель SMT, например Z3.   -  person Anderson Green    schedule 03.02.2019

Ответы (4)


arrow_upward
1
arrow_downward

Безусловно, Choco Solver — это мощный решатель ограничений Java, который часто используется для планирования и планирования.

Возьмем следующий пример: «было бы неплохо, если бы х = 10»

Вы можете кодировать предпочтения по-разному.

1) через переменные и ограничения.

1.1) повторите ограничение с помощью двоичных переменных

ICF.arithm(x,"=",10).reifyWith(b);

в основном это означает, что b = 1 ‹=> x = 10 (поэтому ограничение может быть выполнено или не выполнено), тогда вы можете максимизировать b (возможно, с весом)

1.2) через гэп-переменные

solver.post(ICF.arithm(x,'-',gap,"=",10);

тогда вы можете минимизировать абсолютное значение зазора (возможно, с весом) до ограничения.

2) через поиск: при решении задачи попросите стратегию поиска попробовать x=10, прежде чем пробовать другое значение. Доказательства оптимальности нет, но на практике это работает достаточно хорошо.

Надеюсь, это поможет. Пожалуйста, не стесняйтесь обращаться к нам для получения дополнительной поддержки по Choco Solver www.cosling.com

Лучший,

person Jean-Guillaume Fages    schedule 13.01.2016

arrow_upward
0
arrow_downward

Я думаю, что OptaPlanner — это инструмент, который может помочь вам решить эту проблему, проверьте это:

OptaPlanner — это решение для удовлетворения ограничений. Это оптимизирует планирование бизнес-ресурсов. Каждая организация сталкивается с задачами планирования: назначьте ограниченный набор ограниченных ресурсов (сотрудников, активов, времени и денег) для предоставления продуктов или услуг клиентам. OptaPlanner оптимизирует такие проблемы планирования, чтобы делать больше бизнеса с меньшими ресурсами. Сценарии использования включают маршрутизацию транспортных средств, составление реестра сотрудников, планирование работы, упаковку контейнеров и многое другое.

OptaPlanner — это легкий встраиваемый механизм планирования. Это позволяет обычным программистам Java™ эффективно решать задачи оптимизации. Ограничения применяются к простым объектам предметной области и могут повторно использовать существующий код. Нет необходимости вводить сложные математические уравнения. Под капотом OptaPlanner сочетаются сложные эвристики оптимизации и метаэвристики (такие как поиск запретов, имитация отжига и позднее принятие) с очень эффективным расчетом баллов.

OptaPlanner — это программное обеспечение с открытым исходным кодом, выпущенное под лицензией Apache Software License. Он написан на 100% чистой Java™, работает на любой JVM и также доступен в репозитории Maven Central.

Источник:

http://www.optaplanner.org/

Это часть Drools, в которой есть и другие интересные инструменты:

http://www.drools.org/

person Alberto Anderick Jr    schedule 21.11.2015

arrow_upward
0
arrow_downward

Еще одна активно поддерживаемая библиотека — «choco-solver».

person Vyacheslav Enis    schedule 22.11.2015

arrow_upward
0
arrow_downward

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

person Arton Dorneles    schedule 20.02.2016