Category Archives: 制約論理プログラミング

ECLiPSe CLPで美術館の警備員配置問題を解く

ECLiPSe CLPで以下の美術館の警備員配置問題を解きます。

問題(Problems and exercises in Operations Researchの4.7 Museum Guards):

以下のような部屋構成の美術館に警備員を配置せよ。
OR_4_7easy
条件:
・コスト削減のため警備員は各部屋をつなぐドアの位置に配置し2つの部屋を同時に警備する。
・どの部屋も少なくとも1人の警備員が見張っているようにする。
・上記条件を満たしつつ、なるべく少ない警備員で警備する。

プログラム:

実行結果:

解答配置(の一つ)
OR_4_7easy_ans

解説:
まず部屋をノード、ドアをエッジと考えたグラフを作成し、エッジごとに警備員がいるかいないかを表す変数を宣言します。警備員がいれば1、いなければ0。

Nodesに全部屋のリストを用意しておいて(20行目)、
それをひとつづつ指定したループを処理します(25行目)
ループ中ではエッジ配列の中で指定した部屋を持つものを探し、警備員有無の変数をすべて足し合わせます(29行目からのループ)。ある部屋に注目したとき、そのすべてのドアに対応する警備員変数を足し合わせた式を作ります。少なくとも1つのドアには警備員がいるはずなのでこの式に「1以上」の制約をつけます(40行目)

警備員の数を最小にするのが目標なので警備員有無変数の配列Varsの合計が最小になるように指定し分枝限定法(branch_and_bound)を用いてVarsの値を求めます。
実行結果を見るとわかる通り、最小コストは6で、7つの解があるようです。

もう一つ、以下のもっと複雑な部屋割りの場合も解いてみます。
OR4_7difficult

プログラム:

実行結果:

解答配置(の一つ)
OR_4_7difficult_ans

最小コストは14、全部で27通りの解があるようです。

PrologのLogical Loopの解説

ECLiPSe CLPでソルバーを作るときに欠かせないLogical Loopの説明をしたいと思います。

Prologでプログラムを書いたことがない人は信じられないと思いますが、なんとPure Prologには繰り返し処理を書くための構文がなくて、ループごとに再帰処理を使った述語を定義して繰り返し処理を行います。

例えばLstというリストに入っている要素をすべて表示するという処理を書きたい場合、以下のようにdsp_lst/1という術語を定義して繰り返しを書いて行います:

実行結果:

このように繰り返しの為だけに定義した述語をauxiliary predicate(補助述語)と呼ぶようです。よくPrologのコードで出てくるのですが、述語名のうしろにアンダーバーとかを1つつけて、ループ用の補助述語を定義したりします。

上記かなり愚かしい仕様に思えますが、恐らく以下のような理由からだと推測します。
①Prologの述語は本来「動作」「処理」ではなく、引数同士の「関係」を記述するためのもの(関数ではなく述語と呼ぶゆえん。一階述語論理の述語)
②例えば以下のような述語があった場合、

term1~term3のそれぞれの引数同士の関係が「すべて」成り立つとき、pred(A,B,C)が真となる。本来カンマは「処理の区切り」ではなく「複数の述語どうしを結ぶ条件の&」を表すという原則がある(orは;もしくは同名の別の述語定義)。極論を言えばterm1からterm3の順番をバラバラにしても成り立つはず(実際は大いに記述の順番に依存しますが…理想とする姿がそこという意味)、単純に複数の述語を&で結んだものに過ぎないので繰り返しとかいう概念がそもそもない。

(余談ですが制約論理プログラミングの制約「のみ」で書かれた述語は述語内の制約の順番をバラバラに並び替えても基本的に問題なく動作します。Prologの理想に近い)

このような仕様に一石を投じたのがECLiPSe CLPのメイン開発者のJoachim Schimpfさんの書いた以下の論文です。
Logical Loops
この論文によってPrologに自然な形でのループ処理の記述方法が提示され、ECLiPSeやSicstus Prologなどで採用されています。

Logical Loopの書き方は、上記の補助述語でループを書いていた人に自然に受け入れられるような仕様となっています。逆にPrologで補助述語を使ったループを書いたことがない人は使いこなすまで時間がかかるかもしれません。再帰を使用してループを記述することに慣れている必要があります。

例えば上記のLstというリスト内の文字をすべて表示するプログラムをLogical Loopで書くと、以下のようになります。

上記のように
1.fromtoなどの繰り返し制御用の記述
2.do
3.(繰り返す処理)

の3つの部分を書きます。
補助述語との比較で理解すると良いのですが、
「1.fromtoなどの繰り返し制御用の記述」→述語の引数の部分
「3.繰り返す処理」→述語の内部の処理
となります。
補助述語の書き方をそのまま置き換えたような扱いなので、「繰り返す処理」の部分は別述語のように独立となっていて、ループの外で使われている変数などは明示的に指定しない限り一切使用することはできません。使いたい場合はparamという構文を使用して引数として渡す(後述)必要があります。

fromtoの4つの引数の意味は(First,In,Out,Last)となっていて、やはり補助述語と関連付けて理解すると良いのですが
In→補助述語の引数
Out→補助述語内で再帰呼び出しする際に指定する引数
Last→補助述語の引数がこの値でコールされたらループ終了
という感じです。
一番初めに補助述語をコールする際に指定する引数がFirstとなります。

駆け足になりますがfromto以外で使用できる構文を列挙していきます。これらを複数同時に指定することもできます。

foreach(X,List)
リストList内の要素が順にXに設定され処理が繰り返されます。リストを生成することもできます。Xはループ内局所変数です。

foreacharg(X,StructOrArray)
StructOrArrayの部分はECLiPseのArray([](1,2,3,4)みたいな記述)や複合項 fukugoukou(1,2,3,4) を指定します。
最初の引数から順にXに設定され処理が繰り返されます。termを生成するためには使用できません。Xはループ内局所変数です。

foreacharg(X,StructOrArray,Idx)
引数が2個のものと同じ動きですがIdxに何番目の要素がXに入っているかの数字が入ります(arg(Idx,StructOrArray,X)がtrueとなる)。XとIdxはループ内局所変数です。

foreachelem(X,Array)
foreachargと同じ動きですが2次元配列などでも対応しますArray=[]([](1,2,3),[](4,5,6))などの場合Xに1,2,3,4,5,6が順に設定される。Xはループ内局所変数です。Arrayを生成するためには使用できません。

foreachelem(X,Array,Idx)
引数2個バージョンと同じ動きですがIdxにインデックス位置が設定されます。XとIdxはループ内局所変数です。

foreachindex(Idx,Array)
foreachelemと同じ動きですがXがなくIdxのみ設定されます。Idxはループ内局所変数です。

for(I,MinExpr,MaxExpr)
C言語などのfor(I=MinExpr;I<=MaxExpr;I++)と同じ動き。MaxExprは必ず値を設定しておく必要あり。Iはループ内局所変数です。

for(I,MinExpr,MaxExpr,Increment)
引数3個バージョンと同じ動きだがIncrementで何個づつIが増えるかを設定可能

multifor(List,MinList,MaxList)
for/3と同じだがIに相当する変数をリストとして複数設定する。MinListとMaxListも対応する下限上限をリストで設定する。
Listはループ内局所変数

multifor(List,MinList,MaxList,IncrementList)
引数3つバージョンと同じだがIncrementListに増加分を設定できる

count(I,Min,Max)
forと同じのようだがMaxは値設定しなくてOK。ループ終了後にカウントした値など把握できる。

param(Var1,Var2,…)
ループ内で使用したい変数を指定する。ここで指定しない限りループの外で使用している変数など使用できない。
補助述語に引数として渡すイメージ。

loop_name(Name)
デバッグ用にループの名前を付けることができる。補助述語の名前のようなイメージ。他の述語と重複する名前は許されない。

最後に、先ほど「fromtoなどの記述は複数記述できる」と書いたのですが、これが面白くて、例えばリストを生成する用途で使用したりなどもできます。

リストList=[1,2,3,4,5]があったとして、ListSqにそれぞれの要素を2乗したリストを設定するようなプログラムを書いてみます。

実行結果:

上記動作もfromtoの各引数に関して「補助述語に引数として渡している」イメージを持つと何が起こっているのかわかるのではないかと思います。

以下のような補助述語が生成されてると考えると良いと思います!

ECLiPSe CLPで輸送問題を解く

ECLiPSe CLPで以下の輸送問題を解きます。

問題(Problems and exercises in Operations Research 21ページ 4.5 Transportation ):
イタリアの運送会社は、6つの店舗(Verona,Perugia,Rome,Pescara,Taranto,Lamezia)から5つの港(Genoa,Venice,Ancona,Naples,Bari)に空のコンテナを運ばなくてはならない。

6つの店舗が持っている空のコンテナの数は以下:
4_5empty_containers

5つの港がそれぞれ求めているコンテナの数は以下:
4_5container_demand

コンテナはトラックで送られるが、各トラックは最大で2個のコンテナしか運べない。
また、輸送距離1kmあたり30ユーロのコストがかかる。
各店舗から各港までの距離は以下の通り:
4_5distance

コストが最小となるような輸送計画をもとめよ。

プログラム:

実行結果:

解答を整理すると以下となります。
4_5solution

解説:
EPLexライブラリを用いて解きました。

実は、これとほぼ同じ種類の問題がECLiPSeのTutorialにもあります(EPLexライブラリの解説の章の16.1.3 Example formulation of an MP Problem)
この問題との違いはトラック1つにつきコンテナ2つを運ぶという点だけです。

解説します。運ぶコンテナの数と実際にそれを運ぶトラックの数とを分けて考えることにします。
コンテナの数の配列をAryC、トラックの数をAryLとします。
CostConstantに輸送コストを設定しておきます(8行目)
コンテナの数、トラックの数には 0以上であること、整数であることという制約をつけます(17,18行目)
21行目からはコストの目的関数を生成してます。これを最小にするのが目標となります。この処理を抜けた段階で「WholeCost=コスト関数」の式が得られていて、これを後ほど最小化するようにEPLexに設定します(60行目)
31行目からは各店舗から送られるコンテナ数の上限が持っているコンテナ数であるという制約をつけています。
41行目からは各港に届くコンテナが要望以上であることを示す制約をつけています。
53行目からはコンテナとトラックの個数の関係の制約をつけています(各店舗-港間で移動するコンテナ数<=トラック数*2)
60行目で最適化するコスト関数を設定しています。
61行目でEPLexに問題を解くよう指示しています。
62行目からは、AryCとAryLの変数がまだEPLexの範囲用の値を持っているのを、解いた答えの値へ変更しています。

ECLiPSe でユーザー定義の算術演算子を定義する

ECLiPSe CLPでユーザー定義の算術演算子を定義して is で計算してもらえるようにする方法です。

ちなみにisで既定で計算対象となる述語は ここ を参照してください。

ここでは演算子の右と左の数字を直角三角形の高さと幅として、斜辺の長さを計算してくれる my_opという演算子を定義して実際に使ってます。
プログラム:

実行結果:

演算子の木構造や優先度に関しては以下の記事など参考になります。
[PROLOG] compound term
[Prolog]演算子のカンマとそうでないカンマ、ドット演算子と演算子でないドット(ピリオド)

opのyfxは3つ以上数字がある場合に木構造が左に伸びてくか右に伸びてくかを決定する部分で、
例えば引き算で 6 – 2 -1 と記述した場合、
(6-2)-1 なのか
6-(2-1) なのかで答え変わってきますが、想定しているのは前者です。
このような演算子は yfxで定義します。

200の数字は演算子の優先順位です。200はECLiPSeでは+や-と同じ優先度です。小さいほど優先度が高い。ここは深く考えないでこの数字にしてしまいましたがちゃんと使う場合はまじめな検討が必要です。current_op/3という術語で演算子の優先度や結合の情報(yfxなど)が確認できます。

SWI-PROLOGでも多分同様のことできるとは思うのですが、やり方わかりませんでした。情報求ム。

ECLiPSe CLPで最小全域木を求める

ECLiPSe CLPで以下の問題を解くプログラムを書く方法を説明します。

問題(Problems and exercises in Operations Research 19ページ 4.1 Compact storage of similar sequences

DNAマッピングプロセスの際には、非常に長い同じ長さ&ほとんど同じ並びのDNA配列をコンパクトに保存するという問題に良く遭遇する。
ここでは問題を単純化するためDNA配列を0と1の配列と仮定する。2つのビット列をそれぞれA[i]、B[i]の配列として表現したとき、これらのハミング距離は「|A[i]-B[i]|のビット列全体での総和」で定義される(= 同じ位置のビットが異なる箇所の総数)
以下の6つのビット列のそれぞれのハミング距離は以下となる(問題からコピー)
OR_Excercise_4_1

ハミング距離が大きすぎなければ、1つの完全なビット列のみストレージに記憶し、残りはそのビット列からの派生として差分のみ保存するという方法を採用できる。
上記を実現するため、全ビット列を表現するために最小の差分となるような全域木を求めよ。

解説:
いきなりDNAとか出てきてびっくりしてしまいますが、少し考えると全ノード(ビット列)が接続されたグラフがあり、ノードを結ぶそれぞれのエッジの距離がハミング距離であるグラフを考え、その最小全域木を求める問題ということがわかります。
最小全域木を求めるためにはgraph_algorithmsライブラリ
minimum_spanning_tree/4 という術語を使用します。

minimum_spanning_tree(+Graph, +DistanceArg, -Tree, -TreeWeight) の引数の説明
Graph:グラフ
DistanceArg:エッジ e(_,_,Distance) の Distanceの部分に数字で距離を設定する場合は0を指定
Tree:求められた最小全域木(エッジのリスト)。戻り値
TreeWeight:求められた最小全域木の総コスト。戻り値

実行結果

以下のような全域木となることがわかります(解答からコピー)
OR_Excercise_4_1_2

ECLiPSeで分枝限定法(branch and bound)ライブラリを用いてナップサック問題を解く

ECLiPSe CLPを用いて以下のナップサック問題を解きます。
Example の Knapsack のページ を参考にしてプログラムを作成しました。

問題(Problems and exercises in Operations Research の 18ページ 3.5 Knapsack Branch and Bound ):

投資銀行の総予算は1400万ユーロで、4種類の投資が可能です。次の表は、投資額(Amount)と各投資による純収入(Net revenue)を示しています(単位は百万ユーロ)。投資を行う場合は、各投資を全額行う必要があります。総純収入を最大化する投資方法を答えよ。
OR_excercises_3_5

この問題文だけでは読み取れなかったのですが、解答を見ると4種類の投資は「投資しない/1個口のみ投資する」の2択らしく、同じ投資を2個以上するのは禁止のようです。

解き方:
「制約を満たす」だけではなく「利益を最大化する」「コストを最小化する」解を求める際は分枝限定法(branch_and_bound)ライブラリを使用します。

分枝限定法の厳密な定義やアルゴリズムに関しては他のページや書籍を参考にしてください。
ECLiPSe CLPのbranch and bound ライブラリでは以下の手順でコストを最小化する解を得ます。
1.コスト以外の制約を満たす解を得ます。
2.その時のコストを計算します。計算したコスト=Aとします。
3.新たな制約「コストがA未満であること」を追加して、解を得ます。
4.上記操作を繰り返して解が得られなくなったら、直前に計算したコストが最小コストの解となります。

プログラム:

解説:
6行目でValuesに[投資1,投資2,投資3,投資4]のそれぞれの投資数(0 or 1)の制約を設定しています。Valuesの個々の要素が確保されているのもこの部分ですが、動作に関してfor系の説明をしなくてはなりません。いつか改めて記事書きます。

13行目の述語solve内にある16行目の minimize/2 で分枝限定法を行っていて、繰り返し実行するgoal(この例ではsearch/6)と、コスト計算結果が入る変数(この例ではCost)を指定すると、先ほど解説した1~4の一連の動作を自動で行ってくれます。minimizeではCostを最小化する解を得ます(問題文が利益最大化を目指すものなので15行目でコスト変数への代入時に符号を逆転してます)

16行目のsearch/6の引数のうち、いくつかを説明します。
第三引数(largest): 制約変数のリストのどの変数から値を設定していくかを決める際、「一番大きい数値をドメインに持つ変数」から決定していきます(すべての変数のドメインが0 or 1なのでこのケースでは意味ないです。コピペしてきたので…)
第四引数(indomain_reverse_split) :制約変数に値を設定していくときの順番ですが、「ドメイン内の一番大きいものから降順に」値を設定していきます(このケースでは1を設定して、そのあと0を設定する)
第五引数(complete) :もれなくすべての選択肢を試します(オプションで端折るものがあります)

実行結果:

6行目からのFound a solution with cost ~ の部分で繰り返しコストの条件を厳しくしながらサーチしているのがわかります。
Valuesを見ると2,3,4番目の投資を行うと最大利益42を得られるようです。

上記の問題を「0/1個口の投資」ではなく「0 ~ N個口の投資を行う」という条件に変更した際の解をサーチするプログラムもついでに掲載します。
プログラム:

7行目のところが変更部分ですが、// Amountの「//」はコメントではなくて演算子で、 「Capacity / Amount の整数部分」を計算します。

実行結果:

やはり解は変わり、44が最大利益となり、1番目の投資先に2個、3番目の投資先に1個投資するのが一番利益が高くなるようです。

ついでに、ネットで見かけた複雑そうな30個の荷物の0-1ナップサック問題を解いてみました(プログラムは前半で掲載したもの使いました)
実行結果:

自分のマシン(Intel(R) Core(TM) i5-3340M CPU @ 2.70GHz 2.70 GHz メモリ8GB しょぼめのノートPC)では36msecで解けていました。

Example の Knapsack のページ を見ると、0/1のナップサック問題(上記の0個/1個口の投資しか許されない問題)の場合には別の解き方を行っていたり、EPLEXライブラリを使用した書き方もできることがわかります。また、ナップサック問題は分枝限定法ではなく動的計画法を用いて解くのもメジャーな解き方のようです。

ECLiPSe CLPのsearch/6のChoiceの実験

ECLiPSe CLPで記述するソルバーの構成はおおまかに以下の部分に分かれます。
1.制約の記述
2.解のサーチ
3.解の表示

2.の解のサーチというのは、具体的には以下の2つのループの入れ子の構造となります。
 ループ1:複数の制約変数の中から1つを選択する
 ループ2:変数にドメイン内の値を一つ割り当てる

このとき、ループ1で「どのような順番で変数を選択するか」ループ2で「どのような順番で値を決定するか」という2つの制御をおこなうことができます。この記事はループ2の値決定の順番をいろいろ試す記事となります。

ECLiPSe CLPではループ1,ループ2は例えば以下のような方法で記述可能です(他にもあると思いますが)
labeling/1を使用
 ループ1:リストの先頭の変数から選択
 ループ2:ドメイン内の数値の小さい値から大きい値へと順に値を決定
search/6を使用(ループ1、ループ2の制御を一括で指定)
・以下の2つの述語を使用
 ループ1:delete/5を使用して値を決める変数を決定
 ループ2:indomain/2を使用してどのように変数に値を設定するかを決定

本記事ではsearch/6に関して、「どのような順で変数に値を割り当てるか」というのをオプションを変えながら実験したいと思います。

以下のテスト用プログラムで実験します。

Choice の部分を色々変更することにより実験します。解説の部分は直訳なので自分でも意味わかってない箇所あります。特に「テストされた値を削除」「ドメイン分割」のところが良くわかってません。誰か教えて下さい。

①indomain
組み込みのindomain/1を使用します。値は昇順で試行されます。失敗しても以前にテストされた値は削除されません。

②indomain_min
昇順で試行されます。失敗すると以前にテストされた値が削除されます。値はindomainの場合と同じ順序でテストされますが、バックトラックがより早く発生する可能性があります。

③indomain_max
値は降順で試行されます。 失敗すると以前にテストされた値が削除されます。

④indomain_reverse_min
indomain_minと同様ですが、選択は逆の順序で試行されます。つまり最小の値が最初にドメインから削除され、それが失敗した場合にのみ、値が割り当てられます。

⑤indomain_reverse_max
indomain_maxと同様ですが、選択は逆の順序で試行されます。 つまり、最大値が最初にドメインから削除され、それが失敗した場合にのみ、値が割り当てられます。

⑥indomain_middle
値はドメインの中央から開始して試行されます。 失敗すると以前にテストされた値が削除されます。

⑦indomain_median
値はドメインの中央値から開始して試行されます。 失敗すると以前にテストされた値が削除されます。

⑧indomain_split
ドメインの下半分を最初に試行して、連続するドメイン分割によって試行されます。 失敗すると、試行された間隔が削除されます。 これは、indomainまたはindomain_minと同じ順序で値を列挙しますが、それより早く失敗する可能性があります(注:解サーチ時はなるべく早く失敗したほうが処理時間が速くなる。早く失敗≒変数の決定の入れ子のループのより外側のループ回数が減ることと同等)

⑨indomain_reverse_split
ドメインの上半分を最初に試行して、連続するドメイン分割によって試行されます。 失敗すると、試行された間隔が削除されます。 これは、indomain_maxと同じ順序で値を列挙しますが、それより早く失敗する可能性があります。

⑩indomain_random
値はランダムな順序で試行されます。 バックトラック時に、以前に試行された値が削除されます。 このルーチンを使用すると、別の呼び出しで異なる順序で乱数が作成されるため、再現性のない結果が生じる可能性があります。 この方法では、組み込みのrandom / 1を使用して乱数を作成し、seed / 1を使用して別の実行で同じ番号生成シーケンスを強制することができます。

⑪indomain_interval
ドメインが複数の間隔で構成されている場合は、最初に間隔の選択で分岐します。 1つの間隔では、ドメイン分割を使用します。

ECLiPSe CLP の EPLEX ライブラリを用いて混合整数線形計画問題を解く

ECLiPSe CLPのEPLEXライブラリを使用して混合整数線形計画問題を解きます。

混合整数計画問題とは、線形計画問題の変数のすべてもしくは一部が整数という条件がついた問題です。

Problems and exercises in Operations Research の 3.2 Gomory cutsの問題を解きます。

OR_excersize_3_2
ほぼ線形計画問題と同じですが、x(x1とx2)に整数であるという条件がついています。

線形計画法の時と比べたプログラムの書き方の違いなのですがなんと整数の制約を持つ変数にintegers制約を追加するだけでできてしまいます。(下記のプログラムの13行目)
線形計画問題と混合整数計画問題の解き方の違いとして、混合整数計画問題のほうは分枝限定法を使用したり複雑な方法になるのですが、それらはライブラリの中で行ってくれるため使用する側はほとんど手間が変わりません。

プログラム:

実行結果:

X1 = 1
X2 = 2
が解答です。かなり便利です!

ECLiPSe CLP の EPLEX ライブラリを用いて線形計画法の問題を解く

ECLiPSe CLPのEPLEXライブラリを用いて線形計画法の問題を解く方法を説明します。

EPLEXは外部の数理計画法(Mathematical Programming)ソルバーで、線形計画法(Linear Programming = LP)や混合整数計画法(Mixed Integer Programming = MIP)の問題を解くことができます。

線形計画法とは複数の変数に1次方程式・1次不等式で記述されたいくつかの制約があるときに、目的関数(これも一次式)を最大化もしくは最小化する解を得るためのアルゴリズムです。

混合整数計画法は線形計画法の変数の一部もしくは全部が「整数である」という制約を持つ問題です(こっちのほうが難しいようです)

EPLEXライブラリに関してはTutorial の Chapter 16 The Eplex Libraryに使用方法が書いてあります。EPLEXはECLiPSe CLPのネイティブなライブラリではなく、外部(サードパーティ)のソルバーです。Eplexライブラリを用いることにより他のネイティブなライブラリと同じように使用可能です。また、ECLiPSe CLPをインストールした際に自動的にインストールされるので、特に設定の必要はなく初めから使えます。

世に線形計画法のソルバーはたくさんあるので、別にECLiPSe CLPを使用しなくてもよいのですが、ECLiPSeを使えば他の便利な制約論理プログラミングの制約が同時に使用できるので、のちのち良いことがあると思います。

問題は Problems and exercises in Operations Research の Chapter 2 Linear programming 2.1 Graphical solutionを解いてみます。

問題①
OR_excersize_2_1
Tは転置行列です。
cx = 16*X1 + 25*X2 を最小にするような X1, X2の値を求めよという問題です。

プログラム:

実行結果:

解説:
ほとんどそのまま制約を書いてあるだけですが、ポイントは
①2行目、eplex_instance()でprobという名前のインスタンスを設定し、EPLEXの機能を使うときはそのインスタンスを指定する。
②17行目、eplex_solver_setupで目的関数の設定を行う
③実行結果のX1{0.0 .. 1.7976931348623157e+308 @ 4.2857142857142856}の部分は 変数名{最小値..最大値 @ 解} の意味
くらいです。あとは見ればわかると思います。

問題②:
OR_excersize_2_2

プログラム:

実行結果:

問題③
OR_excersize_2_3

プログラム:

実行結果:

カンタンですね!

機械の買い替え問題(Renewal Plan Problem)を解くプログラム

ECLiPSe CLPで機械の買い換え問題(Problems and exercises in Operations Researchの1.5 Renewal plan)を解くプログラムの説明をします。

問題:
ある会社が12000ユーロの機械を購入し使用しています。機械には毎年維持費(costs)がかかります(維持費は年々上がっていきます)。
使用中の機械は中古で販売(gain)し新しく買いなおすこともできます(中古機械の販売価格は年々下がっていきます)
維持費と中古機械の販売価格は以下の表のとおりになっています(1keuroは1000ユーロ)。
5年間の総運用コストを最小限に抑える機械の買い換え計画を決定しなさい。

OR_Excercise_1_5_1

行間を読むとこの問題は機械の生産する利益に関しては触れられていないのでこれは毎年一定で考慮する必要なしということのようです。

難しくて解けなかったので答えと解説を見ました。説明します。
「i年目に購入した機械をj年目まで使用し、買い替えたときのコスト」をCijという変数で表し、1~6年目時点を表す6つのノードがCijで結ばれた有向グラフを考える(6は5年間の期限終了時を表す)
Cijの計算方法は以下となります。

Cij = 12000 + [(j-i)年間にかかった維持費] – [(j-i)年使用した機械の中古販売価格]

たとえば 2年目に購入した機械を4年目まで使用し買い替えたコストだと
C24 = 12000 + (2000+4000) – 6000 = 12000
となります。これはノード2とノード4を結ぶエッジとなります。
そのように計算した有向グラフは以下のようになります(回答からコピー)

OR_Excercise_1_5_2

このようなグラフの、ノード1からノード6へ至る最小コストの経路が答えとなります。

single_pair_short_path/6を使用すると、最小コストの経路をすべて取得できます。

single_pair_short_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Tolerance, -Path)
 +Tolerance を 0にするとすべての最小コストの経路が取得され、当然それらのコストはみな同じとなります。
 +Tolerance に0より大きい数値を設定すると、最小+その値 までのコストの経路も抽出されるようです。

プログラム

実行結果:

コストは31(=31000ユーロ)が最小で、以下の買い換え計画があるようです。
3年目と5年目で買い替える
3年目と4年目で買い替える
2年目と4年目で買い替える