Перебрать подмножество переменных в ограничении JuMP

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

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

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

Бернардо


constraints loops julia julia-jump network-flow
person Berni    schedule 20.10.2020    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

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

person mlubin    schedule 21.10.2020
comment
Да, это решило мою проблему. Я забыл упомянуть, что я не беспокоюсь о том, чтобы перебирать все дуги при построении ограничения. - person Berni; 21.10.2020

arrow_upward
1
arrow_downward

Вам необходимо переопределить ваш 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,:]), если вы действительно знаете, что просматриваете весь столбец (зависит от вашего точного сценария).

person Przemyslaw Szufel    schedule 20.10.2020
comment
Разве это не связано с созданием переменных NxN? В моем случае количество дуг в задаче значительно меньше, чем NxN, и я хочу избежать такого количества переменных (только по одной на каждую дугу). - person Berni; 20.10.2020
comment
У вас не может быть условных инструкций в модели JuMP (поскольку решатели не поддерживают это). Если ваша цель - выбрать дуги для графа размером N, естественно, у вас есть NxN переменных (или половина от этого числа для неориентированного графа). Если ваше N больше, чем зависит от некоторых конкретных характеристик вашей проблемы, вы можете попытаться реструктурировать его, но это математическое моделирование, а не проблема Джулии JuMP. - person Przemyslaw Szufel; 20.10.2020