材料の最適な利用 - ここでは、大きな巻き物状の材料から様々な形状を、材料の無駄を減らしコスト削減を測りながら行ないます。
多くの産業製品のメーカーが直面する深刻な問題として、大きな巻物状の材料より、最終製品に使われる様々な形状の切断があります。 イフコンピュータのある顧客は、この問題に取り組み、様々な形状(各角は90度のもの)を 無駄が最小限抑えて巻物に配置するシステムを開発しました。
採用された手法は、IF/Prologの制約処理パッケージを使用し、非常に効率的なシステムとなりました。異なる形状の方向と表面の位置で重なりが生じないように、制約が定義されます。
上の図は、直角四辺形が、材料の無駄を省いてどのように材料上に配置されるべきかを示しています。このような問題の最適化は簡単ではありません。オペレーションリサーチの分野では、これを解決するアルゴリズムが過去にも開発されてきましたが、十分とはいえませんでした。。
以下に、IF/Prologの制約論理プログラミングを使用してこのような問題をどう扱えば良いかを説明します。長方形が重ならないようにするという制約を設定し、この制約を組み込まみのbranch-and-boundソルバーに与え、すべての長方形の角に位置を割り当てます。そして、すべての長方形の最終端を最小限にし、材料の無駄を少なくします。
IF/Prologにより提供された高度なプログラミング構造により、この問題は1000行以下の非常に短いコードで解決することができるようになりました。
この問題の解決に、従来のオペレーションリサーチの手法を使用すれば、10倍以上のコード行が必要であったと考えられます。また、問題によっては、標準的なオペレーションリサーチの手法では扱うことができません。例えば、整数リニアプログラミングあるいは簡単なソルバーがそうです。問題を0/1のリニアな問題に下げて取り扱うことはできますが、これにより、変数の数が著しく増え、効率が下がります。
つまり、我々の手法は、ソフトウェアエンジニアリングの面からコスト的に効果的なばかりでなく、新しいアイデアあるいは制限を採用するための変更がしやすいような、より効率的な手法となっています。
材料の巻き物の上に4辺あるいは6辺の形状が複数個配置されます。この際に、材料の無駄は最小限に抑えられます。この形状はすべての角が90度で、お互いに90度の角を保ち、場合によっては異なった方向に置かれます。すべての形状は、材料の橋に対して90度の角を保って配置されます。つまり4辺形では配置方向の選択肢は2つあり、6辺形では4つあります。材料は十分長く取っていますが、幅は固定の長さで、形状を並べる長さはできる限り短くなければなりません。
また、形状の材料上への配置は、できる限り、最初に入ってきた注文の形状を最初に、後で入ってきた注文の形状を後にするようにすることが望まれています。
この問題は複雑な組合せが生じる問題です。例えば、100の四辺形の配置の可能性は10の375乗もあります。6辺形の場合複雑さはもっと増します。
この問題に取り組むにあたって、以下の点で複雑さを減らすことが考えられます。問題の対象性を減らし、考えられる可能な配置を限って、意味のあるヒューリスティックな決定を行なうようにすることです。
この問題を扱うに当たっての制約論理プログラミングの実際の力は、増幅的にアルゴリズムを開発することができることにあります。つまり、制約を何階層にも分けて構築することが可能です。制約自身は、ある解の探索空間を制限するために使われる相互依存性の複合的なネットワークを構築するためにいくつかの変数に影響を与えます。解は、組み込みのbranch-and-boundアルゴリズムを使用して算出されます。このアルゴリズムにより、一つの制約も破られず、同時にすべての形状の最終位置を確実に最適化するような値が変数に与えられます。
問題を小分解することにより、変数間の相互依存性を作るためにが、どのような異なる組み込みの制約方法が組み合わされているかがわかります。これらの変数は、概念モデルの形状の上にマッピングされ、可能な解の中の具体的な位置が言及されます。
以下の説明では、材料上の位置をスロットと呼びます。スロットは、どのような方向にあるどのような長方形であっても満たされます。スロットにはお互いに重ならないようにという制限がありますが、解を求めるために異なる形状と方向がbranch-and-bound探索で考慮されるために、次元と位置は変わります。 スロットは4面の形状、つまり長方形を表します。6辺形は、2つのスロットを占め、さらに形状の方向に応じてこの2つのスロットはお互いに関係を持ちつつ配置されるよう制約されます。
問題を記述するのに十分な制約を以下に紹介します。その後で、実際にこの条件がどのように具体的なコードにマップされるかを見てみましょう。
スロットは実装されるた際にはProlog構造として、長方形の端を表す4つの変数を持っています。
rectangle(Left,Right,Top,Bottom)
すべての制約は、充足される順序は決まっていません。 制約を適用し、コードを順次増幅的に開発・テストを繰り返すために、データ構造を越えたルーチンを使用し、その結果、制約が仕様通りに動作しているかどうかを確かめます。
次のルーチンのそれぞれが制約の階層を適用します。すべての階層と共に、問題がソルバーに送られます。
ここでは、いわゆる「硬い制約」が、各スロットの変数に与えられる値の範囲を限定しています。すべてのスロットと材料の Length(長さ) and Width(幅) が与えられれば、すべてのスロット変数が材料表面の上に存在するような以下の制約を当てはめることができます。
const_material([],_Length,_Width).
const_material([rectangle(L,R,T,B)|RTail],Length,Width) :-
[L,R] in 0:Length,
[T,B] in 0:Width,
const_material(RTail,Length,Width).
述語 in/2 は、変数の有限領域を特定します。領域は、上にあるように間隔として(範囲のチェックは内部で行なわる)、あるいは列挙(整数の分類されたリスト)あるいは列として特定されます。
組み込み述語relation/2は、Orientationsのリストで定義された可能な値の組のそれぞれに属するスロットの変数に制約をかけるために使用されます。スロットの端を示す変数である L, R, T Bは、形状の次元である X Yから値を得ています。
Orientationsのリストは、また、長方形のための識別子 (Id)と方向(Or)のフィールドを有しています。
組み込みのグローバル制約であるall_distinct/1は、個々の長方形の識別子は、確実に一度しか使われないようにするために使われます。
const_orientations([],[],[],_Orientations).
const_orientations([rectangle(L,R,T,B)|RTail],[Id|RIdTail],
[Or|ROrTail],Orientations) :-
R ?= L + X, T ?= B + Y,
relation([Id,Or,X,Y],Orientations),
const_orientations(RTail,RIdTail,ROrTail,Orientations).
const_ids(RectangleIds,No) :-
RectangleIds in 0..No,
all_distinct(RectangleIds).
2つのスロット間の次の比較制約が作られます。
const_no_overlap_rectangle(rectangle(LA,RA,TA,BA),rectangle(LB,RB,TB,BB)) :-
cardinality(1, 2, [LA ?>= RB, RA ?=< LB, BA ?>= TB, TA ?=< BB]).
組み込み述語であるcardinality/3は、リストの比較の中の少なくとも1つ多くとも2つが確実に適用されるように使用されます。この比較により、長方形が別の長方形のAの右、左、上あるいは下Bにあるようにと決められます。
6辺形状の場合は、隣接しお互いに動的に制約を受ける2つのスロットで表現されます。 隣同志でお互いに制約を受ける端が、長方形の方向スロットの変更の際に、変更するのでこの制約を適用することにより問題は、とても複雑になります。
この制約は、長方形の変数Idに関する条件ゴールを一時中断することによって実現されます。そしてIdの変数が、長方形を配置することにより値が与えられると、隣接するスロットが相方のスロットとなり、6辺の形状の構成します。スロットの方向変数に関する条件は、端の間の正しい制約を確実にするために当てはめられます。
6辺の形状の内のスロットの方向に応じて、2つの端の比較は、以下の形式でこの述語に渡されます。
(up -> (right = left), (down = down))
その後、以下のコードは、この構造的な情報をデコードし、この場合domain_if/3述語を使用して条件制約を生成します。
const_linkage([],_RId,_ROrA,_ROrB,_RectA,_RectB).
const_linkage([constraint(Id,Tests)|LTail],RId,ROrA,ROrB,RectA,RectB) :-
const_link_constraints(Tests,ROrA,RectA,RectB,Constraints),
domain_if(RId ?= Id,(ROrA ?= ROrB,Constraints)),
const_linkage(LTail,RId,ROrA,ROrB,RectA,RectB).
const_link_constraints([],_ROrA,_RectA,_RectB,true).
const_link_constraints([(Orient -> (RectAM1 = RectBM1),(RectAM2 = RectBM2))
|LinkTail], ROrA,RectA,RectB,Constraint) :-
const_match(RectAM1,RectA,EdgeAM1), const_match(RectBM1,RectB,EdgeBM1),
const_match(RectAM2,RectA,EdgeAM2), const_match(RectBM2,RectB,EdgeBM2),
Constraint = ( ROrA = Orient
-> EdgeAM1 ?= EdgeBM1,
EdgeAM2 ?= EdgeBM2
; ConTail),
const_link_constraints(LinkTail,ROrA,RectA,RectB,ConTail).
const_match(left, rectangle(L,_,_,_),L).
const_match(right,rectangle(_,R,_,_),R).
const_match(up, rectangle(_,_,T,_),T).
const_match(down, rectangle(_,_,_,B),B).
4つの制約の階層を使って、形状が重ならないような制約を表現することができます。
これらの制約ルーチンの適用順序はいずれから始めてもかまいません。。最終的な結果は、いずれにしろ同じです。変数が rectangle(L,R,T,B)のようなプログラム構造、R ?= X + Lのような制約にバインドされる変数のリストがいくつかあります。 そして、制約R ?= X + Lの中の2つの変数がわかればすぐに、探索を伝えるために瀬得い訳が使われ、三番目の変数に値が与えられます。変数に値が与えられ、値に依存したすべての他の制約が発火されると、探索においてどのような矛盾も許されず、探索スペースの多くは取り除かれます。
制約論理プログラムを解決する最後の段階は、branch-and-bound最適化ルーチンを呼び出すことです。この問題の場合、minimize_maximum/2 の述語を使うことが良いと考えられます。このケースでは、多くの解はありませんので、MaxTime秒の経過後にラベリング過程を時間切れでストップさせることにも意味があります。
minimize_maximum(label_tb(Vars,MaxTime,[]), Ends), label(Orientations)
Varsのリストは、スロットの中のすべての変数およびIDのスロットを有しています。方向や他の中間変数は、制約伝播により値を与えられます。それゆえに、通常、解が存在することが知られていても、すべての変数に値が割り当てられていないことがわかります。この例では、最適化の段階が終了した時に、一つの方向のみが存在するような値をOrientationsの変数にラベリングすることが必要です
上述のプログラムは形状の数が少ない時にはうまく働きます。が、12の形状で16のスロットが発生する時点で、問題の複雑さが顕著になり、我々の32Mb Pentium PCのメモリと時間限界を越え始めます。
もちろん、このプログラムをどのハードウェア上で走らせようが関係ありません。存在するすべてのマシンで、比較的少ない数の形状ではうまくいきますが、マシンの能力を越えることがあります。
この状況を解決するために、我々は問題自身と取り組みました。複雑さを取り除く新しい方法を設計しようとし、新しい制約の階層を適用し、探索スペースをより小さくしました。問題から対象性を取り除き、制約の新しい階層を加えました。
すべてのスロットが他のスロットと重ならないという制約を避けるために、材料の長さを越えてスロット群を配置しました。スロットのいくつかをスロットのセグメントとして定義しました。セグメントの隣接する組合せ内のすべてのスロットは従来通り、重なり合わないようにという制約が置かれています。さらに、一つ置いた隣接しないセグメントの中のすべてのスロットは、他のセグメントのすべてのスロットの右に来るように制約付けられています。セグメント1-Nに対して、次のセグメント配置制約は、セグメントを越えて完全な順序で並びます。
1 < 3 < 5 < 7 < 9 < 11 < . . .
2 < 4 < 6 < 8 < 10 < 12 . . .
1 < 4 < 7 < 10 < . . .
2 < 5 < 8 < 11 < . . .
3 < 6 < 9 < 12 . . .
再び、述語cardinality/3は、ある一つのスロットが2つのセグメントのすべてのスロットの右に来るようにします。すべての制約は、2つの「少なくとも」・「多くとも」の値が制約の数に一致した時に、充足します。ひとつのcardinality/3制約は、個々のスロットに対して、他のセグメントの他のスロットに関する制約を順づけを決定するように作られます。
const_segment_ordered([]).
const_segment_ordered([_Segment1]).
const_segment_ordered([_Segment2,_Segment1]).
const_segment_ordered([Segment3,_Segment2,Segment1]) :-
const_segment_right_of(Segment3,Segment1).
const_segment_ordered([Segment4,Segment3,Segment2,Segment1|SegmentTail]) :-
append(Segment1,Segment2,Segment12),
const_segment_right_of(Segment4,Segment12),
const_segment_ordered([Segment3,Segment2,Segment1|SegmentTail]).
const_segment_right_of([],_Segment12).
const_segment_right_of([rectangle(L,_R,_T,_B)|RTail],Segment12) :-
const_right_of_const(Segment12,L,Constraints),
list_length(Constraints,ConstraintLength),
cardinality(ConstraintLength, ConstraintLength, Constraints),
const_segment_right_of(RTail,Segment12).
const_right_of_const([],_Var,[]).
const_right_of_const([rectangle(_L,R,_T,_B)|RTail],Var,[R ?=< Var|CTail]) :-
const_right_of_const(RTail,Var,CTail).
例えば、4スロットで100の長方形のためのセグメントサイズの場合、必要な空間は、制約にして4950から676にまで必要なファクターが減少します。
問題を分割することにより、可能性のある解に関する制限が置かれます。材料を横切って一つのセグメント内に2倍以上の数のスロットは置かれません。このようにして、セグメントのサイズは、問題の可能な解に合うように調整されます。
いままでのところ、どのようなスロットでも長方形に当てはめることができるので、 制約階層2では、relation/3の制約が各スロットのために生成され、スロットの数分だけ多くの関係エレメントができます。この関係のため空間条件は、スロット数のN乗となります。
スロットは他のスロットに対して、材料上でどのような相対位置にも置くことができるので、対象性の中に取り除くことができるものが存在します。セグメントの中の各スロットは、必ずしも可能なすべての長方形を取る必要がなく、セグメントに組み合わされたすべてのスロットのみが、各長方形として考慮される必要があるのです。
長方形のリストを、セグメントサイズの長さに分けてみました。スロットに配される可能な長方形の数は、セグメントサイズのファクターによって少なくなります。
この問題についての評価は2つの方法で行ないました。解決方法の質と、解決方法を見つけるのに必要な時間と探索空間の評価の2通りです。
この種の問題では、最適解が得られたかどうかを計算より算出するのは不可能です。主観的に、得られた解の質を測ることができるだけです。
テストケースを使用して、与えられた材料の長さとスロットの数に対して、どこに良い解が存在したか、また多くの最適に近い解に対して、得られた解がどのように近いかを見ます。
8 X 16の材料に対して12スロットがどのように収まるかというテストケースを考えました。得られた結果は以下の通りです。
Ends [2,4,6,2,4,6,8,10,10,12,10,14,14,18,16,18] Max End 18 after 0.13 secs. Ends [2,4,6,2,4,6,8,10,12,14,8,12,16,14,17,17] Max End 17 after 2.35 secs. Ends [2,6,8,2,4,4,6,8,10,12,12,16,10,16,11,16] Max End 16 after 6.78 secs. Result placements :- (max end 16)
この結果はとても良い結果であるということができます。最初の解はすぐに得られていますし、最適化は改善され、6.78秒以内に、多くの最適に近い配置のうちの一つが得られています。
次に、8x128の材料に対して、112のスロットという条件での探索を実行してみました。
Ends [2,4,8,6,9,11,11, ... 127,128,130,132,130,130,132,132] Max End 132 after 10.3 secs. Result placements :- (max end 132)
最初の解はすぐに得られましたが、実行後最大130秒を経過するまで、それ以上の最適解は得られませんでした。
上は、100スロットでの問題で最大の探索空間の条件は、8MBで、Pentium90 PCでの測定結果です。
高度なプログラミング言語の柔軟さと組み込み型ソルバーの力の組合せにより、資源割り当て問題あるいはスケジューリング問題に対して、ソルバーに取り組むより問題自身に取り組むことが可能になります。
プログラマーは、問題の対象性に取り組みながら、制約の階層を作り上げることができます。このようにして増幅的に開発することにより、ソフトウェア開発サイクルを顕著に短くすることができます。というのは、個々の階層は、完全にテストすることができる小さなコードの固まりになるからです。
短いIF/Prologのプログラムであれば、より読みやすく、より保守しやすくなります、そしてこれを制約技術と組み合わせることにより、現実的な問題がより効果的に取り組むことができるようになります。