J'essaie de mettre en œuvre un problème de flux d'arc où j'ai un ensemble d'arcs dans un tableau. Chaque arc est une structure de données personnalisée composée de nœuds from / to. Je veux ajouter une contrainte où je n'inclus que les arcs qui vont d'un nœud spécifique (1), quelque chose comme:

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

Cela ne fonctionne pas. Quelle est la meilleure approche pour y faire face? Existe-t-il un moyen de le faire sans précalculer tous les arcs sortants de chaque nœud au préalable? Si oui, existe-t-il un moyen d'ajouter des conditions supplémentaires? Merci d'avance

Bernardo…

2
Berni 20 oct. 2020 à 18:17

2 réponses

Meilleure réponse

Je suppose que la syntaxe que vous recherchez est

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

Cela découle de la syntaxe Julia standard pour les expressions génératrices.

Cependant, l'expression est tout aussi inefficace qu'elle le serait dans Julia simple car elle parcourt tous les arcs. Si cette boucle devient un goulot d'étranglement, vous devrez reformuler l'expression d'une autre manière, par exemple en précalculant les arcs sortants de chaque nœud.

1
mlubin 21 oct. 2020 à 01:49

Vous devez redéfinir votre x pour qu'elle devienne une matrice de contiguïté, c'est-à-dire un carré matrice qui a 1 (ou poids d'arête) où il y a un arc entre une paire de nœuds et 0 sinon.

En supposant que l'ensemble de sommets que vous considérez est N (par exemple N = 1:10 pour 10 sommets), votre contrainte peut maintenant ressembler à ceci:

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

Notez que arcConstraint est juste le nom de la contrainte afin que vous puissiez le référencer plus tard.

Le sum peut également être écrit comme sum(x[n,:]) si vous savez réellement que vous parcourez toute la colonne (cela dépend de votre scénario exact).

1
Przemyslaw Szufel 20 oct. 2020 à 15:56