Блог

Я пытаюсь реализовать проблему с дуговым потоком, когда у меня есть набор дуг в массиве. Каждая дуга представляет собой пользовательскую структуру данных, состоящую из узлов from / to . Я хочу добавить ограничение, в котором я включаю только дуги, которые идут от определенного узла (1), что-то вроде:

 @constraint(m, sum(x[a] for a in arcs; a.from==1) == 1)
  

Это не работает. Каков наилучший подход для решения этой проблемы? Есть ли способ сделать это без предварительного вычисления всех исходящих дуг из каждого узла в первую очередь? Если да, есть ли способ добавить дополнительные условия?
Заранее спасибо

Бернардо

Я предполагаю, что синтаксис, который вы ищете, является

 @constraint(m, sum(x[a] for a in arcs if a.from==1) == 1)
  

Это следует из стандартного синтаксиса Julia для выражений генератора.

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

Вам нужно переопределить вашу x матрицу смежности, то есть квадратную матрицу, которая имеет 1 (или вес ребра), где есть дуга между парой узлов и 0 в противном случае.

Предполагая, что рассматриваемый вами набор вершин N (например N = 1:10 , для 10 вершин), ваше ограничение теперь может выглядеть следующим образом:

 @constraint(m, arcConstraint[n in N], sum(x[n,k] for k ∈ N) == 1 )
  

Обратите внимание, что arcConstraint это просто имя ограничения, чтобы вы могли ссылаться на него позже.

Также sum можно записать так, как sum(x[n,:]) если бы вы действительно знали, что просматриваете весь столбец (зависит от вашего точного сценария).