[PR]当サイトはアフィリエイト広告を利用しています。
今回はエクセルソルバーで組み合わせ最適化問題を解いてみます。
組み合わせ最適化問題は基本的に変数が離散変数になるので、求解が難しい問題となります。離散変数か連続変数かという最適化問題の分類については以下で網羅的に解説しました。
とはいえ組み合わせ最適化問題は色々な場面で出現します。儲けを最大にする商品の選びかた、コストを最小にする出店計画、巡回セールスマン問題など様々な問題が組み合わせ最適化問題として研究されています。
今回は組み合わせ最適化問題の定義や例を示した後、実際に簡単な例題で組み合わせ最適化問題をソルバーで解いてみます。
組み合わせ最適化問題に関する理解が深まりましたら幸いです。
組み合わせ最適化問題とは
組み合わせ最適化問題を抽象的な言葉で表すと次のようになります。
事象の集合E、条件、Eの組み合わせに対する評価値が与えられたとき、条件を満たすEの組み合わせの中で、評価値が最大あるいは最小になるものを見つける問題
これだけでは意味がわかりません。具体的な例でこれから解説していきます。
遠足に持っていくお菓子の選び方【ナップサック問題】
次のような問題はナップサック問題と呼ばれ、組み合わせ最適化の一例としてよく解説されます。
遠足に行くときにお菓子を持っていくことになった。お菓子の条件は合計1000円までと決められている。お菓子の候補は以下となる。各お菓子には満足度が存在する。このとき条件を満たしつつ、お菓子の満足度の合計が最大になる組み合わせを求めなさい。
| お菓子 | 金額 | 満足度 |
| 1.チョコクッキー | 250円 | 2 |
| 2.ポテトチップス | 200円 | 3.5 |
| 3.チョコレート | 150円 | 2 |
| 4.フィナンシェ | 300円 | 3 |
| 5.どら焼き | 300円 | 1 |
例えば、上の問題でお菓子として（1,4,5）を選択すると、チョコクッキー、フィナンシェ、どら焼きを選択したことになり、合計金額は（250+300+300=850円）、満足度の合計は（2+3+1=6）となります。
これを最適化問題として数式化すると次のようになります。
- 目的関数： \(2x_{1}+3.5x_{2}+2x_{3}+3x_{4}+1x_{5}\)→最大化
- 制約条件：\(250x_{1}+200x_{2}+150x_{3}+300x_{4}+300x_{5}\leq 1000\)
- 変数：\(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\)は0か1
上の組み合わせ最適化問題の定義に当てはめてみると、事象の集合が「\(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\)」すなわち選択するお菓子となり、条件が「お菓子の合計は1000円以下」となり、組み合わせに対する評価値が「満足度の合計」となります。
組み合わせ最適化問題が他の最適化問題と大きく異なる点は、事象が「あるか無いか」という変数の二値問題となっていて、基本的に離散変数に対する最適化が必要になる点です。
しかしながら組み合わせを求める問題ではよく現れます。
上のお菓子の選び方の問題では変数、制約条件、目的関数すべてが線形なので、線形計画法、エクセルソルバーではシンプレックスLPで求解できます。
ただしあらゆる組み合わせ最適化問題が線形最適化問題になるとは限らないので、問題が最適化問題のどの分類に入るか見極めることが大切です。最適化問題の分類は以下の記事で解説しています。
組み合わせ最適化問題と相性のよい最適化手法の一つは遺伝的アルゴリズムです。遺伝的アルゴリズムを組み合わせ最適化問題の求解に利用した活用例についてまとめた以下の記事もご覧頂けましたら幸いです。
実際にエクセルソルバーで解いてみる
それでは実際にエクセルソルバーで上のナップサック問題を解いてみましょう。エクセルに次のように入力します。
各セルには次のように入力します。
- x1,x2,x3,x4,x5：0
- G3：=250*B3+200*C3+150*D3+300*E3+300*F3
- H3：=2*B3+3.5*C3+2*D3+3*E3+1*F3
ソルバー設定画面で次のように入力します。ソルバーアドインの使い方については以下の記事をご覧ください。
制約条件に見慣れない「バイナリ」という項目があります。これは変数が0か1かという状態を表します。条件追加ダイアログでは次のように設定します。制約条件の記号を選択するときに「bin」を選択します。
解決ボタンを押すと次のようになります。
思ったよりお菓子をたくさん持って行けそうですね。
上の問題は暗算でも解けるような問題ですが、お菓子の種類が増え、値段だけではなく、重さや容量の制約などが増えると、暗算では求めることが困難になっていきます。
そうした複雑な組み合わせを自動的に求めようと考えるのが組み合わせ最適化問題なのです。
組み合わせ最適化問題はなぜ難しいのか
この節では組み合わせ最適化問題がなぜ難しいのかという話題を解説します。
離散変数を扱うから
上の例で扱ったように、組み合わせ最適化問題は何らかの事象が「あるか無いか」という二値問題になり、離散変数問題となってしまうため、ソルバーでは苦手な分類となってしまうという点が挙げられます。
最適化手法のソルバーは特にGRG非線形において目的関数の微分した値をもとに変数の空間を移動しながら求解します。
目的関数がなめらかなら微分して最適解の近くの離散値を選択することもできますが、それが最適解という保証はないので完全な決め手はありません。
シンプレックスLPの中身であるシンプレックス法も基本的に離散変数は苦手です。中途半端な位置にある整数をうまく比較する方法がなかなか無いからでしょうね。
もちろんエクセルのソルバーは高度な技術が搭載されているので離散変数も解ける場合もあります。上の例ではシンプレックスLPで離散変数であるバイナリの変数でも解けました。
これはエクセルソルバーのシンプレックスLPがすごいのであって、一般的な線形計画法のテキスト通りに簡単な線形計画法ソルバーを自作したりするレベルではとうていバイナリ変数は解けません。
ではエボリューショナリーで解けばよいと考えるかもしれませんが、エボリューショナリーで100変数くらいの多変数問題を解こうとすると、原理的に最適解が求まりにくいという弱点があります。解空間が広大になると、それだけ探索範囲が雪だるま式に増えていき、探索が追い付かなくなるのです。
そもそも最適化問題のモデル化に決まった手順が存在しないから
例えば組み合わせ最適化に関する理論集である以下の書籍では次のように述べられています。
実際的な問題を抽象的な組合せ最適化問題としてどのようにモデル化するかについては, 本書では取り上げない. 実際, そのようなことを可能にする一般的な方法はないからである.
B. コルテ, J. フィーゲン, 浅野孝夫 訳, 浅野泰仁 訳, 小野孝男 訳, 平田富夫 訳, 組合せ最適化 第2版 理論とアルゴリズム, シュプリンガー・ジャパン株式会社 編, 丸善出版株式会社 発行, 2012年.
つまりなんとなく目の前の現象が最適化問題になりそうだな、と気づいても、それをモデル化する決まったやり方は存在しません。
現象を最適化問題として定式化、あるいはアルゴリズム化できるかどうかは、偶然現象を見つけて、偶然問題にできた、という段階を踏むのです。
つまり最適化問題に定式化するのが困難なのです。
すべての組み合わせを求めるのが困難な問題が多い
組み合わせ最適化問題の問題で有名なのが後述する巡回セールスマン問題です。セールスマンが特定の場所を訪れる順番（経路）を求める問題ですが、この経路のパターンは訪れる場所をn箇所とすると(n-1)!通りとなります。
例えばn=30のときはパターンが29!個、つまり8.8×1030個となります。これはコンピューターで1か所計算するのに10-8秒かかる場合、約2.8×1015年かかります。
組み合わせ最適化では組み合わせを求めるので、すべての組み合わせを網羅的に割り出して、評価値の大小をすべて並べ替えれば答えを出せますが、組み合わせが膨大になると、スーパーコンピューターで何億年とかの世界になってきます。
各種最適化手法を用いても、これだけの広大な変数空間から一粒の最善を見つけるのはかなり大変で、変数が増えれば、自然と解けなくなっていきます。量子コンピューターが実用段階に入ればかなり緩和されますが、依然として多変数の巡回セールスマン問題が難しいのは変わりません。
これではご利益はあまり感じられませんが、サイズをN=100にすると、計算時間はスパコンの402万年に対して量子コンピューターは130日となり、かなり印象が変わります。
QunaSys, 量子コンピューターの “よくある誤解” Top10
色々な組合せ最適化問題
ここからは様々な組合せ最適化問題を取り上げて、組み合わせ最適化問題のイメージを持つことを目標に解説していきます。
施設配置問題
過去に当ブログで施設配置問題の例として、移動販売の出店地を決める問題を扱いました。
この例ではやや複雑なので、もう少し簡単な例でご紹介します。
問題は以下となります。
コンビニを出店することになった。候補地は2つある。周辺には町が2つある。町からコンビニまでの距離は近い方が集客できるので町からコンビニまでの距離の合計は近い方がいい。どちらの候補地を選べばよいか。
| 候補地 | 町A | 町B |
| 候補地1 | 1km | 2km |
| 候補地2 | 1.5km | 1.2km |
暗算でも解ける問題ですが、これを最適化問題に書き出すと次のようになります。
- 目的関数：\(1x_{1}+2x_{1}+1.5x_{2}+1.2x_{2}\)→最小化
- 制約条件1：\(x_{1}+x_{2}=1\)
- 制約条件2：\(x_{1}, x_{2}\)は0か1
候補地1に出店するならx1は1、候補地2に出店するならx2は1となります。
組み合わせ最適化問題の定義に当てはめてみると、事象Eが「候補地1か候補地2」、評価値が「町からコンビニまでの距離の合計」となります。
これをエクセルのソルバーで解いてみましょう。
エクセルのセルに次のように入力します。
各セルの値は次のようになります。
- B3, C3：0
- D3：=B3+C3
- E3：=1*B3+2*B3+1.5*C3+1.2*C3
ソルバーの設定画面は次のようにします。
解決すると次のようになります。
なお最適化問題が非線形ならエボリューショナリーを使いましょう。
巡回セールスマン問題
いきなり問題のレベルが上がりますが、巡回セールスマン問題について解説します。
過去に当ブログではエクセルのソルバーで巡回セールスマン問題を解いてみました。
かんたんに言うと、以下のようにある地点があったときに、すべての地点を回って一筆書きで出発点に戻ってくるときに、移動する総距離が最短になるような回り方を求める問題です。
移動する順番が事象Eで、条件は「すべての地点を回って一筆書きで出発点に戻ってくる」、評価値は移動する総距離となります。
巡回セールスマン問題ではグラフ理論の基礎も必要になってくるので、まあこんなもんだ、くらいに思っていただければいいのではないかと思います。
詳しくは過去記事に譲りますが、これをエクセルのソルバーのシンプレックスLPで解くと、次のような経路が求まります。
地図が複雑になればなるほど、簡単ではないパターンが解になる可能性があり、上で述べたように、まともにすべてのパターンを求めようとすると、地点がn箇所とすると(n-1)!通り求める必要が出てきます。
またセールスマンが複数いて、それぞれのセールスマンが地点を回って戻ってくるという問題もあります。例えばVehicle Routing Problemです。これについても当ブログでは過去にGoogleの最適化ソルバーのOR-Toolsで求めてみました。ご興味がありましたらご一読ください。
●OR-ToolsでVehicle Routing Problem(VRP)を解く
瓶パッキング問題
当ブログでは過去に瓶パッキング問題を扱いました。瓶パッキング問題も組み合わせ最適化問題の一つです。
これらの問題の大元になっている問題は以下のようになります。
次のような植物を置く棚を作ることを考えます。
突き出した部分に植物を置き、上の段の陰になる部分には園芸用品などを置きます。
これをすべて1×4材長さ182cmを使って作るとします。
必要な部品は以下となりました。
① 20cm×2
② 40cm×2
③ 60cm×2
④ 80cm×2
⑤ 94cm×2
⑥ 60cm×12
これを1×4材を効率的に使って、最小の使用量で切り出したいとき、どうやってそれを求めるか。
というのが最適化問題となります。
一般に瓶パッキング問題というのは、n個の品物と何個かのビンがある場合を考えます。品物にはそれぞれサイズがあり、ビンはすべて同じ容量です。できるだけ少ない瓶にこれらの品物を詰め込みたい。ビンの詰め方はどうなるか、というのが瓶パッキング問題です。
今回の木材の問題では、品物が①から⑥までのパーツ、ビンが1本の182cmのSPF材です。
組み合わせ最適化問題の定義に当てはめてみると、事象Eが「各ビンに詰めるパーツ」、評価値が使用したSPF材の総本数となります。
上の問題の最適解はSPF材の総本数8本、利用した部材の合計消費量1320cmとなります。
まとめ【組み合わせ最適化は色々ある】
今回は組み合わせ最適化問題について、その概要といくつかの例を示しました。
組み合わせ最適化問題は色々あります。簡単に解ける問題は少ないです。
ただし世の中には色々な場面で現れる問題で、世の中の陰ではこういう計算をしている技術者の方がそれなりにいます。
組み合わせ最適化問題について学び始めた方に今回の記事がお役に立てましたら幸いです。
最適化ソルバーを使いこなす必要があるので、一般的に習得には時間がかかります
当ブログ（シルルスのコードおきば）ではエクセルソルバー関係の記事を他にも執筆しています。参考になりましたら幸いです。
Office最新版が常に使えます。楽天なら購入するとポイントも
●ソルバーをVBAで繰り返す【初期値を変えて複数解を自動探索】
●エクセルソルバーで複数解を求める方法【初期値を変えるしかないです】
●Support Vector Regressionをエクセルのソルバーで作ってみた
USBメモリ 128GB USB2.0 日本製【翌日配達送料無料】 KIOXIA（旧東芝メモリー）TransMemory U202 キャップ式 ホワイト 海外パッケージ LU202W128GG4
