Excelで学ぶ整数計画法 -ソルバーアドインを使いこなせ！-

# 概要
　表計算ソフト[Excel](https://ja.wikipedia.org/wiki/Microsoft_Excel)は、その多機能な面から、図表作成だけでなく、[進捗を記録](http://qiita.com/nezuq/items/d2ff540cdba00d41bfda)したり[イラスト](https://togetter.com/li/904910)を描いたり[ゲームを作成](http://home.att.ne.jp/zeta/gen/celljong/)したりするためにも使われています。
　この記事では、そんなExcelに備わっている[ソルバーアドイン](support.office.com/ja-jp/article/-9ed03c9f-7caf-4d99-bb6d-078f96d1652c)の使い方と、実際の問題にどう対処すればいいかを解説します。手軽に制約式や目的関数を記述できますので、仕事や趣味など**大いに**役立つことでしょう。

# 下準備
　まず、ソルバーアドインを使える状態にします。導入方法はOfficeのバージョンによって多少異なりますので、次のリンクを参照して下さい。

- Office 2003→[Excel2003 Expert 解答（ソルバーアドインの使用）](http://www.wannko.net/office/mondai/excel2003expert/solbakai.html)
- Office 2007→[Excel2007でソルバーアドインはどこに？](http://www.relief.jp/docs/003394.html)
- Office 2010→[What-If分析：ソルバー：エクセル2010基本講座](http://www4.synapse.ne.jp/yone/excel2010/excel2010_solver.html)
- Office 2013→[Excel 2013：ソルバーを使って計算結果を求めるには](https://www.wanichan.com/pc/excel/2013/8/36.html)
- Office 2016→[ソルバーを使用して最適値を求める | Excel2016 | 初心者のためのOffice講座](https://hamachan.info/win10-excel-solver/)

# 使い方
　……上記の「下準備」のリンク先を読めばおおよそ掴めると思いますが、ここでは**いつものサンプル問題**をExcel上で表現して解いてみます。

- 最大化する目的関数：$Z=5X+4Y$
- 制約式1：$1.5X+3Y\leq13.5$
- 制約式2：$3X+Y\leq10$
- 制約式3：$X+2Y\geq7$
- 変数の範囲：$X\geq0$,　$Y\geq0$
- その他：$X,Y\in\mathbb{N}$

![image.png](https://qiita-image-store.s3.amazonaws.com/0/29802/962f11af-e76c-f5e3-5981-bd810c7e5ec4.png)

　ちなみにExcelで使えるソルバーエンジンとしては、
- 滑らかな非線形計画法用の「GRG 非線形」
- 線形計画法・整数計画法用の「シンプレックス LP」
- 滑らかじゃない非線形計画法用の「エボリューショナリー」
があります。「**滑らかって何なんだよ！**」って人がきっと大多数だと思いますが、これを解説しだすと本文の趣旨から逸れますので、解説リンクだけ貼っておきます。普段使いでは「シンプレックス LP」だけ使っていれば問題ないでしょう。
　　[C1級関数,Cn級関数などの意味と具体例 | 高校数学の美しい物語](https://mathtrain.jp/c1kyukansu)

# よりディープな使い方

- 上記画像からお分かりのように、**SUMPRODUCT関数が使えます**。これは、SUMPRODUCTが積和を表す関数であることから、「線形式でなければならない」という「シンプレックスLP」の条件に反しないからです。他にも意外な関数が使えるかもしれません。
- 「変数セル」で選ばれたセルの値が変化しても変化しないセルについては、何ら縛りはありません。例えば、**制約式の係数をIF関数やVLOOKUP関数などでゴチャゴチャ計算**することはセーフですし、**(変数セルに無関係な)セルの値によって目的関数を変更する**こともセーフです。
- 制約条件で「セルAはセルB以上」といった条件を入れることはよくありますが、「セルAはセルB1～B10以上」や「セルA1～A10はセルB13～B23以下」といった条件も書けます。要するに、**1対多や多対多で条件指定できる**わけです。ただし、多対多では互いのセルの数を等しくする必要があります。
- ソルバーアドインのウィンドウを表示した際、Excelのフォーカスが「目的関数のセル」に移動します。例えばシートの左上を見ている際に、目的関数のセルが"Z100"など遠い位置にあったとしたら、**相当の距離を自動でスクロール**するわけです。逆に言えば、例えばA1セルを目的関数のセルにしておくと、**常に(左上に)視点を固定できます**。

　こうした性質は、Excelでツールを作りたい場合に大いに役立つでしょう。

# 実際のツールから見るソルバー開発術

　ここでは、実際に[私が作ったユーティリティツール](https://drive.google.com/open?id=0B22mWPiNr-6-OU5DMjNQRU9tSDA)を元に、各種テクニックについて解説していきます。念のために言っておきますが、↓2行の箇条書きはそれ以降の説明に**それほど関係ない**です。

- [デレステ](http://cinderella.idolmaster.jp/sl-stage/)P向けの説明：[特技Lv上げ](https://imascg-slstage-wiki.gamerch.com/%E7%89%B9%E6%8A%80%E3%83%AC%E3%83%99%E3%83%AB%E4%B8%8A%E3%81%92)する際に、使用する人数を最大化しつつ、成功率を目標%まで持っていくための最適化ツールです。
- それ以外の人向けの説明：[ナップサック問題](http://www.msi.co.jp/nuopt/docs/v18/examples/html/02-05-00.html)の一種を解くための最適化ツールです。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/29802/60821da3-98ca-1aa2-43c4-a70b1c44152a.png)

　上記ユーティリティで目指したいのは、例えるならば「指定された高さ以上まで積み木を積み上げる」作業です。
　それぞれの積み木の高さは、OFFSET関数を使って自動計算します。このOFFSET関数は、変更する変数セルの内容とは無関係に(事前に)決まりますので、問題なく「シンプレックスLP」ソルバーを使えます。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/29802/f60ad6f0-dbcd-807b-aa22-193ecd0eec0d.png)

　また、積み木を積み上げた際の高さは、それぞれの種類の積み木について、「積み木の高さ×使用した個数」を足し合わせれば計算できます。ここでSUMPRODUCT関数が大活躍します。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/29802/ddce97b8-52ad-5d8f-ed4e-1561ecb46e47.png)

　さらに、このセル(見づらいですが緑色の枠で囲まれた方)ではIF文が使われていますが、H5セルは「変数セル」に指定されたセルではありませんので、セルの数式は「ソルバーに関係なく」決まっていると言えます。なので、この場合も問題なく「シンプレックスLP」ソルバーを使えます。
　おまけに、H5が0でない場合の目的関数が「値A-値B×100」といった複雑な数式になっていますが、これは「**満たしたい条件が複数あった場合に、重み付けをして足し合わせる**」というテクニックが使われています。詳しくは「多目的最適化」でググりましょう。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/29802/ce95d582-ab13-4624-6ad9-60d64fb3d529.png)

# まとめ
　Excelでソルバーを利用したツールを開発する一番の利点は、その分かりやすさです。
　セルで入力した値や数式をそのまま利用できますし、結果を表示する際はExcelのUIを存分に活かせます。上記画像で言えば、例えば「使わない積み木(チケット/アイドル)は使用数0なので条件付き書式でセルを真っ白にする」といった小細工が簡単に実装できます。
　反面、計算速度は遅めですので、高速なソルバーを作りたい場合は、[GLPK](http://pse.web.nitech.ac.jp/doc/easymanual.pdf)や[Google Optimization Tools](https://www.gixo.jp/blog/8871/)などを利用してプログラミングなどを行う必要があるでしょう。