k-MSTの整数LP正式化をお探しください

Question

私はk-Minimum Spanning Tree problemのInteger LP公式化をお探しです。

私の考え：

• x_ij = 1は、ツリー内のiからjへのエッジが存在することを意味します。
• Y_I = 1 iはツリーの一部である頂点を意味
• c_ijあるiからjへのエッジのコスト

目的関数：全てのi、jについて 分和（x_ij * c_ij）すべてのjについて

1. 和Y_I = K（1）
2. 和（x_ij）と、いくつかのI> = YI（2）
01：

制約すべてのjについて

3. 合計（x_ji）と、いくつかのI> = YI（3）
4. 2 * x_ij < = YI + YJ

（1）正確MSTにおけるkの頂点があることを確認します。 （2）および（3）は、ノードiがツリー内にある場合、そのノードを含む少なくとも1つのエッジがツリー内にあることを確認します。 （4）は、ツリー内にiとjの間にエッジがある場合、頂点iとjもツリー内になければならないことを示しています。

残念ながら、それは期待どおりに動作しません。誰かが私の間違いを知っていますか？

Answer 1

選択したサブグラフが接続されていることを確認する必要があります。