本記事はGurobi.comに掲載されている下記の記事を日本語訳しています。

数理計画法は極めて強力かつ柔軟な技術です。線形計画法（LP）、混合整数計画法（MIP）、二次計画法（QP）といった最も伝統的な種類の数理モデルでさえ、製造、電力供給、金融、スケジューリング、サプライチェーン管理、輸送・物流など、世界中の複雑な問題の多くを解決することができます。

しかし、ビジネス要件によっては、LP、MIP、QPだけでは、問題や組織のプロセスの複雑さを捉えきれない場合があります。そこで、Gurobiの研究開発チームは、お客様に役立つ高度な機能をいくつか開発しています。今回はそのうちの4つをご紹介します。

バランスをとる：問題に2つの競合する目的がある場合

現実世界の最適化問題には、しばしば2つ以上の競合する、あるいは相反する目的が存在します。例えば、病院の経営者は、病院の看護師のシフト数を最小限に抑えつつ、従業員の満足度を最大化したいと考えるかもしれません。あるいは、投資家は、リスクを最小化しつつ利益を最大化するポートフォリオを構築したいと考えるかもしれません。

そのような場合、Gurobiの Multiple Objectives 機能がまさにお探しのソリューションとなるかもしれません。 Multiple Objectives API を使用すると、複数の目的を記述し、それらをコード全体とシームレスに統合できるため、コードベースの理解と保守が容易になります。

Gurobiは、次の 2 つのアプローチのいずれか、または両方の組合せを使用して、複数の目的のトレードオフを処理できます。

• 重み付けアプローチ：個々の目的関数を配合したものを最適化する

• 階層的アプローチ：優先順位に従って、より高い優先度の目的関数の悪化を制限しながら、段階的に最適化する

場合によっては、階層型の多目的関数を使用すると、目的関数の係数が大きい問題における数値的問題に対処しやすくなります。たとえば、最小化問題に、明確に異なる 2 つの目的関数についての係数が含まれることがあります。1 つの係数グループは 0 ～ 100 の範囲で、もう 1 つ のグループは 100,000 ～ 100,500 の範囲です。大きな係数を持つ目的項は、ペナルティとしてモデル化された 2 つ目の「隠れた」目的関数に対応することがよくあります。たとえば、看護師のスケジュール問題では、主な目的はシフト数を最小化することですが、ペナルティが課される 2 つ目の目的として看護師間のシフトバランスを考慮する場合があります。バランスの取れていない解にはペナルティ（係数 100,000）が課されるため、目的関数全体の最小化によって（うまくいけば）回避されます。ただし、係数がこのような大きな幅を持っている最適化問題は数値的問題を引き起こすことがあり、このような係数の代わりに問題を階層型多目的最適化としてモデル化することで回避できます。

この機能の詳細については、multiobj.py の例をご覧ください。

不確実性を受け入れる：問題データが変化したとき

人生は不確実であり、多くのビジネス問題における入力データも同様です。問題の詳細をすべて捉えた数理モデルを持っていたとしても、予測需要が予想より10%低かった場合、最適化された生産に何が起こるかを理解する必要があります。あるいは、建物の建設計画を立てていて、プロジェクトの第1フェーズが1日遅れた場合、2日遅れた場合、あるいは5日遅れた場合に建設コストがどうなるかを知りたい場合もあるでしょう。

Gurobiの Multiple Scenarios 機能を使用すると、複数の異なるシナリオセットを指定し、それらすべてのシナリオに対する解を計算できます。各シナリオを別々のモデルとして実装して個別解くことも可能ですが、この機能を使用すると、すべてのシナリオをバイナリ変数で区別し、1つの大きなモデルとして解くため、完全に別々のモデルで解く場合よりも高速に問題を解くことができます。

一見すると、複数シナリオ機能はかなり制限されているように見えるかもしれませんが、これらの制限を回避するためのヒントやコツがいくつかあります。ただし、この機能は前述の多目的最適化機能と組み合わせて使用できないという制限があります。

この機能の詳細については、multiscenario.py および sensitivity.py の例を参照してください。

ソリューションを受け入れてもらう：顧客がソリューションを（最適なソリューションであっても！）受け入れてくれない場合

ビジネスの詳細をすべて網羅した完璧なモデルの構築が完了しました。いくつかのバグを修正した後、モデルの改良に時間を費やし、場合によっては ソルバーパラメータを調整して 最高のパフォーマンスを実現しました。最終的に、モデルは妥当な時間内に最適な解を生成しました。おめでとうございます。これであなたの仕事は完了です！

… 本当にそうでしょうか？

多くの場合、最も難しいのは実際のモデリングやコーディングそのものではなく、最適化によって提供されたソリューションを顧客やユーザーに受け入れてもらい、実際に運用してもらうことです。

どうすれば可能なのでしょうか？ユーザーにはこれが最適な答えに見えないのでしょうか？

実際「ブラックボックス」から出てくるソリューションを受け入れるのは難しい場合があります。特にユーザーが数理最適化に精通していない場合、複雑なビジネス問題に対して最適な解決策を見つけることが実際に可能であると信じられないのかもしれません。

このような場合、複数のソリューションを用意し、エンドユーザーに提供することが非常に有益です。エンドユーザーは、それぞれのソリューションを比較し、最適なソリューションがなぜ実際に最適なのかを理解することができます。このアプローチは、最適なソリューションの価値を示すのに役立ち、意思決定者により高いコントロール感を与えます。

Gurobiでは、Solution Pool を定義することができます。この機能により、ソルバーは1回の実行で複数の解を自動的に返却します。ソリューションプールの設定方法はいくつかあり、（1）通常の最適化の過程で見つかったすべての解を追加の計算なしで保存する方法、（2）追加の計算コストをかけて、最適な解に加えてn個の最良の解を保存する方法などがあります。

複数の解決策を持つことは、ビジネス上の問題に、ユーザーの好みやその他の側面など、定量化が難しい暗黙的な要素が含まれている場合にも役立ちます。このような場合、最適なソリューションとは異なっていても、複数のソリューションの中から1つを選択する方が望ましい場合があります。

最後に、モデル化の担当者は解を見てモデリングエラーや制約の不足を検討することがよくあります。最適な解はこの点で役立ちますが、他の解があるとさらに役立つ可能性があります。

poolsearch.py の例は、この機能を使い始めるのに適しています。

迷路を抜け出す：モデルが実行不能な場合

モデルが実行不能な状況への対処は非常に困難です。特に大規模モデルを扱う場合、どの制約が問題なのかを把握するのが難しい場合があります。制約の数学的解釈は完全に正しいにもかかわらず、ビジネス要件の修正が必要となる場合もあります。Gurobiは、実行不能な状況への対処を支援する2つの機能を提供します。

最初の機能は、Irreducible Inconsistent Subsystem (IIS) の計算です。これは、モデルが実行不能な理由を理解するのに役立ちます。簡単に言うと、IISとは、元のモデルにおける制約と変数の上下限値についての実行不能な部分集合であり、そこから単一の制約または変数の上下限値を削除すると実行可能になります。IISを人間が理解できるモデル形式で記述することで、矛盾する制約のセットを手動で検査し、原因を特定するのに役立ちます。

IISは人間が解釈することを想定しているため、Gurobiは小さなIISを提供するよう努めています。しかし、IISの計算自体が非常に困難な問題であり、多くのMIPの解決を必要とする場合が多いため、それ自体が不可能な場合もあります。IISが役に立たない場合は、実行可能性緩和（Feasibility Relaxation）を計算することで、モデルにどのような変更を加えれば実行可能に変換できるかを理解するのに役立つ場合があります。feasopt.py の例では、実行可能性緩和機能の使用方法を示しています。

ビジネス要件が完全に理にかなっており、数学的な制約への変換も正しいにもかかわらず、Gurobiがモデルを実行不可能と判断するケースは少なくありません。このようなケースの大半は、数値的な問題が原因です。数値的な問題の症状としては、最適化ではモデルが実行不可 能と判断されるものの、IIS計算では「実行可能なモデルでは IIS を計算できない」というエラーが表示されることが挙げられます。パラメータ設定によって数値的な問題の症状を解決できる場合もありますが、数値的な問題の根本原因に対処することが、通常、推奨される最もロバストな解決策です。

隠れた名機能をさらに発見

Gurobiの高度なモデリング機能についてさらに詳しく知り、さらに多くの「隠れた魅力」を発見するには、1 時間のオンデマンドウェビナープレゼンテーション “Hidden Gems – Useful Gurobi Features You Might Not Know”（英語）をご覧ください。