🍣

数理最適化による問題解決の実践的なアプローチ

2020/11/03に公開

はじめに

数理最適化は現実社会における意思決定や問題解決を実現するための有用な手段です．数理最適化は，下図に示すように，(1)最適化問題のモデリング，(2)アルゴリズムによる求解，(3)結果の分析・検証，(4)最適化問題とアルゴリズムの再検討という一連の手続きからなります．
数理最適化の手続き
　数理最適化を用いて現実問題を解決するためには，まず，代表的な最適化問題とそれらに対する効率的なアルゴリズムを良く知ることが必要です．しかし，数理最適化の理論やアルゴリズムの専門的な知識があれば，それだけで現実問題を上手く解決できるようになるわけではありません．実際には，最適化問題のモデリングにかかるインタビューからシステムの実装・導入にいたるまで，これらの専門的な知識だけでは解決できない課題が数多く存在します．本稿では，筆者がコンサルタントとの共同研究を通じて得た経験にもとづき，研究者がコンサルタントと協力して現実問題に取り組む際に生じる課題とその対策について解説します．

目標の設定

実務では期間や人員など多くの現実的な制約の下で問題解決に取り組むため，学術的な課題に取り組むことは容易ではありません．コンサルタントは共同研究の成果を論文として発表する動機（インセンティブ）がなければ，確実かつ少ない手間で現実問題を解決できるアプローチを望ましいと考える傾向があります．例えば，研究者は現実問題から効率的なアルゴリズムが知られていない未解決の最適化問題を開拓したいと望む一方で，コンサルタントは現実問題を効率的なアルゴリズムが知られた既存の最適化問題にモデリングしたいと望むという方針の不一致はしばしば生じます．このような場合には，上手く課題を切り分けて異なるプロジェクトとして進めるなど，研究者とコンサルタントの間でプロジェクトの取り組みを調整する必要があります．
　現実問題の解決には多くの意思決定者（ステークホルダー）が関わっており，利害が衝突することは少なくありません．そのため，最適化問題のモデリングにかかるインタビューの段階で，コンサルタント，現場の計画担当者，責任者や経営者など，全ての意思決定者と十分なコミュニケーションを取り，最終的な目標について合意を得る必要があります．特に，運用と計画のどちらを効率化したいのかを明確することは重要です．数理最適化では，費用の最小化や利益の最大化などの指標(KPI)を目的関数に設定する事例が多いため，これらの指標を改善する計画案を作成することが目標であると思い込んでしまうことが多いです．しかし，実際には，現場の計画担当者の作業を自動化もしくは支援することが目標であることも少なくありません．前者では，計画担当者より優れた計画案を作成することが求められる一方で，後者では，計画担当者と同程度の計画案を作成すれば十分であり，それらの目標の難しさは大きく異なります．さらに，計画担当者の作業を完全に自動化する必要がなく，支援により計画担当者の作業の負担を軽減すれば十分であるならば，システムでは担当することが難しい一部の処理を計画担当者に任せることで現実問題を効率的に解決することが可能になります．
　現実問題に取り組む際には，意思決定の範囲（スコープ）を適当な規模に抑えることも重要です．複数の業務から構成される大規模な事業の全体を最適化すれば，個別の業務を最適化するよりも良い結果が得られるだろうと期待してしまいます．しかし，実際には，各業務を担当する数多くの意思決定者の合意を得るためのコミュニケーションに多くの手間がかかり，目標の設定すらおぼつかなくなることが少なくありません．

データの取得と利用

数理最適化を用いて現実問題を解決するためには，最適化問題の入力データが必要になります．そのため，現実問題に取り組む際には，必要な入力データを少ない手間で確実に取得できる環境が整備されているかどうか確認する必要があります．もし，数理最適化を用いたシステムを導入することで，現場の計画担当者に入力データを作成するための新たな業務が生じるならば，業務を効率化するという本来の目標から大きく外れる結果をとなります．
　数理最適化を用いて現実問題に取り組むためには，先にデータの取得と分析を済ませていることが前提です．これらは多くの手間と期間をかけて取り組むべきプロジェクトです．必要なデータを取得できる環境が整備されていないならば，まずはデータの取得と分析のプロジェクトを立ち上げるように勧めることが望ましいです．これらの成果は数理最適化に取って代わるわけではありませんが，データが可視化されるだけでも業務の効率化につながる多くの知見が得られるので成果を十分に期待できます．
　環境が整備されていても機密保持契約などの都合により必要な入力データが取得できないことも少なくありません．また，新たな事業を立ち上げる際など，そもそも該当する入力データが存在しないこともあります．現実問題に取り組む際には，必ずしも業務から生じる現実のデータそのものが必要なわけではなく，提示する計画案が現実問題の解決に有効なことを検証できる現実的なデータであれば十分であることが多いです．このような場合には，手間はかかりますがシミュレータを開発して現実的な入力データを作成することもあります．
　取得したデータがどれぐらい信頼できないかを確認することも重要です．取得したデータには欠損や誤りが含まれるだけではなく，計画や運用など業務のあらゆる段階で改変が生じる可能性があります．このような入力データでは，最適解問題の解が妥当な計画案につながらないだけではなく，そもそも最適化問題の実行可能解（制約条件を満たす解）すら求まらないことも多いです．現実問題に取り組む際には，入力データが正確であると過信せずに，むしろ入力データに問題がないか検証するぐらいの気持ちで取り組むことが望ましいです．

問題解決の手続き

現場の計画担当者のインタビューでは，最適化問題のモデリングに必要な情報が簡単には得られないことに注意する必要があります．最適化問題のモデリングに必要な情報の多くは，日常的に現場で業務に従事している計画担当者にとって改めて話題にするまでもない常識であり，コンサルタントが慎重なインタビューを重ねてもそれらの情報を十分に引き出すことはなお困難です．そのため，コンサルタントは十分なモデリングができないまま次の段階に進まざるを得ず，提示した計画案が現場の計画担当者の期待から大きく外れてしまうことは少なくありません．これは，現場の計画担当者とコンサルタントのどちらか一方が悪いわけではありません．そもそも，現場の計画担当者が最適化問題のモデリングに必要な情報を自ら整理できるならばコンサルタントは不要なはずであり，むしろ，暫定的な計画案を提示することは現場の計画担当者からモデリングに必要な情報を引き出すための手段であると割り切ることが望ましいです．そのようなわけで，初めに示した(1)-(4)の手続きが1回で終わることはまれで，妥当な計画案が得られるまで繰返し再検討が必要になります．ところで，再検討のたびに現場の計画担当者のコメントが大きく変わり話が行ったり来たり揺り戻しが生じることは少なくありません．このような場合には，打合せを始める際に，これまでのあらましを簡単に説明した上で最終的な目標を再確認すると良いです．
　現実問題が効率的なアルゴリズムが知られた最適化問題に類似しているもしくは，それを部分問題として含んでいることは多いです．しかし，既存のアルゴリズムをそのまま適用できる現実問題は少なく，実務から生じるさまざまな制約条件により，既存のアルゴリズムを大幅に修正する必要が生じたり，効率的なアルゴリズムが知られていない最適化問題にモデリングせざるを得ないことが多いです．このような最適化問題に対する代表的なアプローチとして，問題を整数計画問題に定式化して分枝カット法にもとづく整数計画ソルバーを適用する方法や，個別の問題に含まれる特徴的な構造を利用してメタヒューリスティクスを開発する方法などが知られています．整数計画ソルバーは汎用性が高いですが求解性能が入力データに敏感になることが少なくありません．メタヒューリスティクスは高い求解性能を期待できますが，新たな問題に取り組むたびに開発に多くの手間と期間を要することが少なくありません．このように汎用性と求解性能を両立させることは容易ではありません．
　数理最適化を用いて現実問題に取り組む際にボトルネックになるのは，最適化問題の修正にともなうアルゴリズムの修正もしくは開発です．実務から生じる制約条件が追加されると，アルゴリズムの大幅な修正もしくは新規に開発が必要となり，数日もしくは数週間，下手をすれば数ヶ月の期間を要することが少なくありません．そのため，下図に示すように，最適化問題のモデリングが終わるまでは，できる限り整数計画ソルバーなど汎用性の高い既存のソフトウェアを利用し，メタヒューリスティクスなどアルゴリズムの開発を避けることが望ましいです．その後に，既存のソフトウェアでは実務に耐える十分な求解性能が得られない，ライセンスの都合により現場の計画担当者が利用できないなどの事情があれば，改めてアルゴリズムの開発に着手すれば良いでしょう．
数理最適化を用いた現実問題に対するアプローチの例
　数理最適化を用いて現実問題に取り組む際には，アルゴリズムの実行に使える計算機の性能と計算時間を確認する必要があります．例えば，リアルタイムシステムを開発するために最適化問題を解くのであれば計算時間が1秒では長すぎます．逆に，年間の生産計画を立てるために最適化問題を解くのであれば計算時間が数時間でも長すぎることはないです．実務では，アルゴリズムの実行に使う計算時間を可能な限り短くする必要があるわけではなく，与えられた計算時間内に収まれば十分であることが多いです．また，最適化問題の厳密な最適解が必要なのか，どの程度の質の近似解が必要なのかも確認する必要があります．整数計画ソルバーは最適解を求める分枝カット法にもとづいているため，最適解が求まらない限りは何も出力しないと勘違いされることが少なくありません．しかし，整数計画ソルバーは，それまでの探索で得られた最良の実行可能解を暫定解として保持しているため，計算時間の上限を設定して近似解を出力させることが可能です．

最適化問題のモデリング

これまで説明したように，インタビューでは最適化問題のモデリングに必要な情報が簡単には得られないため，最も簡単な最適化問題から始めて，現場の担当者と再検討を繰返しつつ，段階的に変数や制約条件を追加して最適化問題を拡張することが望ましいです．この方法にはいくつか利点があります．

始めから複雑な手続きをプログラミングできないように，始めから複雑な最適化問題もモデリングできません．慎重に取り組んだとしても始めから誤りを全く含まない最適化問題をモデリングすることは難しいです．簡単な最適化問題から始めて，慎重に検証を重ねつつ，段階的に複雑な最適化問題に拡張することで，最適化問題に含まれる誤りを効率的に検出できるようになります．最適化問題のモデリングはプログラミングに通じることが少なくないので，プログラミングにおける多くの注意事項は最適化問題のモデリングにも当てはまると考えて差し支えありません．
最適化問題の入力データの項目を少なく抑えることができます．以前に説明したように，現実問題に取り組む際には，必要な入力データを少ない手間で確実に取得できることが前提となります．すなわち，最適化問題をモデリングする際に必要な入力データの項目をできる限り減らせば，入力データの取得に要する手間を減らすことができるわけです．特に，取得できるデータを全て利用するのではなく，信頼できるデータの項目を吟味した上で必要最小限の利用にとどめることが望ましいです．
インタビューで現場の計画担当者が挙げる要件が多いときに，これらを必ず満たすべき要件（絶対制約）と可能ならば満たすことが望ましい要件（考慮制約）に分類できます．以前に説明したように，現場の計画担当者にとって必ず満たすべき要件は改めて話題にするまでもない常識です．そのため，インタビューにおいて現場の計画担当者が挙げる要件から重要なものとそうでないものを見分けることは容易ではありません．しかし，暫定的に選んだ要件を元に作成した計画案を提示すれば，現場の計画担当者から，この計画案は重要な要件を満たしていないとの指摘を得ることは容易です．また，提示した計画案が現場の計画担当者の期待から大きく外れていなければ，計画案を作成する際に考慮しなかった要件は重要ではなかったと確認できます．
実行可能解が求められないときに原因となる制約条件を特定し易くなります．複雑な最適化問題では，多くの制約条件が互いにトレードオフの関係を持つため，実行可能解が求められない原因となる制約条件を特定することは容易ではありません．このような場合には，重要な要件のみを制約条件に持つ簡単な最適化問題から始めて，段階的に制約条件を追加することで，重要でないにも関わらず実行可能解を求める妨げになる制約条件を特定できます．実務では，重要な要件であってもそれらを全て同時には満たせないこともあります．このような場合には，現場の計画担当者といくつかの重要な要件が互いに衝突していることを確認した上で，どの要件を優先するか決定する必要が生じます．このとき，優先しないと決めた要件を制約条件から除外する必要はなく，例えば，制約条件 $\sum_{j=1}^n a_{ij} x_j \ge b_i$ ( $i \in \overline{M}$ )を $\sum_{j=1}^n a_{ij} x_j + y_i \ge b_i$ と緩和し，その違反量 $y_i$ の重み付き和 $\sum_{i \in \overline{M}} w_i y_i$ を目的関数に追加すれば，これらの要件を考慮した最適化問題に変形できます( $\overline{M}$ は優先しない要件に対応する制約条件の添字集合)．ただし，制約条件の緩和を多用すると，これらの制約条件のトレードオフの調整が難しくなることに注意して下さい．

最適化問題をモデリングする際には，入力データとあわせて現場の計画担当者が過去に作成した計画案を入手することが望ましいです．これらの計画案がインタビューで現場の計画担当者が挙げた要件を満たしていなければ，それらの要件は重要でなかったと判断できます．ただし，以前に説明したように，取得した入力データは計画や運用など業務のあらゆる段階で改変が生じる可能性があり，それらが原因で現場の計画担当者が作成した計画案が要件を満たしていないこともあります．特に，運用の段階で入力データの変更に合わせて計画案が改変されている可能性が高いので注意する必要があります．

システムの実装と導入

私自身はシステムの実装や導入に関わった機会は少ないですが，コンサルタントとの共同研究を通じて気づいた点をいくつか挙げます．

現場の計画担当者が明らかに実行可能解が存在しない入力データを与えることは少なくありません．業務では利用可能な資源を使い切るように計画を立てるため，例えば，生産計画において需要量の合計が生産量の合計をわずかに上回るように入力データを与えることは少なくありません．実際に，現場の計画担当者は，入力データを与えて最適化問題を1回だけ解くのではなく，入力データに含まれる不具合を修正しては最適化問題を解く手続きを繰り返すことが多いです．これは，現場の計画担当者が数理最適化を用いてシミュレーションしているとも言えます．このような場合には，全ての要件を考慮した計画案を解く最適化問題を解く前に，必要最低限の要件のみを満たす実行可能解が存在するかどうかを確認する簡単な最適化問題を解く2段階法が有効です．この方法であれば，入力データに含まれる不具合が原因で実行可能解が存在しないときに，その原因をすぐに知らせることができます．
現場の計画担当者だけがシステムの利用者とは限らないことに注意する必要があります．例えば，下図に示すように，業務では営業担当者が見積りを作成するために計画担当者に計画案の作成を依頼することがあります．このような場合には，営業担当者が簡単な計画案を元に見積りを作成できるならば，初めに営業担当者にシステムを利用してもらうことが望ましいです．営業担当者が計画担当者に計画案の作成を依頼する必要がなくなれば，見積りの作成に要する時間を大幅に短縮できる上に計画担当者の負担も大いに軽減できます．しかも，簡単な計画案で十分ならば複雑な最適化問題にモデリングする必要もないので，早い段階でのシステムの実装と導入が可能です．以前に説明したように，現実問題の解決には多くの意思決定者が関わっており，必ずしも現場の計画担当者だけがシステムの利用者となるわけではありません．それぞれの意思決定者の目標を踏まえて，現場の複数の利用者からフィードバックを貰いながら段階的にシステムを導入することが望ましいです．

また，業種によりシステムを導入する難しさが大きく異なることに注意する必要があります．製造業など設備の運用が簡単に調整できない事例ではシステムの導入が難しく，オンラインサービスなどサービスの運用が簡単に調整できる事例ではシステムの導入が容易であることが多いです．
作成した計画案を可視化することは大きなメリットがあります．前節で説明したように，最適化問題のモデリングでは，現場の計画担当者に計画案を提示してフィードバックをもらうことが重要です．このとき，現場の計画担当者が直観的に理解し易い形で計画案を提示する必要があります．もちろん，可視化には相応の手間がかかりますので，最小の手間で最大の効果を狙って可視化の導入は必要最小限にとどめるよう注意して下さい．

まとめ

本稿では，筆者がコンサルタントとの共同研究を通じて得た経験にもとづき，数理最適化の研究者がコンサルタントと協力して現実問題に取り組む際に生じる課題とその対策について解説しました．研究者をそのままエンジニアに置き換えても当てはまる内容が多かったのではないでしょうか？また，数理最適化に限らず，数理的な手法にもとづいて現実問題を解決する際に共通する話題も多かったと思います．大学や研究所などで教育研究に従事する研究者が，企業などが抱える現実問題の解決に携われる時間は少ないです．それだけに，研究者が単独ではなくコンサルタントと上手く協力して現実問題の解決に当たることが望ましいです．本稿で取り上げた課題は限定的で，その対策も妥当性の裏付けがあるわけではないことに注意して下さい．数理最適化を活用したいエンジニアやコンサルタントの皆様の参考になれば幸いです．