Return to Question

I want to find a mathematical formulation to use with the GLPK software package. Given a directed graph and a root, I need to find a tree that minimizes the value of the edges in that graph. Note that we DON'T need to include all vertices.

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.

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:

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).

In that example the root is A and the tree that minimizes the cost of edges is $A,C,E,D$ with cost $-4$. In other words I want to find a tree with minimum value, the number of nodes doesn't matter at all.

Any help with related problems? I can't find any material or papers...

Trying to code in AMPL:

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

set V := 0..n;
set E within {V,V};

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 root : y[0] = 1;  
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} : y[u] <= sum{v in V} x[u,v];
subject to rest4 {(u,v) in E} : y[u] >= x[u,v];

Now i don't know how to set a root. The code above is returning this:

Problem:    maed
Rows:       35
Columns:    42 (42 integer, 42 binary)
Non-zeros:  105
Status:     INTEGER OPTIMAL
Objective:  maed = -12 (MINimum)

No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
 1 maed                      -12                             
 2 root                        1             1             = 
 3 UreachR[0,2]                1            -0               
 4 UreachR[0,3]                1            -0               
 5 UreachR[1,0]                0            -0               
 6 UreachR[2,1]                1            -0               
 7 UreachR[2,4]                0            -0               
 8 UreachR[3,2]                1            -0               
 9 UreachR[3,4]                0            -0               
10 UreachR[4,3]                0            -0               
11 UreachR[4,1]                1            -0               
12 VreachR[0,2]                1            -0               
13 VreachR[0,3]                1            -0               
14 VreachR[1,0]                1            -0               
15 VreachR[2,1]                0            -0               
16 VreachR[2,4]                0            -0               
17 VreachR[3,2]                1            -0               
18 VreachR[3,4]                0            -0               
19 VreachR[4,3]                0            -0               
20 VreachR[4,1]                0            -0               
21 rest3[0]                    0                          -0 
22 rest3[1]                    0                          -0 
23 rest3[2]                    0                          -0 
24 rest3[3]                    0                          -0 
25 rest3[4]                    0                          -0 
26 rest3[5]                    0                          -0 
27 rest4[0,2]                  1            -0               
28 rest4[0,3]                  1            -0               
29 rest4[1,0]                  0            -0               
30 rest4[2,1]                  1            -0               
31 rest4[2,4]                  0            -0               
32 rest4[3,2]                  1            -0               
33 rest4[3,4]                  0            -0               
34 rest4[4,3]                  0            -0               
35 rest4[4,1]                  1            -0               

No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
 1 x[0,2]       *              0             0             1 
 2 x[0,3]       *              0             0             1 
 3 x[1,0]       *              0             0             1 
 4 x[2,1]       *              0             0             1 
 5 x[2,4]       *              1             0             1 
 6 x[3,2]       *              0             0             1 
 7 x[3,4]       *              1             0             1 
 8 x[4,3]       *              1             0             1 
 9 x[4,1]       *              0             0             1 
10 x[0,0]       *              1             0             1 
11 x[0,1]       *              0             0             1 
12 x[0,4]       *              0             0             1 
13 x[0,5]       *              0             0             1 
14 x[1,1]       *              0             0             1 
15 x[1,2]       *              0             0             1 
16 x[1,3]       *              0             0             1 
17 x[1,4]       *              0             0             1 
18 x[1,5]       *              0             0             1 
19 x[2,0]       *              0             0             1 
20 x[2,2]       *              0             0             1 
21 x[2,3]       *              0             0             1 
22 x[2,5]       *              0             0             1 
23 x[3,0]       *              0             0             1 
24 x[3,1]       *              0             0             1 
25 x[3,3]       *              0             0             1 
26 x[3,5]       *              0             0             1 
27 x[4,0]       *              0             0             1 
28 x[4,2]       *              0             0             1 
29 x[4,4]       *              0             0             1 
30 x[4,5]       *              0             0             1 
31 x[5,0]       *              0             0             1 
32 x[5,1]       *              0             0             1 
33 x[5,2]       *              0             0             1 
34 x[5,3]       *              0             0             1 
35 x[5,4]       *              0             0             1 
36 x[5,5]       *              0             0             1 
37 y[0]         *              1             0             1 
38 y[1]         *              0             0             1 
39 y[2]         *              1             0             1 
40 y[3]         *              1             0             1 
41 y[4]         *              1             0             1 
42 y[5]         *              0             0             1 

Integer feasibility conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
    max.rel.err = 0.00e+00 on row 0
    High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
    max.rel.err = 0.00e+00 on row 0
    High quality

Now i don't know how to set a root. The code above are returning this:

Now i don't know how to set a root. The code above is returning this: