混合整数線形計画(MILP)

小規模の複数制約付き混合整数線形計画をブラウザ内で求解・検算する。

変数6個・制約8行まで。目的係数・係数行列・右辺は別々に入力し、同じ変数順・制約順で対応付けてください。

計算はこのブラウザ内で実行します。実行時間・演算数・探索ノード数に上限があります。

項目を入力・選択してから「計算する」を押してください。

必要な入力・選択は3項目です。

変数の種類・上下界(上から順にx1~x6)必須
行変数名区分下限上限 任意操作
1
2

4列を左端の欄へタブ区切りで貼り付けられます。6行まで。

下限は必須、上限の空欄は上限なし。二値は0と1に制限します。整数変数の小数境界は内側の整数へ切り詰めます。

改行・空白・タブで区切って入力してください。1,234は1つの数値です。6個まで。

c1、c2…を改行または空白で入力。0の係数も省略せず、変数と同じ個数を入力してください。

制約行と右辺 b(係数行列Aの行順に対応)任意
行記号右辺 b操作
1
2

2列を左端の欄へタブ区切りで貼り付けられます。8行まで。

制約なしの場合は空欄のまま。条件がある行は記号・右辺を両方入力してください。

制約係数行列 A(8行×6列・左上から使用)任意
行/列123456
1
2
3
4
5
6
7
8

制約がm行・変数がn個なら、左上m×nだけ係数を入力します。使う範囲の0も明記し、範囲外は空欄にしてください。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

最小化または最大化: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。