割り当ての最適化/設定のカバー

Question

私は次の作業を行っていて、解決策が見つかりませんでした。

ネットワークノードの配置に最適なソリューションを見つける必要があります。目的は、接続ケーブルの掘削コストを最小限に抑えることです。いくつかの掘削コストはお互いに依存します。例えば。 2つのノードが並んでいて最初に1つのケーブルを掘ったとすると、この掘削コストを第2ノードへの掘削のための第1ノードに含める必要はありません。しかし、2番目のノードを選択するだけでは、ノード1とノード1からノード2に掘削コストを追加する必要があります。

各ノードには、特定の数のユーザーが用意されています。例えば、少なくともユーザのカバレッジに到達する。ユーザーの90％が制約です。

は、私は次計画を使用しようとしたが、CVXはそれを好きではない：良いアイデアを持つ誰もが例えばバイナリ線形または二次計画を使用して...

cvx_begin 
variable x(n,1) binary; 
minimize(x'*Q*x) 
subject to 
    x'*A*x >= 0.9; 
cvx_end 

ありますか？おかげで、BR

Answer 1

x'Ax

はa(i,j)*x(i)*x(j)の合計です。あなたは、リニアMIPの問題を抱えている。これにより

z(i,j) <= x(i) 
z(i,j) <= x(j) 
z(i,j) >= x(i)+x(j)-1 
z(i,j) in {0,1} 

：製品z(i,j)=x(i)*x(j)はによって直線化することができます。

私たちは、この製剤中で使用することができ、いくつかの最適化があります。

• 私たちは、対角線がx(i)^2=x(i)
• z(i,j)」として特別に扱うことができ、対称
• を利用することにより、AとQ三角行列を作ることができますが、 sは厳密に三角形構造に縮小することができます。