整数計画問題の実験環境
小規模な整数線形計画問題を厳密な分枝限定法で解き、探索のすべてのノードを確認できます。探索木全体を調べた場合にのみ、最良点を最適解と証明済みとして報告します。
プログラムは4,000文字、40行、変数8個、複数変数を含む制約8個までです。ノード上限は1～5,000で、厳密な算術演算が3,000,000回に達した場合も探索を停止します。端末上のバックグラウンド処理で計算し、制限時間は15秒です。JSONレポートとノードのCSVをダウンロードできます。 一行目に maximize (最大化) または minimize (最小化) と目的関数を入力します。その後、制約を一行ずつ入力してください。 最大4,000文字。 実行前に設定を確認してください。
処理結果
整数計画問題の実験環境
- maximize 5x + 4y のように、目的関数を一行目に記述してください。
- 制約を一行ずつ入力します。x, y >= 0 のような上下限制約や、integer x、binary z のような任意の行を追加できます。
- ノード上限を設定して探索を実行してください。
- 状態、現在の最良実行可能解、最良境界、ギャップを確認し、JSONレポートまたはノードのCSVをダウンロードしてください。
できること・制限
プログラムは4,000文字、40行、変数8個、複数変数を含む制約8個までです。ノード上限は1～5,000で、厳密な算術演算が3,000,000回に達した場合も探索を停止します。端末上のバックグラウンド処理で計算し、制限時間は15秒です。JSONレポートとノードのCSVをダウンロードできます。
分枝限定法
各ノードでは単体法で線形緩和を厳密に解きます。整数変数が分数値なら、x <= floor と x >= ceiling の二つの枝に分割します。緩和問題が実行不可能な場合、または既知の最良整数点を上回れない場合、そのノードを枝刈りします。方法: Wolsey, Integer Programming 第2版、第7章 (2020)。
証明済みの意味
すべてのノードを解くか厳密な境界で枝刈りできた場合、現在の最良実行可能解の最適性、または問題の実行不可能性が証明されます。ノード上限またはステップ予算によって探索が先に停止した場合、現在の最良解はそれまでに見つかった最良点にすぎません。レポートには最良境界とその差を示します。
入力規則
integer x, y のように指定した変数以外は連続変数として扱います。指定した変数は整数です。一変数の制約は上下限になります。緩和問題が非有界の場合、整数計画問題も非有界または実行不可能となる可能性があるため、探索を停止します。