[ ホームページ ] [ 携帯用URL ]
DS 数学 BBS・2
小中高の範囲は DS 数学 BBS(携帯電話用)へ。
数学以外の話題は赤猫雑談掲示板で。
注意事項, 記号の書き方例をお読みになった上でご利用ください。

[ EZBBS.NET | 新規作成 | ランキング | オプション ]
iモード&(絵文字)、au対応!ケータイからも返信できる無料掲示板!
名前
 E-mail 
題名
内容

投稿KEY    タグ有効 改行有効 等幅フォント
URL
 
掲示板のTOP | 過去ログ集 | 投稿練習 | よく質問される問題 | エッセイblog



56783.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:初心者    日付:2018年06月06日(水) 05時44分
補足
私の理解している範囲でpdfでビンパッキング問題と列生成法について纏めました.
ご参考までにご利用ください.
https://drive.google.com/open?id=1aNZfpzfz8TblVB3Od0ckVqUJgdMWn6cn
0x8212.oit.ac.jp (150.89.130.18)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.62 Safari/537.36

56770.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:初心者    日付:2018年06月04日(月) 23時46分
補足
ビンパッキング問題の調査をしたところ,ビンパッキング問題のwiki(以下のURL)にて,解決致しました.時間があれば,こちらの方で纏めようと思います.
https://optimization.mccormick.northwestern.edu/index.php/Column_generation_algorithms
0x8212.oit.ac.jp (150.89.130.18)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.62 Safari/537.36

56710.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:初心者    日付:2018年06月01日(金) 09時54分
補足
双対問題における目的関数の変数y_i,_jは箱が使われているとき1そうでないときを0とする変数です.
また,主問題における目的関数の変数x_i,_jは箱にアイテムが使われているとき1,そうでないとき0を表しています.
0x8211.oit.ac.jp (150.89.130.17)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.62 Safari/537.36

56702.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:初心者    日付:2018年05月31日(木) 18時36分
返信遅れて申し訳ありません.ご回答ありがとうございます.
言葉の整理ができたため,非常に助かりました.ご助言ありがとうございます.

双対問題以降,どのような数値を扱っているのかが不明確なため具体的な説明ができない状況なので,自身の確認のために理解したことを補足していきます.
0x8211.oit.ac.jp (150.89.130.17)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.62 Safari/537.36

56687.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:らすかる    日付:2018年05月30日(水) 22時13分
具体的にどのようにしているのかがわからないと
どうなっているのかは誰にもわからない気がしますが、
とりあえず具体的な内容を聞いても私の手には負えそうに
ありませんので、他の回答者にお任せしたいと思います。

pl22290.ag0506.nttpc.ne.jp (124.154.44.18)
Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:60.0) Gecko/20100101 Firefox/60.0

56686.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:初心者    日付:2018年05月30日(水) 22時02分
回答ありがとうございます.
解を知りたいのではなく,ビンパッキング問題における列生成法を用いた際に,どのようにして解が選ばれていくのかの仕組みを理解したいです.
言葉足らずで申し訳ないです.

また補足ですが,列生成法の私が理解している大まかな流れを箇条書きで記述します.

1.定式化
2.x_i_jの取る値を0~1の実数に緩和
3.双対問題に変形
4.双対問題から最適解を求めてナップザック問題として処理
5.ナップザック問題の最適解が1より大きければ列を追加,なければ4が最適解
6.この辺りから挙動が不明

4番辺りから数字がどうなっているのか理解できていない状況です.

また,定式化した問題に対する双対問題の定式化を下記のリンクに載せておきます.
https://drive.google.com/open?id=1KdEFHb5G9mNJZds5eJGNPBvv5_YfjaVv
0x8211.oit.ac.jp (150.89.130.17)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.181 Safari/537.36

56685.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:らすかる    日付:2018年05月30日(水) 21時32分
条件を満たす解は72通りありますが、
72通りすべての数値を知りたいということですか?

pl22290.ag0506.nttpc.ne.jp (124.154.44.18)
Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:60.0) Gecko/20100101 Firefox/60.0

56681.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:初心者    日付:2018年05月30日(水) 20時27分
補足として
まずビンパッキング問題を下の設定した問題で変数を定義すると,

箱の容量をB = 8
アイテムの個数を I=4
箱の個数をJ=4
アイテム列の添え字をi∈I(アイテムの個数)
各アイテムの大きさを{s_1,s_2,s_3,_s_4} = {1,3,6,7}
箱の添え字をj∈J,J = 4(アイテムの個数)
アイテムi∈Iを箱j∈Jに詰めるとき1,そうでないとき0となる変数x_i_j
箱j∈Jが使われるとき1,そうでないとき0となる変数y_j


これを元に定式化した画像を以下に示します.
https://drive.google.com/open?id=1ixHznVidLTgdrav695JtbXutjonjbKLM
0x8211.oit.ac.jp (150.89.130.17)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.181 Safari/537.36

56679.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:初心者    日付:2018年05月30日(水) 20時03分
ご回答と誤植のご指摘ありがとうございます.
s_1の大きさは1です.また,考え方を知りたいためアイテムは4個だけです.
分かりにくくて申し訳ないです.
0x8211.oit.ac.jp (150.89.130.17)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.181 Safari/537.36

56675.Re: 組み合わせ問題(ビンパッキング問題)における列生成法  
名前:らすかる    日付:2018年05月30日(水) 19時10分
s_1の大きさがわかりません。
アイテムは4個だけですか?

pl22290.ag0506.nttpc.ne.jp (124.154.44.18)
Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:60.0) Gecko/20100101 Firefox/60.0

56674.組み合わせ問題(ビンパッキング問題)における列生成法  
名前:初心者    日付:2018年05月30日(水) 18時14分
お世話になります.
現在,ビンパッキング問題という組み合わせ最適化問題を解決する上で登場する列生成法を勉強しています.

無学のため勉強していて数式を眺めても,動きの正しさがわかりません.
そこで,質問なのですが,

問題の設定として,

アイテムが複数あって各アイテムの大きさがわかるとき,容量が一定の箱にアイテムを詰めていくときに箱の個数が最小になる組み合わせを選択する問題です.

以下の条件で実際の数値がどうなるのかを教えて頂けないでしょうか?よろしくお願い致します.

箱の容量 B = 8
アイテムの集合 I = {1,2,3,4}
アイテムの各大きさ s_1,s_2 = 3,s_3 =6,s_4 = 7

ご協力の程よろしくお願い致します.
0x8211.oit.ac.jp (150.89.130.17)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.181 Safari/537.36


「56674.組み合わせ問題(ビンパッキング問題)における列生成法」への返信

無料アクセス解析

アクセス解析の決定版!無料レンタルで最大100ページ解析!

特定の個人への誹謗中傷は無予告削除対象です。
   投稿KEY
   パスワード

EZBBS.NET produced by InsideWeb