Skip to content
検索結果に戻る

多目的混合整数計画法

提唱者
Ehrgott, M.; Mavrotas, G. and others in multi-criteria optimization
年
1980s–2000s
種類
Mathematical optimization
系統
Simulation / optimization

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

多目的混合整数計画法(MO-MIP)は、線形または非線形制約の下で、2つ以上の相反する目的関数を同時に最適化する最適化フレームワークです。このフレームワークでは、一部の決定変数は整数値に制限され、他の変数は連続値を取ります。これは、連続量に加えて離散的な選択を必要とする工学設計、サプライチェーン計画、資源配分、スケジューリング問題に広く応用されています。

手法の背後にある直感

多くの現実世界の意思決定には、離散的な選択(いくつの施設を開設するか、どのプロジェクトに資金を供給するか、機械を購入するかどうか)と連続的な決定(どれだけ生産するか、予算をどのように配分するか)の両方が含まれます。これらの選択が複数の相反する目標に同時に影響する場合(例えば、サービスレベルを最大化しながらコストを最小化する場合)、単一の最適解は存在しません。代わりに、MO-MIPは、すべての非劣解のトレードオフフロンティア(パレートフロンティア)を探索し、意思決定者に単一の強制的な答えではなく、実現可能な妥協点の構造化されたマップを提供します。

歴史学

混合整数計画法は、1950年代から1960年代にかけて、Gomory、Land、Doigの研究を通じて定式化されました。多目的拡張は、多くの工学およびオペレーションズリサーチの問題が競合する目標を含むことを研究者が認識した1970年代から1980年代にかけて登場しました。体系的な扱いは、Ehrgott (2005) と Mavrotas (2009) によって統合され、彼らのイプシロン制約法の実装は、実用的なMO-MIPの広く引用される参考文献として残っています。

使うべき場面

MO-MIPは、意思決定問題が整数変数またはバイナリ変数(施設配置、プロジェクト選択、スケジューリング)と連続量を自然に含み、2つ以上の相反する目的を明示的にトレードオフする必要がある場合に使用します。厳密またはほぼ厳密なパレート解が必要であり、計算リソースが分枝限定探索を許容する場合に適しています。すべての変数が連続である場合(代わりに多目的LPまたは非線形計画法を使用)、問題の規模が大きすぎて厳密なMIP解法が実行不可能であり、メタヒューリスティクスがより実用的な場合、または単一の集約目的で十分であり、多目的分析が意思決定価値を追加しない場合は使用しないでください。

限界と注意点

  • 計算コストは整数変数の数と問題サイズに対して指数関数的に増加します。大規模なインスタンスでは、厳密な方法では手に負えない場合があります。
  • すべての目的と制約を数学的な形式で正確に定式化する必要があり、これは定性的または曖昧な現実世界の目標では難しい場合があります。
  • 重み付き和法のようなスカラー化方法は、パレートフロンティアの非凸領域にある解を発見できず、重要なトレードオフを見逃す可能性があります。
  • 密なパレートフロンティアを生成するには、多くのMIP部分問題を解く必要があり、総計算時間が増大します。
  • 結果は制約の定式化と問題データの精度に敏感です。実行不可能または適切に境界付けられていないモデルは有用な出力を生成しません。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 各スカラー化された部分問題に対して、証明可能な最適解または準最適解を提供し、扱いやすい問題サイズに対してパレートフロンティアの品質を保証します。
  • 連続緩和では忠実に表現できない、現実世界の離散的な選択(バイナリ決定、整数数量)を自然に扱います。
  • 完全なパレートフロンティアを生成し、意思決定者に単一の強制的な妥協点ではなく、透明で構造化されたトレードオフ情報を提供します。
  • イプシロン制約法やその他の体系的なスカラー化により、非劣解集合の制御された密な探索が可能です。
  • 大規模MIP問題を扱う幅広い商用およびオープンソースソルバー(CPLEX、Gurobi、GLPK、CBC)と互換性があります。

応用

  • 施設配置とサプライチェーンネットワーク設計:コストを最小化し、顧客サービスカバレッジを最大化するバイナリ開閉変数を使用します。
  • 資本予算編成とプロジェクトポートフォリオ選択:予算とリソースの制約の下で、バイナリプロジェクト選択変数を使用して、リターンを最大化し、リスクを最小化します。
  • 生産スケジューリング:整数ロットサイズとバイナリ機械割り当てを使用して、メイクスパンと納期遅延を同時に最小化します。
  • エネルギーシステム計画:離散的な投資決定と連続的なディスパッチ変数を使用して、発電所の組み合わせのコストとCO2排出量を最適化します。
  • 医療資源配分:整数人員配置とバイナリ施設決定を使用して、患者カバレッジと公平性を最大化しながら支出を最小化します。
  • 輸送とロジスティクス:整数車両フリートとルーティング決定を使用して、移動時間と排出量を同時に最小化します。

使い方

使い方

1

問題を定式化するには、最小化または最大化するk個の目的関数 f_1(x), ..., f_k(x)、線形または非線形制約 Ax <= b の集合、および一部の変数が整数値(例:バイナリ0/1)で、他の変数が連続値である変数ドメインを指定します。解く前に、境界とデータを明確に定義します。

2

スカラー化または分解戦略を適用して、多目的問題を一連の単一目的MIP部分問題に変換します。一般的な戦略には、重み付き和法(w_i * f_i の合計を最小化)、イプシロン制約法(他の目的を閾値レベルに制約しながら1つの目的を最適化)、および達成スカラー化関数があります。

3

各スカラー化されたMIP部分問題を、分枝限定法、分枝カット法、またはその他の厳密解法ソルバー(例:CPLEX、Gurobi、GLPK)を使用して解きます。各部分問題について、ソルバーは整数実行可能解空間を探索し、各ノードでLP緩和を適用し、実行不可能または劣位な枝を刈り込みます。

4

部分問題の実行全体で、すべての非劣解を収集し、パレートフロンティアを近似的または厳密に構築します。2つの解は、どちらもすべての目的において他方よりも厳密に優れていない場合に非劣位です。フロンティアを密にするために、スカラー化と解法のサイクルを異なるパラメータで繰り返します。

5

意思決定者には、パレートフロンティアを視覚化(散布図、並行座標プロット)とともに提示します。多基準意思決定ルール、ステークホルダーの好み、または辞書式順序付けを適用して、非劣解の集合から実装する優先解を選択します。

よくある落とし穴

  • 非凸な目的空間で重み付き和法を使用すると、パレートフロンティアのセグメント全体を見逃すことになります。そのような場合は、イプシロン制約法または拡張達成スカラー化関数を推奨します。
  • 緩和で整数変数を連続変数として扱い、後で丸めることは、パレート最適性を保証せず、実行不可能または劣位な解を生成する可能性があります。
  • 解く前に制約の冗長性やタイトネスのチェックを怠ると、ソルバーが過剰な時間実行されたり、誤った実行不可能性を報告したりする可能性があります。
  • フィルタリングや視覚化のガイダンスなしにすべてのパレート解を意思決定者に提示すると、意思決定麻痺につながります。常に構造化された選択支援とともに結果を提示してください。
  • 少なすぎるスカラー化実行でパレートフロンティアが完全であると仮定すると、過信した結論につながる可能性があります。収集されたすべての解にわたる非劣性をチェックしてカバレッジを検証してください。

よくある質問

MO-MIPは標準的な多目的線形計画法とどう違うのですか?

多目的LPでは、すべての決定変数が連続であるため、効率的なパレート解は凸多面体の頂点で見つけることができます。MO-MIPでは、一部またはすべての変数が整数値である必要があり、実行可能集合が非凸で離散的になるため、シンプレックス法ではなく分枝限定探索が必要です。

NSGA-IIのようなメタヒューリスティクスを厳密なMIPソルバーの代わりに使用できますか?

はい、大規模または組み合わせ的に複雑な問題では、スケーラビリティが優れているため、メタヒューリスティクスがしばしば好まれます。トレードオフとして、メタヒューリスティクスは最適性保証のない近似パレートフロンティアを提供しますが、厳密なMO-MIPソルバーは、見つけた解の非劣性を保証します。

イプシロン制約法とは何ですか、なぜ推奨されるのですか?

イプシロン制約法は、1つの目的を最適化しながら、他のすべての目的が指定された境界(イプシロン)よりも悪くならないように制約します。この方法は、重み付き和法が見逃す非凸パレート領域の解を発見できるため、一般的なMO-MIP問題に対してより信頼性が高くなります。

いくつのパレート解を生成すべきですか?

目的の数と意思決定に必要な解像度によります。2つの目的の場合、20〜50個の均等に配置された解でフロンティアを特徴付けるのに通常十分です。3つ以上の目的の場合、数は組み合わせ的に増加します。解の過負荷を避けるために、対話型または選好誘導型の手法が推奨されます。

MO-MIPはデータに不確実性がある問題に適していますか?

標準的なMO-MIPは決定論的データを仮定しています。入力データが不確実な場合は、ロバスト最適化または確率的計画法の拡張と組み合わせる必要があります。例えば、2段階確率的MO-MIPや最悪ケースの目的境界を持つロバストMO-MIPなどです。

関連する手法

参考文献

  1. Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer, Berlin.

    ISBN:9783540213987
    コピーしました。
  2. Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465.

    DOI 文献を開く
    コピーしました。