Q&A
この部分がひっかけぽい’・Aの要素aに対して、それぞれ決まった1～10個の要素Bと対応付けが可能です。’可能であり、絶対ではない。
おそらく割当問題に属すると思う問題についてアドバイスを下さい
3375要素ある集合A、15要素ある集合Bがあります。
制約1
・集合Aの各要素をひとつの集合Bの要素に対応付けます。
制約2
・集合Bの各要素を225個の集合Aの要素と対応付けます。
制約3
・Aの要素aに対して、それぞれ決まった1～10個の要素Bと対応付けが可能です。
これらの制約を満たす対応付けが「存在するかどうか」を判定するアルゴリズムが欲しいと思っていますが、どなたか、解説ページ、教科書、ライブラリ等をご紹介頂ければ幸いです。ライブラリの場合、C++, R, pythonだと助かります。SIMPLEのように完全に商用の言語はごめんなさい（SIMPLEで可能なのは分かっています）。なお、実際に運用する際には、制約3が割と厳しめ（対応付け可能な要素の平均は2程度）なので、遺伝的アルゴリズムや乱択アルゴリズムなど、近似解を求めるタイプのアルゴリズムは不適合です。
組み合わせ最適化の問題としては基本的なものだと思いますが、生憎この分野には詳しくありませんので、よろしくお願いいたします。
----以下補足----
入力は、集合Ａ、集合Ｂ、制約３の対応付け可能な組み合わせの集合
（ただし、集合Ａ・集合Ｂは不変）
出力は、制約を満たす分類が可能か否かのBoolean
なお、3375=15^3, 225=15^2 です。
回答2件
0
自己解決
分かってみれば簡単な話、というかGLPKが便利すぎるだけですね。定数の書き方とか、GNU mathprogの習俗に合っているかどうかは自信がないので、もし突っ込みがあればよろしくお願いいたします。
GNU
1#------------------------------ 2# 集合の定義 3#------------------------------ 4param Suit := 15; 5param Capacity := 225; 6param NElement := Suit*Capacity; 7set A := 1..NElement; 8set B := 1..Suit; 9 10#------------------------------ 11# 変数の定義 12#------------------------------ 13var RESULT{A,B} binary; 14 15#------------------------------ 16# パラメータの定義 17#------------------------------ 18param PERMISSION{A,B} binary; 19 20#------------------------------ 21# 目的関数 22#------------------------------ 23minimize DEPARTURE: sum{i in A} (sum{j in B} (RESULT[i,j]*(1-PERMISSION[i,j])) ); 24 25#------------------------------ 26# 制約式 27#------------------------------ 28s.t. rule1{i in A}: sum{j in B} RESULT[i,j] =1; 29s.t. rule2{j in B}: sum{i in A} RESULT[i,j] =Capacity; 30 31#---------------------------------------- 32# データ 33#---------------------------------------- 34data; 35 36#------------------------------ 37# パラメータ 38#------------------------------ 39param PERMISSION := 40 #ここに、' 3 4 0'等という行が並ぶ。 41 #最初の数字が集合Aの要素番号、次が集合Bの要素番号、 42 #最後が0か1で、1なら「対応付け可能」 43; 44
投稿2016/11/17 05:53
編集2016/11/17 05:57
総合スコア55
0
’情報の追加・修正の依頼をする’にも記載しましたが、
条件を整理しないと回答しにくいと考えこちらに。
’制約1
・集合Aの各要素をひとつの集合Bの要素に対応付けます。 ’
つまり集合A（3375要素）は集合B（15要素）に分類できる。
’制約2
・集合Bの各要素を225個の集合Aの要素と対応付けます。
つまり集合BはAの225要素に対応。’ここ重要
制約3
・Aの要素aに対して、それぞれ決まった1～10個の要素Bと対応付けが可能です。
可能であり絶対ではないと定義。
つまりAの主要素aは要素Bに対して10程度までの対応で絶対条件ではない。
今ロジックを考査中です。
投稿2016/11/16 10:30
総合スコア3747
ありがとうございます。
せっかくなので補足します。数学的な意味はないので省略しましたが。実際には、集合Aの3375要素と集合Bの225要素は常に不変で、様々な制約3の「対応付け可能な組み合わせ」を入力として、分類可能かどうかのBooleanを返すような使い方を想定しています。
ミスです。
集合Bの15要素
でした。
ありがとうございます’実際には、集合Aの3375要素と集合Bの225要素は常に不変で’これが重要ですよ。
集合Bが１５要素ですね。了解しました。わくわくする質問ありがとうございます。
こちらこそお時間を割いて頂きありがとうございます。問題のモデル化そのものは得意なのでだいぶ純粋な問題に還元できたとは思いますが、ここまで来て自分の不得意分野であると分かってしまったので、困り果てていた次第です。
情報の追加・修正依頼でも記載しましたが、制約３の集合Aのaの対応づけが、どのように作用するかも気になります。
Rで線形計画法での解法かな？
たとえば、単純化した例を示します。集合Bを色だとします。赤・白・青・黄があり、それぞれの色の箱に3つずつ国旗を入れます。国旗が12種類あって、日の丸なら赤の箱か白の箱に、ユニオンジャックなら青か白か赤か黄のどれにも入れられます。フランスの三色旗なら青か白か赤です。このルールが制約３です。実際に近い問題では、とはいえこれも実際の問題ではなくたとえ話ですが、寒色の箱、暖色の箱などと、もう一段抽象化された箱が集合Bなので、その抽象化の仕方を様々に変えて、どの抽象化のルールならば分類が成り立つかを求める、というのが最終的な使い方になります。
ご指摘の通り、Rが向いていそうではあります。
先ほどの例では、国旗が集合Aです。
では集合についてさらに要素を分解する方法で考えましょう。例えば国旗の場合では’色’の要素を使う？とか。（例としてなので要素がどのように分類できるか）を考慮すると線形計画法が適用できそうですね。
そうですね。とりあえず。GLPKで解くことにします。C++から呼べるようにすると使いやすそうなので。問題は明確なので、あとはGNU Mathprogでちゃんと書けるように練習するだけ...
バイナリ変数を使った分かりやすい例はあまり見つかりませんでしたが
http://yamaimo.hatenablog.jp/entry/2015/07/17/200000
を参考にしつつ、汚くて良ければ書けそうです。ありがとうございます。
参考のページを今見ています。制約の条件の適用に関してはちょっと力仕事ですね。
はい、そこが悩み所です。制約の条件が「式」として入ってしまうので。
をなんとかパラメトライズして「データ」にしたいと思って色々と
試行錯誤しています。とっかかりは掴めたものの、ちょっと骨が折れますし、
制約３を変えて回す、というのに適さない形になりますね。
再び悩んでいます。mathprogジェネレータ、という解は、いやですね。
×をなんとか
○それをなんとか
解決しました。自己解決を投稿しましたが、MasahikoHirataさんの助言に負う所は大きいです。ありがとうございます。
あなたの回答
tips
プレビュー
