Это проблема линейного программирования?

Question

Я потянул волосы за одну проблему ... Общая проблема сложная ... но позвольте мне сделать все возможное, чтобы объяснить ту часть, которая действительно имеет значение ...

У меня есть графикгде каждое ребро представляет корреляцию между соединенными двумя узлами.Каждый узел представляет собой временной ход (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, но любой код в порядке ...

Answer 1

Я думаю, что есть простой подход линейного программирования. Представьте решение в виде матрицы, где каждый столбец является узлом, а каждая строка - событием. Ячейки равны 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#Monte_Carlo_simulation и (согласно 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 столбцами, как описано выше.

Answer 2

Вы можете представить это как смешанную целочисленную программу.

Предположим, у нас есть 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].

Answer 3

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

 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 и x.x == konstant