CPLEXのサンプルの組み立てスケジューリングAssembly Sequencing（CPLEX OPL CPLEXサンプル CP）を読み解きます。
<サンプル導入ディレクトリ>opl\examples\opl\sequence\sequence.mod
にあります。
-
実行環境
- CPLEX 22.1.1
- Windows 11 64bit
-
サンプル
●コード
この記事でのサンプルは、オリジナルのサンプルとほぼ同じ内容ですが、日本語コメントを入れたり順序を入れ替えたり、添え字を入れ替えたりして読みやすくしています
●サンプルデータ
問題
このモデルは、組立ラインで処理される一連のカスタム コンピューターの組立順序を決定するものです。
各コンピューターは様々な部品を持ちます。部品によって連続で組立できる個数の上限があったり、逆に最小でも連続で組立しなければならない個数があったり、ある部品の組立の後には組立できない部品があったり、という制約があります。
利用データ
- コンピューターの情報：必要な部品
２. 部品の情報：連続組立の最大最小条件と後続禁止部品
この表は以下のようなことを示しています。
・CPU150は2台まで連続で取り付け可能です。
・SoundCardは2台連続で取り付ける必要があります。
・CDRWの後にTapeの取り付けは不可能です。
決定変数
- コンピューターの組立順序
目的関数
目的関数はない。
制約
- 最大連続：部品毎に、その部品必要とするコンピューターを連続で組立できる上限台数がある。
- 最小連続：部品毎に、その部品必要とするコンピューターを連続で組立しなければならない台数がある。
- 各部品に、不正なフォロワー (「illegalFollowers」)がある場合、次の組立では、その不正な部品は含まれてはならない。
問題の種類
制約プログラミング
目的関数
なし
決定変数と解
１. コンピューター組立順序
決定変数は組み立てる順序に並べ替えたコンピューター番号になります。以下はわかりやすいように含まれるコンポーネントも一緒に表示しています。
OPLコード解説
OPLコードの解説を行っていきます。
利用データ
まずコンピュータータイプと部品のデータの定義を行っています。
データの中身の定義はsequence_hkwd.datファイルの中で行っています。
組み立てる必要があるコンピューターの台数(mod)
int nComputers = ... ;
range AllComputers = 1..nComputers ;
組み立てる必要があるコンピューターの台数(dat)
nComputers = 6;
各部品タイプの名前のセットです。
部品タイプのセット(mod)
{string} ComponentTypes = ...; ;
}
部品タイプのセット(dat)
ComponentTypes=
{ "CPU150", "CPU250", "CPU450", "Modem288", "Modem336", "Modem56K",
"CDRW", "Cartridge", "Tape", "SoundCard", "VideoCard" };
次は、各部品の組み立てルールのセットです。
各部品タイプには、各部品の組み立てルール（最大連続、最小連続、不正なフォロワーのセット）のタプルの配列が定義されます。
各部品の組み立てルール(mod)
//組み立てルール（最大連続、最小連続、不正なフォロワーのセット）のタプル
tuple ComponentInfo
{
int maxSeq;
int minSeq;
{string} illegalFollowers;
};
// Assembly rules for each component
// 各部品の組み立てルールのタプルの配列
ComponentInfo components[ComponentTypes] = ...;
#[]#はペア (添字、値) で配列を初期化する記述方法です。
各部品の組み立てルール(dat)
components = #[
CPU150: <2,1,{}>,
CPU250: <5,1,{}>,
CPU450: <5,1,{}>,
Modem288: <2,1,{}>,
Modem336: <5,1,{}>,
Modem56K: <5,1,{}>,
CDRW: <5,1,{Tape}>,
Cartridge: <5,1,{}>,
Tape: <6,1,{}>,
SoundCard: <2,2,{}>,
VideoCard: <6,1,{}>
]#;
問題ブラウザで見ると以下のようになっています。
コンピュータに必要な部品のセットのリスト(mod)
{string} computer[AllComputers] = ...;
コンピュータに必要な部品のセットのリスト(dat)
computer = [{CPU450, Modem56K, CDRW, VideoCard, SoundCard},
{CPU250, Modem336, Tape, VideoCard},
{CPU250, Modem288, Cartridge, VideoCard,SoundCard},
{CPU450, Modem56K, Tape, VideoCard, SoundCard},
{CPU250, Modem336, CDRW, VideoCard},
{CPU150, Modem288, Cartridge, VideoCard,SoundCard}];
問題ブラウザで見ると以下のようになっています。
assertでAllComputersの部品がComponentTypesで定義されているかの確認をしています。
全てのコンピューターの部品がComponentTypesで定義されているかの確認
assert {
forall (a in AllComputers)
forall (s in computer[a])
s in ComponentTypes;
}
ジェネリック集合の記述方法で、実際にコンピュータに組み込まれて構築される部品をセットに抽出しています。
ジェネリック集合は、「p in S : condition」の式の論理積です。このサンプルだと「c in computer[a] 」を満たす、部品cの論理積です。つまり使われているすべての部品を重複なしで選択しています。
実際にコンピュータに利用されている部品のセット
{string} UsedComponentTypes = { c | c in ComponentTypes, a in AllComputers : c in computer[a] };
問題ブラウザで見ると以下のようになっています。
assertでUsedComponentTypesがComponentTypesで定義されているかの確認をしています。
全ての利用部品がComponentTypesで定義されているかの確認
assert {
forall (u in UsedComponentTypes)
u in ComponentTypes;
}
同様にジェネリック集合の記述方法で、不正なフォロワーを持つ部品をセットに抽出しています。
「d in components[c].illegalFollowers」を満たす、部品cの論理積です。つまり利用されているillegalFollowersの部品を利用しているすべての部品を重複なしで選択しています。
不正なフォロワーを持つ部品
{string} HasIllegalFollowers = { c | c in UsedComponentTypes, d in UsedComponentTypes
: d in components[c].illegalFollowers };
問題ブラウザで見ると以下のようになっています。「Tape」という不正なフォロワーを持つ「CDRW」が抽出されています。
assertでHasIllegalFollowersの部品がComponentTypesで定義されているかの確認をしています。
不正なフォロワーを持つ部品がComponentTypesで定義されているかの確認
assert {
forall (u in HasIllegalFollowers)
u in ComponentTypes;
}
同様にジェネリック集合の記述方法で、各部品がどのコンピューターで利用されているかのセットをセットの配列に抽出しています。
「c in computer[i]」を満たす、コンピューターの番号iの論理積を部品ごとにセットにしています。
各部品がどのコンピューターで利用されているかのセット
{int} componentInComputer[c in UsedComponentTypes] = {i | i in AllComputers : c in computer[i] };
問題ブラウザで見ると以下のようになっています。各部品ごとにどのコンピューターで使われているかのセットを持っています。
assertでcomponentInComputerのコンピューターが１からnComputers（=6)の範囲で定義されているかの確認をしています。
componentInComputerに結びつくコンピューターが定義されているかの確認
assert {
forall (c in UsedComponentTypes)
forall (u in componentInComputer[c]) {
u >=1;
u <= nComputers;
}
}
決定変数
次に決定変数の定義を行っています。
dvarが決定変数を意味します。
computerInSeq[i]=j の場合、 組立順序内で[i] 番目のコンピュータがjであることを意味します（オリジナル・サンプルソースコードのコメントのiとjの解説は間違っています）。
決定変数:組立順序
dvar int computerInSeq[1..nComputers] in AllComputers;
これらの決定変数は、求められた解では以下のようになりました。
目的関数
ありません。
制約
次に制約の定義を行っています。
subject toの中カッコで囲みます。
制約（mod）
subject to{
---略----
}
制約0:コンピューターはすべて異なる
allDifferent関数で配列内の値が全て異なるように制約しています。つまりおなじコンピューターを組み立てないようにしています。
制約1:コンピューターはすべて異なる
allDifferent(computerInSeq);
制約1:最大連続：部品毎に、その部品必要とするコンピューターを連続で組立できる上限台数がある。
制約1:最大連続
forall (c in UsedComponentTypes) {
forall ( p in 1..nComputers - components[c].maxSeq )
// If there are maxSeq # of component c in a row starting from position p to p+maxSeq-1,
// => the (p+ maxSeq)th computer must not contain component c.
// 位置 p から p+maxSeq-1 までの行に部品 c の maxSeq # がある場合、
// => (p+ maxSeq) 番目のコンピューターには部品 c が含まれていてはなりません。
(sum(s in p..p+components[c].maxSeq-1) (computerInSeq[s] in componentInComputer[c]) == components[c].maxSeq)
=>
//not (computerInSeq[p+components[c].maxSeq] in componentInComputer[c]);
computerInSeq[p+components[c].maxSeq] not in componentInComputer[c];
};
なお、この制約にラベルをつけようとすると「Constraint labeling not supported for dimensions with variable size, use named constraints instead.」というエラーになってしまうため、問題ブラウザーでは確認ができませんでした。
例としてc="SoundCard"かつp=1についてみていきます。
段階的に展開すると以下のようになります。
forall (c in UsedComponentTypes) {
→ c="SoundCard"
forall ( p in 1..nComputers - components[c].maxSeq )
→ forall ( p in 1..6 - components["SoundCard"].maxSeq )
→ forall ( p in 1..6 - 2 )
→ forall ( p in 1..4 )
→ p=1
// If there are maxSeq # of component c in a row starting from position p to p+maxSeq-1,
// => the (p+ maxSeq)th computer must not contain component c.
// 位置 p から p+maxSeq-1 までの行に部品 c の maxSeq # がある場合、
// => (p+ maxSeq) 番目のコンピューターには部品 c が含まれていてはなりません。
(sum(s in p..p+components[c].maxSeq-1) (computerInSeq[s] in componentInComputer[c]) == components[c].maxSeq)
→ (sum(s in 1..1+components["SoundCard"].maxSeq-1) (computerInSeq[s] in componentInComputer["SoundCard"]) == components["SoundCard"].maxSeq)
→ (sum(s in 1..2) (computerInSeq[s] in {1 3 4 6}) == 2)
→ ((computerInSeq[1] in {1 3 4 6} + computerInSeq[2] in {1 3 4 6}) == 2)
→ ((1 in {1 3 4 6} + 6 in {1 3 4 6}) == 2)
→ (2) == 2)
TRUE
=>
//not (computerInSeq[p+components[c].maxSeq] in componentInComputer[c]);
computerInSeq[p+components[c].maxSeq] not in componentInComputer[c];
→ computerInSeq[1+components["SoundCard"].maxSeq] not in componentInComputer["SoundCard"];
→ computerInSeq[1+2] not in {1 3 4 6};
→ 2 not in {1 3 4 6};
→ TRUE
};
さらに分解して考えていきます。
まず、forallの意味を考えます。
チェックが必要なコンピューターを特定
→ forall ( p in 1..4 )
1番目から4番目までの順序のコンピューターまでしかチェックしないということを言っています。SoundCardのmaxSeqは2ですから、5番目以降はどんなコンピューターを選んでもSoundCardが2回以上連続することはないのでチェックを省略しているのです。
次にp=1についてみていきます。
前半の条件の
maxSeq分連続しているかどうかのチェック
→ (sum(s in 1..2) (computerInSeq[s] in {1 3 4 6}) == 2)
の式では、SoundCardのmaxSeqである2つ分のcomputerInSeqをみてcomponentInComputerにあるコンピューターの台数が合計2個になるかをチェックしています。
図で表すと以下のイメージです。
つまりSoundCardを含むコンピューターを2台続けているかのチェックをしています。
「=>]は「上の条件が成り立つならば」という意味です。この例の場合「SoundCardが2回連続で続いていたならば」という意味です。条件に当てはまりましたので後半の条件も確認していきます。
後半の条件の
maxSeq分連続したら、次は連続していないかどうかのチェック
→ computerInSeq[1+components["SoundCard"].maxSeq] not in componentInComputer["SoundCard"];
はチェックした分の次の組立に、サウンドカードが含まれているコンピューターがないかということを意味しています。
図で表すと以下のイメージです。
3番目のコンピューターにはSoundCardが含まれていませんので、TRUEになります。制約を満たしたことになります。
制約2:最小連続の制約
この制約は1番目の組立とそれ以降で記述が変わるので、2つ別に定義しています。
制約2-1:1 番目のコンピューターの部品は、少なくとも minSeq # 回連続して出現する必要があります。
制約2-1:1 番目のコンピューターの部品は、少なくとも minSeq # 回連続して出現する必要があります。
forall (c in UsedComponentTypes) {
// The components in the 1st computer must appear at least minSeq # of times in a row.
// 1番目のコンピューターの最小連続の制約
ct2firstComponentHigherThanMinseq:
(computerInSeq[1] in componentInComputer[c])
=>
((sum( s in 1..components[c].minSeq) (computerInSeq[s] in componentInComputer[c])) >= components[c].minSeq);
}
例としてminseqが2以上のc="SoundCard"についてみていきます。
段階的に展開すると以下のようになります。
forall (c in UsedComponentTypes) {
→ c="SoundCard"
// 1番目のコンピューターの最小連続の制約
ct2firstComponentHigherThanMinseq:
(computerInSeq[1] in componentInComputer[c])
→ (computerInSeq[1] in componentInComputer["SoundCard"])
→ (computerInSeq[1] in {1 3 4 6})
→ (1 in {1 3 4 6})
→ TRUE
=>
((sum( s in 1..components[c].minSeq) (computerInSeq[s] in componentInComputer[c])) >= components[c].minSeq);
→ ((sum( s in 1..components["SoundCard"].minSeq) (computerInSeq[s] in componentInComputer["SoundCard"])) >= components["SoundCard"].minSeq);
→ ((sum( s in 1..2) (computerInSeq[s] in {1 3 4 6})) >= 2);
→ (((computerInSeq[1] in {1 3 4 6})+(computerInSeq[2] in {1 3 4 6})) >= 2);
→ (((1 in {1 3 4 6})+(6 in {1 3 4 6})) >= 2);
→ (((1 in {1 3 4 6})+(6 in {1 3 4 6})) >= 2);
→ (2 >= 2);
→ TRUE
}
前半の条件の
前半の条件
→ (computerInSeq[1] in {1 3 4 6})
は、1番目のコンピューターがSoundCardを持つコンピューターに含まれているかをチェックしています。
後半の条件の
前半の条件
→ ((sum( s in 1..2) (computerInSeq[s] in {1 3 4 6})) >= 2);
は、1-2番目のコンピューターがSoundCardを持つコンピューターに含まれているかをチェックしています。つまり2台連続で組み立てているかの制約になっています。
問題ブラウザで見ると以下のようになります。
図にすると以下のようなイメージになります。
制約2-2:2番目以降のコンピューターの最小連続の制約
制約2-2:2番目以降のコンピューターの最小連続の制約
forall (c in UsedComponentTypes) {
forall ( p in 1..nComputers-components[c].minSeq )
// Every component that is not in computer p but appears in computer p+1
// must appear minSeq # of times in a row from p+1 to p+minSeq.
// コンピューター p には存在しないが、コンピューター p+1 に表示されるすべての部品
// minSeq は p+1 から p+minSeq まで連続して何回も出現する必要があります。
//ct3:
(((computerInSeq[p] not in componentInComputer[c])
&& (computerInSeq[p+1] in componentInComputer[c]))
=>
(sum(s in p+1..p+components[c].minSeq) (computerInSeq[s] in componentInComputer[c]))
== components[c].minSeq);
};
例としてminseqが2以上のc="SoundCard"のp=4についてみていきます。
段階的に展開すると以下のようになります。
forall (c in UsedComponentTypes) {
→ c="SoundCard"
forall ( p in 1..nComputers-components[c].minSeq )
→ p=4
// コンピューター p には存在しないが、コンピューター p+1 に表示されるすべての部品
// minSeq は p+1 から p+minSeq まで連続して何回も出現する必要があります。
//ct3:
(((computerInSeq[p] not in componentInComputer[c])
&& (computerInSeq[p+1] in componentInComputer[c]))
→ (((computerInSeq[4] not in componentInComputer["SoundCard"])
&& (computerInSeq[4+1] in componentInComputer["SoundCard"]))
→ (((5 not in {1 3 4 6})
&& (3 in {1 3 4 6}))
→ TRUE
=>
(sum(s in p+1..p+components[c].minSeq) (computerInSeq[s] in componentInComputer[c]))
== components[c].minSeq);
→ (sum(s in 4+1..4+components["SoundCard"].minSeq) (computerInSeq[s] in componentInComputer["SoundCard"]))
== components["SoundCard"].minSeq);
→ (sum(s in 5..4+2) (computerInSeq[s] in {1 3 4 6}))
== 2);
→ (sum(s in 5..6) (computerInSeq[s] in {1 3 4 6}))
== 2);
→ (computerInSeq[5] in {1 3 4 6} + computerInSeq[6] in {1 3 4 6})
== 2);
→ (3 in {1 3 4 6} + 4 in {1 3 4 6})
== 2);
→ (2)
== 2);
→ TRUE
};
前半の条件の
→ (((computerInSeq[4] not in componentInComputer["SoundCard"])
&& (computerInSeq[4+1] in componentInComputer["SoundCard"]))
は、4番目のコンピューターはSoundCardを持たず、5番目のコンピューターに含まれていることをチェックしています。4番目という、SoundCardの連続の組立が始まる１つ前のチェックをしているところがポイントです。
図にすると以下のようなイメージになります。
後半の条件の
→ (computerInSeq[5] in {1 3 4 6} + computerInSeq[6] in {1 3 4 6})
== 2);
は、4番目に続く、5-6番目の2台のコンピューターがSoundCardを持つコンピューターに含まれているかをチェックしています。つまり2台連続で組み立てているかの制約になっています。
図にすると以下のようなイメージになります。
制約3:各部品に、不正なフォロワー (「illegalFollowers」)がある場合、次の組立では、その不正な部品は含まれてはならない。
制約3:各部品に、不正なフォロワー (「illegalFollowers」)がある場合、次の組立では、その不正な部品は含まれてはならない。
forall (c in HasIllegalFollowers) // for component c that has an illegal follower,不正なフォロワーを持つ部品 c の場合
forall( p in 1..nComputers-1) // for computer p コンピュータ用
forall( c2 in UsedComponentTypes : c2 in components[c].illegalFollowers)
// If computer p has component c and c2 is c's illegal follower =>
// c2 must not be in computer p+1
// コンピューター p に部品 c があり、c2 が c の不正なフォロワーである場合 =>
// c2 はコンピュータ p+1 にあってはなりません
ct4illegalfollower:
(computerInSeq[p] in componentInComputer[c] ) =>
(computerInSeq[p+1] not in componentInComputer[c2]);
例としてillegalFollowersを持つがc="CDRW"のp=1についてみていきます。
段階的に展開すると以下のようになります。
forall (c in HasIllegalFollowers) // for component c that has an illegal follower,不正なフォロワーを持つ部品 c の場合
→ c="CDRW"
forall( p in 1..nComputers-1) // for computer p コンピュータ用
→ p=1
forall( c2 in UsedComponentTypes : c2 in components[c].illegalFollowers)
→ forall( c2 in UsedComponentTypes : c2 in components["CDRW"].illegalFollowers)
→ forall( c2 in UsedComponentTypes : c2 in {"Tape"})
→ c2="Tape"
// If computer p has component c and c2 is c's illegal follower =>
// c2 must not be in computer p+1
// コンピューター p に部品 c があり、c2 が c の不正なフォロワーである場合 =>
// c2 はコンピュータ p+1 にあってはなりません
ct4illegalfollower:
(computerInSeq[p] in componentInComputer[c] ) =>
→ (computerInSeq[1] in componentInComputer["CDRW"] ) =>
→ (1 in {1 5} ) =>
→ TRUE =>
(computerInSeq[p+1 not in componentInComputer[c2]);
→ (computerInSeq[1+1] not in componentInComputer["Tape"]);
→ (computerInSeq[2] not in {2 4});
→ (6 not in {2 4});
→ TRUE;
前半の条件の
→ (computerInSeq[1] in componentInComputer["CDRW"] ) =>
は、1番目のコンピューターはCDRWが含まれていることをチェックしています。
後半の条件の
→ (computerInSeq[1+1] not in componentInComputer["Tape"]);
は、2番目のコンピューターはTapeが含まれていないことをチェックしています。
図にすると以下のようなイメージになります。
問題ブラウザで見ると以下のようになります。
完成OPL
製品サンプルとほぼ同じ内容ですが、日本語コメントを入れたり順序を入れ替えたり、添え字を入れ替えたりして読みやすくしています。
sequence_hkwd.mod
/* ----------------------------------------------------
アセンブリの順序付け
----------------------------------------------------- */
using CP;
execute{
}
// The number of computers we need to build
// 組み立てる必要があるコンピューターの台数
int nComputers = ... ;
range AllComputers = 1..nComputers ;
// 部品タイプのセット
{string} ComponentTypes = ...;
//組み立てルール（最大連続、最小連続、不正なフォロワーのセット）のタプル
tuple ComponentInfo
{
int maxSeq;
int minSeq;
{string} illegalFollowers;
};
// Assembly rules for each component
// 各部品の組み立てルールのタプルの配列
ComponentInfo components[ComponentTypes] = ...;
// List of components needed by a computer
// コンピュータに必要な部品のセットのリスト
{string} computer[AllComputers] = ...;
//全てのコンピューターの部品がComponentTypesで定義されているかの確認
assert {
forall (a in AllComputers)
forall (s in computer[a])
s in ComponentTypes;
}
// Components that are actually in computers to build
// 実際に実際にコンピュータに利用されている部品のセット
{string} UsedComponentTypes = { c | c in ComponentTypes, a in AllComputers : c in computer[a] };
// 全ての利用部品がComponentTypesで定義されているかの確認
assert {
forall (u in UsedComponentTypes)
u in ComponentTypes;
}
// Components that have illegal followers
// 不正なフォロワーを持つ部品
{string} HasIllegalFollowers = { c | c in UsedComponentTypes, d in UsedComponentTypes
: d in components[c].illegalFollowers };
//{string} HasIllegalFollowers = { c | c in UsedComponentTypes: c in components[c].illegalFollowers };
// 不正なフォロワーを持つ部品がComponentTypesで定義されているかの確認
assert {
forall (u in HasIllegalFollowers)
u in ComponentTypes;
}
// Which computers contain the component
// 各部品がどのコンポーネントで利用されているかのセット
{int} componentInComputer[c in UsedComponentTypes] = {i | i in AllComputers : c in computer[i] };
// componentInComputerに結びつくコンピューターが定義されているかの確認
assert {
forall (c in UsedComponentTypes)
forall (u in componentInComputer[c]) {
u >=1;
u <= nComputers;
}
}
/* ----------------------------------------------------
* Variables:
* computerInSeq -- if computerInSeq[i]=j, it means computer[i] is jth in the
* sequence
* 決定変数:
* 組立順序-- computerInSeq[i]=j の場合、 組立順序内で[i] 番目のコンピュータがjであることを意味します
* --------------------------------------------------- */
dvar int computerInSeq[AllComputers] in AllComputers;
/* ----------------------------------------------------
* Constraints
* 制約
* --------------------------------------------------- */
subject to
{
// 制約0:コンピューターはすべて異なる
ct0allDifferent:
allDifferent(computerInSeq);
// 制約1:最大連続
forall (c in UsedComponentTypes) {
forall ( p in 1..nComputers - components[c].maxSeq )
// If there are maxSeq # of component c in a row starting from position p to p+maxSeq-1,
// => the (p+ maxSeq)th computer must not contain component c.
// 位置 p から p+maxSeq-1 までの行に部品 c の maxSeq # がある場合、
// => (p+ maxSeq) 番目のコンピューターには部品 c が含まれていてはなりません。
// ct1:
(sum(s in p..p+components[c].maxSeq-1) (computerInSeq[s] in componentInComputer[c]) == components[c].maxSeq)
=>
//not (computerInSeq[p+components[c].maxSeq] in componentInComputer[c]);
computerInSeq[p+components[c].maxSeq] not in componentInComputer[c];
};
// 制約2-1:1 番目のコンピューターの部品は、少なくとも minSeq # 回連続して出現する必要があります。
forall (c in UsedComponentTypes) {
// The components in the 1st computer must appear at least minSeq # of times in a row.
// 1番目のコンピューターの最小連続の制約
ct2firstComponentHigherThanMinseq:
(computerInSeq[1] in componentInComputer[c])
=>
((sum( s in 1..components[c].minSeq) (computerInSeq[s] in componentInComputer[c])) >= components[c].minSeq);
}
// 制約2-2:2番目以降のコンピューターの最小連続の制約
forall (c in UsedComponentTypes) {
forall ( p in 1..nComputers-components[c].minSeq )
// Every component that is not in computer p but appears in computer p+1
// must appear minSeq # of times in a row from p+1 to p+minSeq.
// コンピューター p には存在しないが、コンピューター p+1 に表示されるすべての部品
// minSeq は p+1 から p+minSeq まで連続して何回も出現する必要があります。
//ct3:
(((computerInSeq[p] not in componentInComputer[c])
&& (computerInSeq[p+1] in componentInComputer[c])) =>
(sum(s in p+1..p+components[c].minSeq) (computerInSeq[s] in componentInComputer[c]))
== components[c].minSeq);
};
// 制約3:各部品に、不正なフォロワー (「illegalFollowers」)がある場合、次の組立では、その不正な部品は含まれてはならない。
forall (c in HasIllegalFollowers) // for component c that has an illegal follower,不正なフォロワーを持つ部品 c の場合
forall( p in 1..nComputers-1) // for computer p コンピュータ用
forall( c2 in UsedComponentTypes : c2 in components[c].illegalFollowers)
// If computer p has component c and c2 is c's illegal follower =>
// c2 must not be in computer p+1
// コンピューター p に部品 c があり、c2 が c の不正なフォロワーである場合 =>
// c2 はコンピュータ p+1 にあってはなりません
ct4illegalfollower:
(computerInSeq[p] in componentInComputer[c] ) =>
(computerInSeq[p+1] not in componentInComputer[c2]);
};
データは以下です。
sequence_hkwd.dat
// 組み立てる必要があるコンピューターの台数
nComputers = 6;
// 部品タイプのセット
ComponentTypes=
{ "CPU150", "CPU250", "CPU450", "Modem288", "Modem336", "Modem56K",
"CDRW", "Cartridge", "Tape", "SoundCard", "VideoCard" };
//各部品の組み立てルールのタプルの配列
components = #[
CPU150: <2,1,{}>,
CPU250: <5,1,{}>,
CPU450: <5,1,{}>,
Modem288: <2,1,{}>,
Modem336: <5,1,{}>,
Modem56K: <5,1,{}>,
CDRW: <5,1,{Tape}>,
Cartridge: <5,1,{}>,
Tape: <6,1,{}>,
SoundCard: <2,2,{}>,
VideoCard: <6,1,{}>
]#;
//コンピュータに必要な部品のセットのリスト
computer = [{CPU450, Modem56K, CDRW, VideoCard, SoundCard},
{CPU250, Modem336, Tape, VideoCard},
{CPU250, Modem288, Cartridge, VideoCard,SoundCard},
{CPU450, Modem56K, Tape, VideoCard, SoundCard},
{CPU250, Modem336, CDRW, VideoCard},
{CPU150, Modem288, Cartridge, VideoCard,SoundCard}];
参考
製造：生産計画- IBM Documentation
CPLEXサンプルを読み解く記事一覧