2

AMPL で小さな問題を解決しようとしていますが、それを制約に変換できないという問題に直面しました。問題は次のとおりです。 A、B、およびCの 3 つのセットがあるとします。Cの 1 つのサブセットに存在する場合、 A の2 つ以下の要素がBの 1 つの要素にリンクされるように、A の要素をBの要素にリンクしたい( Cの任意のサブセットの 3 つの要素のうち最大 2 つ) Bの 1 つの要素にリンクされています)。私はすでにこの部分をやった

この制約を書いたとします。

subject to constr {(i,j,k) in C, b in B}: x[i,b] + x[j,b] + x[k,b] <= 2;

コードの目的は、次の場合を最大化することです。 {(i,j,k) in C, b in B}: x[i,b] + x[j,b] + x[k,b] <= 1;

つまり、次の場合を最小限に抑えるために:

{(i,j,k) in C, b in B}: x[i,b] + x[j,b] + x[k,b] = 2;.

この目的はどのように書けばよいでしょうか？また、( constraint is = 2 ) <= 定数 (MAX など)の回数を取得したい場合、どうすればそれを行うことができますか? 以下は、これまでに書いたコードです。AMPL の学生版と cplex の学生版を使用しています。どうぞよろしくお願いいたします。

set A;
set B;
set C within A cross A cross A;
param constant:= 5;
var x{A,B} binary;
subject to constr1 {(i,j,k) in C, b in B}: x[i,b]  + x[j,b] + x[k,b] <= 2;
subject to onlyOneLinkForEachElementInA {a in A}: sum{b in B} x[a,b] = 1;
data;
set A:= 0 a b c d e f;  #note that 0 is used only to pad the subsets and force them to have dimension of 3
set B:= 1 2 3;
set C: 0 a b c d e f:=
(a,b,c) (a,c,0) (c,d,0) (e,f,b) (a,b,0) (f,b,0);
solve;
for {i in A :i!=0} { printf "%s\t",i;for{c in B} {if x[i,c]=1 then printf "%s\n",c;}};

私はこれを試しましたが、うまくいきませんでした（numberofもうまくいきませんでした）：

subject to constr2 {b in B}: count {(i,j,k) in C} ( (x[i,b] + x[j,b] + x[k,b]) = 2 ) <= MAX;ここで、MAX は次のように宣言されます。

param MAX:= 5;
4

1 に答える 1

2

線形および (一部の) 二次式のみを最適化できます。回数を最小限に抑えようとしているため x[i,b] + x[j,b] + x[k,b] == 2、追加の指標変数が必要です。

var has_2{C} binary;
minimize has_2 sum((i,j,k) in C) not_2[i,j,k]
subject to constr1 {(i,j,k) in C, b in B}: x[i,b] + x[j,b] + x[k,b] - has_2[i,j,k] <= 1

constr1 は、x 変数の 2 つが 1 の場合、has_2 を強制的に 1 にします。x 変数の 0 または 1 つが 1 の場合、目的関数は has_2 を強制的に 0 にします。x変数が既にバイナリである場合は、has_2 を作成した方がよい場合があります。特に、変数よりも has_2 変数の方が多いことを考慮して、上限 1 で連続しxます。

于 2014-07-21T02:40:06.143 に答える