Steiner Tree Solution with GLPK

I am new to using GPLK and I am trying to solve Steiner Tree problem through it. The mathematical formulation I use is this: formula

This is the part of the code I'm testing:

# Number of terminal vertexes
param p, integer;

# Number of steiner vertexes
param s, integer;

# Terminal vertexes set
set P := 1..p;

# Steiner vertexes set
set S := (p+1)..(p+s);

# Vertexes set
set V := P union S;

# Edges set
set E, within V cross V;

# Edges cost
param c{(i,j) in E} default 0;

# Variable y
var y{(i,j) in E}, binary;

# Variable x
var x{(i,j) in E} >= 0;

# x constraint
s.t. Xconstraint{(i,j) in E}: x[i,j] <= (p) * y[i,j];

# Steiner vertexes constraints
s.t. Sconstraint{i in S}: sum{(i,j) in E} x[i,j] - sum{(k,i) in E} x[k,i] = 0;

# Terminal vertexes constraints
s.t. Pconstraint{i in P}: sum{(i,j) in E} x[i,j] - sum{(k,i) in E} x[k,i] = -1;

# Minimize vertexes cost
minimize cost: sum{(i,j) in E} c[i,j]*y[i,j];

solve;

printf "The tree cost is:\n",
   sum{(i,j) in E} c[i,j] * y[i,j];
printf "\n";

data;

param p := 10;
param s := 8;

param : E : c :=
    1 16 1340771
    2 18 2783118
    2 14 1534253
    2 17 71057
    3 12 1439171
    3 15 1921785
    4 11 3793393
    4 13 573690
    5 18 1268333
    6 17 2907508
    7 11 1981430
    8 11 1205285
    8 12 3190105
    9 12 393839
    10 16 461534
    10 18 1072719
    11 4 3793393
    11 7 1981430
    11 8 1205285
    12 3 1439171
    13 4 573690
    12 8 3190105
    12 9 393839
    13 14 776147
    13 17 2239343
    14 2 1534253
    14 13 776147
    14 15 2613116
    15 3 1921785
    15 14 2613116
    15 16 170002
    16 1 1340771
    16 10 461534
    16 15 170002
    17 2 71057
    17 6 2907508
    17 13 2239343
    18 2 2783118
    18 5 1268333
    18 10 1072719
;

end;

      

I tested this example using this site: http://www3.nd.edu/~jeff/mathprog/mathprog.html and it displays this message: "PROBLEM DOES NOT NEED A FREE SOLUTION". I think this example is bad, or the constraints are not correct, can anyone help me?

+3


source to share


1 answer


You need to change this limitation:

# Terminal vertexes constraints
s.t. Pconstraint{i in P: i != 1}: sum{(i,j) in E} x[i,j] - sum{(k,i) in E} x[k,i] = -1;

      



This is because the first node is in the stream from this stream based composition.

+2


source







All Articles