Максимальное количество назначенных переменных в удовлетворении ограничений

Question

Каковы некоторые известные алгоритмы (или ресурсы для поиска алгоритмов), чтобы найти назначение, которое максимизирует число назначенных переменных в задаче ограничения ограничений (в случае отсутствия удовлетворяющего присваивания)?

Answer 1

Для линейных уравнений линейная алгебра может быть использована для нахождения числа степеней свободы и, следовательно, числа присваиваемых независимых переменных.

Edit:

При внимательном мысли о вас проблемы, я думаю, что Simplex Algorithm может помочь вам. Это оптимизирующий алгоритм для нахождения наилучшего целочисленного решения для задачи линейной оптимизации.

Edit 2:

Пусть допустимая область будет подаваемые склады.

Пример:

Допустим, у вас есть 2 типа депо, X и Y.

X требует 5 масла и 7 стали должны предоставляться.

Y требуется 8 масляных и 2 стальных изделия.

Вы хотите максимизировать количество поставки депо:

функцию, чтобы максимизировать = X + Y

Условия:

X < = общее количество складов типа X Y < = общее число складов типа Y 5X + 8Y < общий объем подачи масла 7X + 2Y < всего стального электроснабжения

Применить алгоритм Simplex и вуаля!

Answer 2

Возможно, вы хотите максимизировать количество удовлетворенных ограничений вместо назначенных переменных? Я подумал о том, что вы могли бы получить от максимизации числа назначенных переменных (пока вы тривиально не увидите по крайней мере одно ограничение, нарушенное), и мне кажется, что вы хотите что-то по линии наибольшего подмножества ограничений, которые являются выполнимыми. В противном случае я, вероятно, не понимаю ваш критерий оптимизации.

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

Я буду использовать рамки взвешенной проблемы ограничения ограничений (WCSP) в следующем.

Учитывая, что вы представляете свои ограничения как таблицы разрешенных или запрещенных частичных назначений, вы можете преобразовать ограничение, просто присваив допустимым присваиваниям стоимость 0 и запрещенные затраты на присваивание 1. То есть всякий раз, когда ограничение переменной не допускается ограничением , он понесет расходы.Назначение, которое минимизирует затраты, следовательно, минимизирует количество ограничений, которые он нарушает, что эквивалентно максимизации количества удовлетворенных ограничений. Как только у вас есть такое задание, должно быть легко построить наибольшее подмножество удовлетворяющих ограничений, итерации по всем ограничениям и проверить, удовлетворяет ли им присваивание или нет. Хорошим решением для WCSP является toulbar2, который вычисляет такие наименьшие присвоения стоимости данному WCSP.

Построение WCSP из проблемы ограничения ограничений (CSP) прост, если вы представляете ограничения как таблицы. Весовые ограничения просто таблицы вида

X_1 X_2 … X_n c 

1 1 … 1 0 

1 2 … 1 0 

... 

2 2 … 3 1 

2 2 … 4 1 

Здесь мы имеем ограничение над п переменных x_1, ..., X_n, где переменные могут принимать значения из конечных областей {1,2} и {1,2,3, 4}. Предполагая, что вы отметили допустимый кортеж с «T» и недопустимым с «F», конвертируя суммы в замену «T» на стоимость 0 и «F» стоимостью 1.

Обратите внимание, что это не Формат WCSP. Формат подробно описан в пакете toulbar2, указанном выше.

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