GurobiでSteiner Treeを集める賞を受賞

Question

私は数学的プログラミングの問題をモデリングするのが初めてです。私はGurobiソルバーを使ってネットワーク最適化に関する練習問題を解決しようとしています。これは練習問題です：

`添付ファイルのグラフグラフ10092015.gmlには、通信会社が光ファイバネットワークに接続できる潜在的なキャビネットのセットが含まれています。各キャビネット（ノード）uには利益が関連付けられており、各エッジuvには接続コストが関連付けられています。

1. リンクのインストールの予算が4000ユーロを超えないことを知って、企業利益を最大化するネットワークを設計します。前回の最適解から
2. 、無料のキャビネット4と14 `

のために接続されているキャビネットに無線ルータをインストールするには、500ユーロのコストでキャビネット19にネットワークを拡張するの利便性を評価しますあなたはこれについてどう思います

formulation of the problem

：私はスタイナー木の収集賞として問題を定式化？これを解決するには、切断面アプローチを使用して分離問題を定義する必要がありますか？

私は問題をモデル化する方法を考え出したと思いますが、このタイプの練習にはまだ自信が持てません。

ご協力いただきありがとうございます。

Answer 1

私はこの問題の解決策を以前に与えました。私はこの問題をPCSTとして定式化しました。私は、ネットワークを設計するためのコストに上限を課すという制約を加えました（それは費やす予算をモデル化しています）。

一度、最初のポイントの解決策を得ました。私はバイナリ変数kを導入しました。これは、1がキャビネット4,14のコストを無駄にし、ルータ設置のコストを19で追加することを示しています。次に：ポイント1で見つかった樹冠に19の接続を強制しました。 （2 * y [19]）< = yの場合と同じです。y [19] = 1

2-キャビネット19が樹木の中にある場合、4と14でも必要です。 3- [19]が樹木の中にある場合、ルーターが引き起こすコストの変化を導入します。[4] + y [14]

3-これは次のようになります。k [1] < = y [19]