2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Целочисленная оптимизация (?) с произвольными ограничениями
Сообщение17.04.2025, 18:33 
Если функция принимает только маленькие значения, то можно попробовать просто перебирать случайные векторы, подходящие по ограничениям.

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

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

 
 
 
 Re: Целочисленная оптимизация (?) с произвольными ограничениями
Сообщение17.04.2025, 18:44 
dgwuqtj
А, ну да, makes sense. Получается, что только перебором, других способов нет?

 
 
 
 Re: Целочисленная оптимизация (?) с произвольными ограничениями
Сообщение18.04.2025, 19:37 
Вы бы более подробно изложили свою задачу. Потому что от этой конкретики и нюансов может зависеть, разрешима ли она.

А так, если говорить "в общем", то можете для начала вот здесь
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.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group