2
$\begingroup$

Instance: a directed graph $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$.
Solution: A directed tree with root $v$.
Objective: Minimize total weight.

My formulation:

Formulation

My AMPL code:

param n >= 1, integer;  # number of vertices

set V := 0..n-1;
set E within {V,V};
param r := 0;

param w{E};  # edge weights

#Variável que determina se a aresta pertence a árvore
var x{V,V} binary;

#Variável que determina se existe um caminho de v pra r
var y{V} binary;


minimize maed :
  sum{(u,v) in E} x[u,v] * w[u,v];

subject to UreachR {(u,v) in E} : y[u] >= x[u,v];
subject to VreachR {(u,v) in E} : y[v] >= x[u,v];
subject to rest3 {u in V : u != r} : y[u] = sum{v in V} x[v,u];

The formulation and corresponding code above is returning A subgraph of G with cycles... I want a restriction that can eliminate them (make a tree).

Improve this question
$\endgroup$
1
  • $\begingroup$ Hint: Google "minimum spanning tree in directed graph", you'll come to the Chiu-Liu/Edmonds algorithm. Now think about how you could reduce the weight further by getting rid of some vertices; is it safe to do so greedily? $\endgroup$
    – j_random_hacker
    Commented Dec 4, 2016 at 12:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.