混合整数線形計画(MILP)
バグ・不具合を報告
小規模の複数制約付き混合整数線形計画をブラウザ内で求解・検算する。
変数6個・制約8行まで。目的係数・係数行列・右辺は別々に入力し、同じ変数順・制約順で対応付けてください。
計算はこのブラウザ内で実行します。実行時間・演算数・探索ノード数に上限があります。
項目を入力・選択してから「計算する」を押してください。
必要な入力・選択は3項目です。
計算結果
—
—
- 目的値の下界
- —
- 目的値の上界
- —
- 最適性ギャップ
- —%
- 評価した探索ノード
- —個
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
最小化または最大化:cᵀx。条件:各行の∑aᵢⱼxⱼ ≦・≧・= bᵢ、各変数 lⱼ≦xⱼ≦uⱼ(上限空欄は+∞)、整数・二値条件。LP緩和は下限を移動して非負変数へ変換し、2段階単体法で解きます。整数成分が非整数の緩和解で⌊xⱼ⌋以下と⌈xⱼ⌉以上に分枝。最小化の上界は最良実行可能値、下界は未探索分枝のLP緩和値。最大化では向きが逆。ギャップ=|実行可能値−緩和境界| / max(1, |実行可能値|)。数値許容差と演算・時間・ノード上限を設け、最適性が未証明なら上限到達と表示します。
実行可能解と目的値、下界・上界、最適性ギャップ、探索区分、制約検算表。
計算例(架空の数値)
最大化 x2、整数 x1・x2≧0、制約 −x1+x2≦1、3x1+2x2≦12、2x1+3x2≦12。最適解は(x1,x2)=(1,2)、目的値2(SciPy milpの掲載例)。
適用対象と限界
有限下界を持つ、係数・境界の絶対値0または0.0000001~100000の小規模線形混合整数最適化モデル。下界が−∞の変数、半連続・半整数、非線形・二次目的、6変数超・8制約超、大規模最適化は対象外。LP緩和が非有界でも整数問題の非有界性を証明できない場合は判定保留とします。。
方法と出典
方法:E476 simplex+branch-and-bound v1.0 (2026-11-13)。データ記録日:2026-11-13。