最適化モデリング：それを単なる芸術で終わらせないための技術

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

最適化モデルの実装は、「通常」のソフトウェア開発とはまったく異なるものだと私たちは皆知っています。事前に単純なTODOリストを定義し、厳密なスケジュールに従ってタスクを実行することはできません。創造的な自由、何時間も要する調査、そして多くの失敗が必要です。そこには勇気、創造性、そして忍耐力が求められます。同僚は計画を尋ねるべきではありません。実際、この困難な期間中は、「終わった」とあなたが告げるまで、そっとしておくべきです。最適化は芸術なのです。他に方法はありません。そうですよね？

私は長年多くのチームと仕事をしてきましたが、それぞれが最適化を実際に実装する際に独自の方法を持っていました。上記の考え方を共有するチームもあれば、異なる姿勢を取るチームもありました。その全容を見てきた中で、私は他の分野のベストプラクティスを適用しているチームに軍配を上げたいと思います。この記事では、それが実際にどのようなものかをお見せします。

ステップ１：準備

コードを一行書く前に、手元に準備しておきたい3つのことがあります。

• 数理モデルを書き出す
  Visual Studio CodeやWordのようなツールは数式表記をうまくサポートしてくれます。実際、すぐにコーディングしたい場合は、ホワイトボードや紙でも十分です。モデルは作業を小さな塊に分解するのに役立ち、後でのデバッグにも役立ちます。
• 少なくとも１つの現実的なデータセットを集めておく
  これはもちろんテストに必要です。しかし、ソリューションを現状と比較するのにも役立ち、解決策の品質と実行時間の両面で比較できます。また、モデルが適切なレベルの詳細を捉えているかを確認するのに役立ちます。そして、他の人に解決策を実演したい場合の素晴らしい出発点となります。ランダムに生成されたデータは避けてください。そのようなデータではソルバーのパフォーマンスが大きく異なる可能性があるためです。
• モデルの核心部を特定しておく
  言い換えれば、現実的に意味をなすモデルの最小限の部分を特定します。これは「実用最小限製品（MVP: Minimum Viable Product）」よりもはるかに小さい場合があります。詳細な条件付けは生成されたソリューションを実際に実行するためには重要ですが、最初のイテレーションでは、必要ではない多くの詳細を省略できます。 人員計画では、各シフトが1人に割り当てられることを保証する制約が必要ですが、労働規則はまだ必要ありません。サプライチェーン計画では、在庫バランス制約が必要ですが、需要の優先順位付けは後で追加できます。

ステップ２：実装

いよいよ調理の時間です！ 何も実行しないままにモデルの完全な定式化を実装するのではなく、反復的なアプローチを試してみてください。少し鍛錬が必要ですが、長期的にはより大きな成果が得られます。

• 目的関数または制約を一度に1つずつ実装し、必要な場合にのみ補助変数を導入する
  定式化が既にあるため、最初からすべてを追加したくなるかもしれませんが、定式化とコードの両方に間違いが含まれている可能性があります。間違いは、一度に1つずつ導入する方が診断、解決は容易になります。たとえば、発電最適化では、起動停止コストと対応する補助変数は後回しにできます。
• 常にコードを実行できるようにしてください
  私はよく人々のコードのデバッグを手伝ってきました。最初の質問である「プログラムを最初から最後まで実行できますか？」という問いに対するユーザーの答えは、「いくつか問題があり、現在取り組んでいるので、最初にいくつか変更したり、いくつかの手順をスキップしたりする必要があります」ということがよくあります。常に動くイテレーションから次のイテレーションへと進む習慣を身につけてください。バージョン管理と自動テストは、ここで大きな違いを生むことができます。
• モデルを小さなブラックボックスのように設計する：問題データを解データに変換する1つの関数（またはクラス）として
  モデルが関与しない限り、前処理と後処理はその関数の外に置いてください。モデルオブジェクトを外部から隠します。このアプローチにより、コードがクリーンに保たれ（関心の分離: separation of concerns ）、テストを書きやすくなります。このアプローチの例については、OptiModsのライブラリを参照してください。

ステップ３：検証

反復的なアプローチを採用する理由は、作業を継続的に検証できるからです。早く検証できるほど、まだ比較的簡単に解決できる段階で間違いを見つけられる可能性が高まります。次から次へとバグが発生するような状況では、記録的な速さで大規模な最適化モデルを実装（あるいはさらに悪いことにデプロイ）しても、もはや誉められたものではありません。これを避ける方法は次のとおりです。

• あなたのモデルが下した決定を可視化する
  モデルの正しさと価値を正当化するために、目的関数の値に焦点を当てたくなるかもしれません。数値が改善されれば、何か正しいことをしているに違いありません。しかし、その比較は、関連するすべての解がまったく同じ制約セットに対して実行可能である場合にのみ役立ちます。代わりに、決定のシンプルな可視化を見つけてください。たとえば、従業員にシフトを割り当てる場合、従業員と曜日を軸にしたシンプルなグリッドを表示します。これは、連続シフトの最大数などの制約に関する問題をすぐに特定するのに役立ちます。VRP（車両経路問題）を解決している場合は、各車両の詳細なスケジュールと停車地、タイミングを出力します。Jupyter NotebookとPandasおよびPlotly、またはシンプルなStreamlitテストアプリケーションは、テスト目的で視覚化をすばやく追加するのに最適な方法です。
• unittestのようなフレームワークを使用して自動テストを追加することは、将来の変更後もコードがスムーズに実行されることを保証する優れた方法です
  この導入により、モデルの定式化について慎重に考えることも強制されます。1つの機能をテストする小さなデータセット（理想的には、それぞれ1つまたは2つの要素しか含まないセット）を作成してみてください。シフト割り当ての問題に戻ると、通常、特定のシフトの組合せを1人の従業員に割り当てることができるかどうかを決定する多くの労働規則があります。それぞれの規則について、1人の従業員と、該当する規則に違反する一連のシフトを含む小さなデータセットを作成できます。次に、モデルが実行不可能であることを表明します。2番目のテストとして、2人目の従業員を追加し、シフトが2人の従業員間で分配されることを確認します。
• パフォーマンスよりも正しさに焦点を当てる
  正しい結果を出さないもののパフォーマンスを改善しても意味がありません。そして、モデルを拡張するにつれて、パフォーマンスは向上することも悪化することもあります。そして、試してみないとわかりません。同じ理由で、当社のエキスパートチームは、モデルに変更が加えられた場合、ソルバーパラメータを再検討することをよく提案します。以前は機能していたものが、もはや期待される動作をもたらさない可能性があるためです。
• フィードバックを求める
  ユーザーがモデルが動作しているのを見ると、定式化を変更する可能性のあるフィードバックをよく提供してくれます。いくつかの制約が欠けているかもしれません（「そのスケジュールは実際には実行できない」）、または物事を複雑にしすぎているかもしれません（「そのような入力データを見ることはないだろう」）。

上記のようなアイデアは決して特別なものではなく、実際には最適化を含む（しかし、それに限定されない）多くのソフトウェア開発チームで適用されています。これらは成功を保証するものでもありません。おそらく、定式化の最後の部分を完了した後、パフォーマンス、コードのリファクタリング、追加のテストに着手する必要があるでしょう。しかし、次に「巷の」ベストプラクティスについて耳にしたとき、私たちオペレーションズリサーチの実務家は本当にそれほど違うのか、自問してみてください。常に学ぶべきことがあります。

著者プロフィール Ronald van der Velden（ロナルド・ファン・デル・フェルデン） テクニカルアカウントマネジメント マネージャー – EMEA ロナルド・ファン・デル・フェルデンは、ロッテルダムのエラスムス大学で計量経済学およびオペレーションズリサーチの修士号を取得しました。キャリアをQuintiqでスタートし、ソフトウェア開発者として計画およびスケジューリングモデルの作成、世界中の顧客でのビジネス分析とソリューション設計、バリュースキャンや「1週間デモチャレンジ」といった技術営業活動など、さまざまな役割を経験しました。また、エンターテイメント業界の3Dグラフィックスに特化したニッチ企業でリード開発者として2年間勤務した後、Gurobiで自身の数学的ルーツに戻りました。余暇には、妻と2人の息子と過ごしたり、フェルウェでランニングをしたり、趣味のソフトウェアプロジェクトに取り組んだりすることを楽しんでいます。