用 GLPK 求解 Steiner 树

Question

我是 GPLK 的新手，我正试图通过它解决 Steiner Tree 问题。我使用的数学公式是这样的：

这是我正在测试的代码片段：

# 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;

我已经使用这个网站测试了这个例子： http://www3.nd.edu/~jeff/mathprog/mathprog.html 并显示此消息："PROBLEM HAS NO FEASIBLE SOLUTION"。我认为要么这个例子不好，要么约束有误，有人可以帮助我吗？

Answer 1

您需要更改此限制条件：

# 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;

那是因为第一个节点是这个基于流的公式的流出处。

用 GLPK 求解 Steiner 树

Solving Steiner Tree with GLPK

graph

ampl

glpk

mathprog