0

我正在使用 MathProg（一种特定于 GLPK 库的语言，类似于 AMPL 的子集）来查找图顶点的拓扑排名。这是我的线性编程课的作业。这是一个介绍性练习，以确保我们可以制定一个简单的线性程序并使用 GLPK 解决它。

我编写了一个 Perl 脚本，它在 MathProg 中为给定的图形生成线性程序。它通过 打印变量的值（顶点等级）printf。如果可行，那正是我想要的；否则它会打印全零，但我只想打印Infeasible, has cycles or loops..

我设法以一种骇人听闻的方式做到了（见下文）。如何更优雅地做到这一点，而不重复可行性条件？有没有一种方法可以检测不依赖于正在解决的问题的不可行性？

param Vsize := 3;
set V "Vertices" := (0..Vsize-1);
set E "Edges" within V cross V := {(0, 1), (1, 2), (2, 0)};

var v{i in V} >= 0;
minimize rank_total: sum{i in V} v[i];
edge{(i, j) in E}: v[j] - v[i] >= 1;

solve;

printf "#OUTPUT:\n";
printf (if ((exists{i in V} v[i] >= 1) or card(E) = 0) then "" else "Infeasible, has cycles or loops.\n");
printf{i in V} (if ((exists{j in V} v[j] >= 1) or card(E) = 0) then "v_%d: %d\n" else ""), i, v[i];
printf "#OUTPUT END\n";

end;

我试图声明param Feasible binary := (exists{i in V} v[i] >= 1) or card(E) = 0;，但 GLPK 拒绝了它Model processing error。我之前声明的时候solve，它说operand preceding >= has invalid type，之后的时候，它说expression following := has invalid type。我正在寻找常见编程语言中的变量之类的东西。

4

1 回答 1

1

在 AMPL 中，您可以检查内置参数solve_result以查看问题是否不可行：

if solve_result = 'infeasible' then
  print 'Infeasible, has cycles or loops.';

但是，我不确定 GLPK 是否支持此参数，在这种情况下您可能需要手动检查可行性。

至于错误，因为exists是一个逻辑表达式，您不能将其用作数字表达式。解决方法是简单地将逻辑表达式放入if：

param Feasible binary :=
  if (exists{i in V} v[i].val >= 1) or card(E) = 0 then 1;
于 2015-03-28T14:01:01.683 回答