2

整数プログラムを書く必要があります。信じられないほど単純ですが、GLPK# はおろか、呼び出し可能ライブラリーを使用して GLPK の整数プログラムを作成する方法についての良い情報がほとんどないという問題があります。

私の整数プログラムは次のようになります。

Maximise: X[0] + X[1] + ... + X[n];

s.t.      X[1] + X[5] <= 1;
          X[1] + X[7] <= 1;
          X[2] + X[4] <= 1;
          X[3] + X[9] <= 1;
          ...
          X[i] = {0,1}

バイナリ X がたくさんあり、合計を最大化したいと考えています。特定の X は、他の特定の X を除外します。

私がこれまでにできたのは、

LPProblem lp = new LPProblem()
{
  ModelClass = MODELCLASS.MIP,
  ObjectiveDirection = OptimisationDirection.MAXIMISE,
  ObjectiveName = "Z"
};

// Stuff goes here, I'm not sure how to represent the model

SOLVERSTATUS status = lp.SolveInteger();
4

3 に答える 3

4

GLPK# 以外のものを使用することもできます。学者なら、CPLEX または Gurobi を無料で入手できます。それ以外の場合、Google OR Tools は過去 1 年間 C# をサポートしていました。Google OR Tools ページによると、GLPK と CBC のラッパーが含まれています。2 つのソルバーを切り替えることができるという単純な理由から、Google OR Tools の使用をお勧めします。特定のインスタンスでは、あるソルバーが他のソルバーよりも優れている場合があります。

于 2013-02-22T06:30:12.027 に答える
1

これをもう少し記入するための他のいくつかのコメント。まず、GLPKは問題ありませんが、大規模なモデルでは非常に低速です。大きな問題に直面している場合（将来的にはそうであっても）、すでに述べたような他のソルバーを検討する方がよい場合があります。また、GLPK＃の開発は非常に静かなようです-私はほぼ2年間更新を見ていません。それは良いことかもしれません（それは安定していて動作するので、なぜそれを変更するのですか）、またはそれが行き詰まっている可能性があります。

すでに述べたように、GurobiとCPLEXはどちらも非常に強力で強力な高速ソルバーであり、C＃で優れたモデリングAPIを提供します。あなたがそれらにアクセスすることができれば、彼らは本当にそれだけの価値があります。SCIPソルバーは優れています-おそらく非商用ソルバーの中で最高ですが、C＃インターフェイスについてはよくわかりません。

Google ORツールのもう1つの潜在的な利点は、制約プログラミングに重点を置いていることです。バイナリ変数と制約の複雑なセットがある場合、CPアプローチにはいくつかの利点があります。

于 2013-02-28T11:06:14.423 に答える
1

あなたが説明する問題は、「最大クリーク問題」と呼ばれます。頂点に 1 ～ n のラベルが付いた無向グラフを作成します。x[i] + x[j] <= 1 という形式の制約がある場合、i と j の間にエッジを描画します。H を補グラフとします。つまり、G の i と j の間にエッジがない場合に限り、i と j の間にエッジがあります。クリークは頂点のサブセットで、それぞれがあなたの問題は、最大サイズのクリークを見つけることです。これは有名な NP 完全問題です。それにもかかわらず、これを解決するための非常に優れたヒューリスティック アルゴリズム (およびおそらく利用可能なソフトウェア) が多数あります。次の調査を見てください http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.5821

あなたが与える IP 定式化はあまり厳密ではないため、n がかなり小さい場合を除き、CPLEX や GUROBI などのトップ ソルバーを使用しても、その定式化では適切な時間内に問題を解決できない可能性があります。

于 2013-06-09T16:28:40.480 に答える