0

私は MathProg (AMPL のサブセットに似た GLPK ライブラリに固有の言語) を使用して、グラフの頂点のトポロジカル ランキングを見つけています。これは、線形計画法クラスの課題です。簡単な線形プログラムを定式化し、GLPK を使用してそれを解決できることを確認するための入門演習です。

特定のグラフの MathProg で線形プログラムを生成する Perl スクリプトを作成しました。を介して変数の値 (頂点のランク) を出力し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 に答える