Целочисленная оптимизация (?) с произвольными ограничениями

[STR]

Пусть есть пространство 12D векторов. Каждая координата может принимать значение от 0 до 25. На пространстве задана целевая функция, которая каждому вектору ставит в соответствие целое число. Нужно найти некоторое количество векторов (скажем, по 20 штук), которые соответсвуют значению целевой функции 0, 1, 2, 3 ... и т.д. При этом, поиск нужно вести не во всем пространстве, а с учетом ограничений. Ограничения могут быть по типу: "у вектора не больше чем 3 одинаковых координаты", или "у вектора обязательно одна и только одна (но любая) из координат должна равняться 5" и т.д., в любых комбинациях.
Существуют ли какие-то более оптимальные методы, чем просто перебор всех вариантов в лоб? Я смотрел в сторону целочисленного программирования, но там все ограничения задаются равенствами/неравенствами. Не совсем понятно, как это применить к моему случаю. Кроме того, там ищется только минимум функции, а мне нужны решения для каждого значения функции. Буду благодарен за подсказку!

[dgwuqtj]

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

[STR]

dgwuqtj
Потенциально, в пределах от 0 до 40 000. Но нужны мне только маленькие, не больше 20. Только не совсем понял, какую роль играет величина значения функции? Перебирать-то придется в пространстве векторов, а оно огромное. Даже с учетом ограничений.

[dgwuqtj]

Случайный вектор сгенерировать легко, если ограничения не сильно замысловатые. Но чем большие значения может принимать функция, тем меньше вероятность, что вектор подходит (т.е. значение функции на нём маленькое).

[STR]

dgwuqtj
А, ну да, makes sense. Получается, что только перебором, других способов нет?

[Alex Krylov]

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

А так, если говорить "в общем", то можете для начала вот здесь
https://en.wikipedia.org/wiki/Integer_programming
обратить внимание на раздел "Using total unimodularity". С помощью этого аргумента доказывается разрешимость ряда задач комбинаторной оптимизации.

Вот это еще может относиться к делу: https://en.wikipedia.org/wiki/Farkas%27_lemma

Я не до конца понял, что так конкретно у вас, но если говорить о задачах целочисленного программирования "в общем", то в общем случае задачи целочисленного программирования относятся к классу NP-трудных задач. Даже решение одного единственного линейного уравнения относительно двоичных переменных в общем случае является NP-трудной задачей, т.к. по сути это вот это https://en.wikipedia.org/wiki/Subset_sum_problem.