scip - Zimpl:非線形制約

Question

タイプの制約があります（zmpl内）

S1 の合計 (i,j) : x[i,j]*c[i,j]<=100

ここで、x は 2 次元のバイナリ変数で、c[i,j] はパラメーターです。これを次のように変更したい

sum (i,j) in S1 : x[i,j]*c[i,sum (i) x[i,j]]<=100

基本的に、2 番目のインデックスのパラメーターは、i 番目の行で選択された変数の数に依存します。これを行う効果的な方法はありますか？

Answer 1

まず、変数式でパラメータにインデックスを付けることはできません。これは、本質的にそれらも変数にするためです。

代わりに、追加の変数を使用して目的の制約をモデル化することをお勧めし、可能な限りシンプルにしようとしています。

set S2 := { 0..card(S1) }; # new set to model all possible outcomes of the sum operation

var y[S1] >= 0;   # y models nonnegative coefficients c[i,j]

var z[S2] binary; # models the value of the x-sum 

subto binlink: sum <i,j> in S1: x[i,j] - sum <s> in S2: s * z[s] == 0;
# binlink expresses the outcome of the x-sum in z

subto partition: sum <s> in S2: z[s] == 1; 
# maybe redundant because of binlink, but easy to write

subto coeflink: forall <i,j> in S1: y[i,j] == sum <s> in S2: c[i,s] * z[i,s]
#links continous coefficient variable to coefficient parameter

subto yourcons: sum <i,j> in S1: x[i,j] * y[i,j] <= 100;
# finally...

この定式化は非線形ですが、試してみる価値があると思います。その有効性は、定式化の「動的係数」の数と、私の回答で定義されたセットS2のサイズに大きく依存します。