комбинаторика - Задача о назначениях с дополнительными условиями

Классическая задача о назначениях формулируется так:

Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.

Это задача линейного программирования и решается, например, венгерским алгоритмом.

А как можно решить эту задачу при наличии дополнительных усложнений вносящих нелинейность? Например:

1. Число работ меньше числа исполнителей. При этом Петя, Вася и Коля так привыкли работать в одной команде, что если вы возьмете на работу всех троих, то каждый согласится работать на 10% дешевле
2. Возможен и обратный вариант - Саша и Маша терпеть не могут друг друга и согласятся работать в одной компании только за двойную оплату.
3. Для каждой работы определено рабочее место и рабочие места расположены в ряд. Петя, Вася и Коля хотят не просто работать вместе, а сидеть за соседними столами, иначе скидка отменяется

Очевидно, что задача решается методом полного перебора. Есть ли другие варианты?