Это проблема линейного программирования?
Я потянул волосы за одну проблему... Общая проблема сложная... но позвольте мне сделать все возможное, чтобы объяснить ту часть, которая действительно имеет значение...
У меня есть график, где каждое ребро представляет корреляцию между двумя соединенными узлами. Каждый узел представляет собой временной ход (TC) (то есть 400 временных точек), где события будут происходить в различные временные точки. Корреляция между двумя узлами определяется как процент перекрывающихся событий. Для простоты этого примера предположим, что общее количество событий, происходящих на каждом узле, равно $tn$. И если два TC (узла) имеют перекрывающиеся события $on$ (то есть события, которые произошли в один и тот же момент времени). Тогда корреляция может быть определена просто как $on$/$tn$.
Теперь у меня есть сеть из 11 узлов; и я знаю корреляцию между каждыми двумя узлами. Как мне сгенерировать TC для всех 11 узлов, которые соответствуют ограничениям корреляции???
Это легко сделать для двух узлов, когда вы знаете корреляцию между ними. Предположим, что TC_1 и TC_2 имеют значение корреляции 0,6, что означает, что в двух TC имеются события с перекрытием на 60 процентов. Также предположим, что общее количество событий для TC_1 и TC_2 одинаково с $tn$. Простой алгоритм для размещения событий в двух TC: сначала случайным образом выбрать 0,6*$tn$ временных точек и рассматривать их как временные интервалы, в которых в обоих TC произошли перекрывающиеся события. Затем случайным образом выберите (1-0,6)*$tn$ временных точек в TC_1, чтобы разместить остальные события для TC_1. Наконец, случайным образом выберите (1-0,6)*$tn$ временных точек в TC_2, где в соответствующие временные точки в TC_1 не произошло никаких событий.
Однако становится все труднее, когда вы рассматриваете сеть с 3 узлами, где сгенерированные три TC должны соответствовать всем трем ограничениям корреляции (т. Е. 3 ребрам)... Это вряд ли возможно сделать для сети с 11 узлами...
Это имеет какой-то смысл для вас? Пожалуйста, дайте мне знать, если это не...
Я думал, что это всего лишь проблема компьютерного программирования, но чем больше я об этом думаю, тем больше это похоже на проблему линейного программирования, не так ли?
У кого-нибудь есть разумное решение? Я делаю это в R, но любой код в порядке...
3 ответа
Я думаю, что есть простой подход линейного программирования. Представлять решение в виде матрицы, где каждый столбец является узлом, а каждая строка - событием. Ячейки либо 0, либо 1, чтобы сказать, что событие связано или не связано с данным узлом. Тогда ваше ограничение корреляции - это ограничение, фиксирующее число 11 в паре столбцов относительно количества 1 в каждом из этих столбцов, которое вы фактически исправили заранее.
Учитывая эту структуру, если вы обрабатываете каждую возможную строку как отдельный элемент, встречающийся X_i раз, то у вас будут ограничения вида SUM_i X_i * P_ij = K_j, где P_ij равен 0 или единице, в зависимости от того, имеет ли возможная строка i 11 в пара столбцов, отсчитываемых j. Конечно, это большое бедствие для большого количества узлов, но с 11 узлами имеется 2048 возможных рядов, что не является полностью неуправляемым. X_i может быть не линейным, но я думаю, что они должны быть рациональными, поэтому, если вы готовы использовать поразительное количество строк / событий, у вас должно быть все в порядке.
К сожалению, вам также, возможно, придется попробовать различное общее количество столбцов, потому что существуют неравенства. Если имеется N строк и в двух столбцах есть m и n 1s, то в этой паре столбцов должно быть не менее m + n - N 11s. Фактически, вы можете сделать так, чтобы общее число 1 в каждом столбце выступало в качестве переменной решения - это дало бы вам новый набор ограничений, в которых Q_ij равен 0, и один в зависимости от того, имеет ли строка столбца i значение 1 в столбце к.
Там может быть лучший ответ скрывается там. В частности, легко генерировать нормально распределенные случайные величины для определенных корреляций (когда это возможно) - http://en.wikipedia.org/wiki/Cholesky_decomposition и (согласно Google R mvrnorm). Рассмотрим матрицу с 2^N строками и 2^N-1 столбцами, заполненными записями, которые имеют +/-1. Пометьте строки всеми комбинациями из N битов, а столбцы - всеми ненулевыми столбцами из N битов. Заполните каждую ячейку -1^(четность метки строки И метки столбца). Каждый столбец имеет одинаковые номера +1 и -1 записей. Если вы объединяете два столбца вместе элемент за элементом, вы получаете другой столбец, который имеет одинаковое количество записей +1 и -1 - поэтому они взаимно не связаны. Если ваша декомпозиция Холецкого предоставляет вам матрицы, элементы которых находятся в диапазоне [-1, 1], вы можете использовать его для объединения столбцов, где вы объединяете их, выбирая случайным образом из столбцов или из отрицательных столбцов в соответствии с конкретная вероятность.
Это также предполагает, что вы, возможно, могли бы обойтись в исходном подходе линейного программирования, например, с 15 столбцами, выбрав не из 2^15 различных строк, которые являются всеми возможными, но из 16 различных строк, которые имеют тот же шаблон, что и матрица с 2^4 строками и 2^4-1 столбцами, как описано выше.
Если существует решение (у вас может быть проблема без решения), вы можете представить ее как систему линейных уравнений.
x1/x2 = b =>
x1 - b*x2 = 0
or just
a*x1 + b*x2 = 0
Вы должны быть в состоянии преобразовать это в решение системы линейных уравнений или, точнее, однородной системы линейных уравнений, поскольку b в Ax=b равно 0.
Проблема в том, что, поскольку у вас есть n узлов и n*(n-1)/2 отношений (уравнений), у вас будет много отношений, и решения не будет.
Вы можете представить эту проблему как
Минимизируйте Ax, где x > 0 и xx == konstant
Вы можете представить это как смешанную целочисленную программу.
Предположим, у нас есть N узлы, и что каждый узел имеет T общее время Вы хотите найти назначение событий этим временным интервалам. Каждый узел имеет tn <= T События. Есть M Всего ребер в вашем графике. Между любой парой узлов i а также j что разделяет ребро, у вас есть коэффициент
c_ij = overlap_ij/tn
где overlap_ij количество перекрывающихся событий.
Позволять x[i,t] быть двоичной переменной, определенной как
x[i,t] = { 1 if an event occurs at time t in node i
= { 0 otherwise.
Тогда ограничение, которое tn события происходят в узле i можно записать как:
sum_{t=1}^T x[i,t] == tn
Позволять e[i,j,t] быть двоичной переменной, определенной как
e[i,j,t] = { 1 if node i and node j share an event a time t
= { 0 otherwise
Позволять N(i) обозначить соседей узла i, Тогда у нас есть это в каждый раз t
sum_{j in N(i)} e[i,j,t] <= x[i,t]
Это говорит о том, что если общее событие происходит в соседнем узле i вовремя t затем узел i должно быть событие во время t, Кроме того, если узел i имеет двух соседей u а также v мы не можем иметь e[i,u,t] + e[i,v,t] > 1 (это означает, что два события будут использовать один и тот же временной интервал), потому что сумма по всем соседям меньше x[i,t] <= 1,
Мы также знаем, что должно быть overlap_ij = tn*c_ij перекрывающиеся события между узлами i и узел j, Это означает, что у нас есть
sum_{t=1}^T e[i,j,t] == overlap_ij
Собрав все это вместе, вы получите следующий MIP
minimize 0
e, x
subject to sum_{t=1}^T x[i,t] == tn, for all nodes i=1,...,N
sum_{j in N(i)} e[i,j,t] <= x[i,t],
for all nodes i=1,...,N and all time t=1,...,T
sum_{t=1}^T e[i,j,t] == overlap_ij for all edges (i,j)
between nodes
x[i,t] binary for i=1,...,N and t=1,...,T
e[i,j,t] binary for all edges (i,j) and t=1,...,T
Здесь цель равна нулю, так как ваша модель - это просто проблема осуществимости. Эта модель имеет в общей сложности T*N + M*T переменные и N + N*T + M ограничения.
Решатель MIP, такой как Gurobi, может решить вышеуказанную проблему или доказать, что она неосуществима (т. Е. Решение не существует). Gurobi имеет интерфейс к R.
Вы можете извлечь окончательный временной ряд событий для i й узел, глядя на вектор решения x[i,1], x[i,2], ..., x[i,T],