当 LP 在 MathProg 中不可行时打印一些完全不同的东西

Question

我正在使用 MathProg（一种特定于 GLPK 库的语言，类似于 AMPL 的子集）来查找图形顶点的拓扑排序。这是我的线性规划 class 的作业。这是一个入门练习，以确保我们可以制定一个简单的线性程序并使用 GLPK 对其进行求解。

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

我设法以一种 hacky 的方式做到了（见下文）。 怎样做更优雅，不重复可行性条件？有没有一种方法可以检测不依赖于正在解决的问题的不可行性？

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。我在寻找类似于通用编程语言中的变量的东西。

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

当 LP 在 MathProg 中不可行时打印一些完全不同的东西

Print something completely different when the LP is infeasible in MathProg

feasibility

ampl

glpk

mathprog