最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。
intlinprog
混合整数線形計画法 (MILP)
混合整数線形計画法ソルバー。
以下で指定された問題の最小値を見つけます。
f、x、intcon、b、beq、lb、ub はベクトル、A と Aeq は行列です。
f、intcon、lb および ub をベクトルまたは配列として指定することができます。詳細は、行列引数を参照してください。
メモ
intlinprog は、ソルバーベースのアプローチのみに適用されます。2 つの最適化アプローチの詳細については、はじめに問題ベース アプローチまたはソルバーベース アプローチを選択を参照してください。
構文
x = intlinprog(f,intcon,A,b)x = intlinprog(f,intcon,A,b,Aeq,beq)x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)x = intlinprog(problem)[x,fval,exitflag,output]
= intlinprog(___)説明
x = intlinprog(problem)problem 構造体を使用してすべてのソルバーの入力をカプセル化します。mpsread を使用して MPS ファイルから problem 構造体をインポートできます。prob2struct を使用して OptimizationProblem オブジェクトから構造体 problem を作成することもできます。
例
線形不等式を使用して MILP を解く
問題を解く
目的関数ベクトルと整数変数のベクトルを記述します。
f = [8;1]; intcon = 2;
"より大きい (>)" 不等式に -1 を乗算することにより、すべての不等式を A*x <= b 形式に変換します。
A = [-1,-2;
-4,-1;
2,1];
b = [14;-33;20];intlinprog を呼び出します。
x = intlinprog(f,intcon,A,b)
LP: Optimal objective value is 59.000000. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
x = 2×1
6.5000
7.0000
すべてのタイプの制約を使用して MILP を解く
問題を解く
目的関数ベクトルと整数変数のベクトルを記述します。
f = [-3;-2;-1]; intcon = 3;
線形不等式制約を記述します。
A = [1,1,1]; b = 7;
線形等式制約を記述します。
Aeq = [4,2,1]; beq = 12;
範囲制約を記述します。
lb = zeros(3,1);
ub = [Inf;Inf;1]; % Enforces x(3) is binaryintlinprog を呼び出します。
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
LP: Optimal objective value is -12.000000. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
x = 3×1
0
5.5000
1.0000
初期点の使用
初期実行可能点がある場合とない場合の両方について整数計画問題を解くためのステップ数を比較します。問題には 8 つの変数、4 つの線形等式制約があり、すべての変数が正になるように制限されています。
線形等式制約の行列とベクトルを定義します。
Aeq = [22 13 26 33 21 3 14 26
39 16 22 28 26 30 23 24
18 14 29 27 30 38 26 26
41 26 28 36 18 38 16 26];
beq = [ 7872
10466
11322
12058];すべての変数が非負となるように制限する下限を設定します。
N = 8; lb = zeros(N,1);
すべての変数が整数値であることを指定します。
intcon = 1:N;
目的関数ベクトル f を設定します。
f = [2 10 13 17 7 5 7 3];
初期点を使用せずに問題を解き、表示を調べて分枝限定ノードの数を確認します。
[x1,fval1,exitflag1,output1] = intlinprog(f,intcon,[],[],Aeq,beq,lb);
LP: Optimal objective value is 1554.047531.
Cut Generation: Applied 8 strong CG cuts.
Lower bound is 1590.479592.
Branch and Bound:
nodes total num int integer relative
explored time (s) solution fval gap (%)
10000 0.90 0 - -
10947 0.97 1 2.481000e+03 3.585818e+01
14148 1.25 2 2.073000e+03 2.319190e+01
17131 1.55 3 1.854000e+03 1.180593e+01
17777 1.60 3 1.854000e+03 0.000000e+00
Optimal solution found.
Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).
比較するため、初期実行可能点を使用して解を求めます。
x0 = [8 62 23 103 53 84 46 34]; [x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);
LP: Optimal objective value is 1554.047531.
Cut Generation: Applied 8 strong CG cuts.
Lower bound is 1590.479592.
Relative gap is 59.21%.
Branch and Bound:
nodes total num int integer relative
explored time (s) solution fval gap (%)
4535 0.56 2 2.262000e+03 2.965091e+01
6516 0.73 3 1.854000e+03 1.412399e+01
7795 0.83 3 1.854000e+03 2.695418e-01
7825 0.83 3 1.854000e+03 0.000000e+00
Optimal solution found.
Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).
初期点がない場合、
intlinprogは約 30,000 の分枝限定ステップをとる。初期点を使用する場合、
intlinprogは約 5,000 のステップをとる。
初期点を与えることが常に役立つとは限りません。この問題の場合、初期点を与えると、時間と計算ステップが節減されます。ただし、問題によっては、初期点を与えることで intlinprog がより多くのステップを必要とする場合があります。
既定ではないオプションを使用して MILP を解く
問題を解く
反復表示を使用しません。
ソルバーの入力を指定します。
f = [-3;-2;-1];
intcon = 3;
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1]; % enforces x(3) is binary
x0 = [];表示を指定しません。
options = optimoptions('intlinprog','Display','off');
ソルバーを実行します。
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)
x = 3×1
0
5.5000
1.0000
問題ベースのアプローチを使用して MILP を解く
この例では、問題ベースのアプローチを使用して問題を設定し、次にソルバーベースのアプローチを使用してその問題を解く方法を示します。問題は、次のとおりです。
この問題を表す、prob という名前の OptimizationProblem オブジェクトを作成します。2 値変数を指定するため、整数型で下限が 0、上限が 1 の最適化変数を作成します。
x = optimvar('x',2,'LowerBound',0); xb = optimvar('xb','LowerBound',0,'UpperBound',1,'Type','integer'); prob = optimproblem('Objective',-3*x(1)-2*x(2)-xb); cons1 = sum(x) + xb <= 7; cons2 = 4*x(1) + 2*x(2) + xb == 12; prob.Constraints.cons1 = cons1; prob.Constraints.cons2 = cons2;
問題オブジェクトを問題構造体に変換します。
problem = prob2struct(prob);
生成された問題構造体を解きます。
[sol,fval,exitflag,output] = intlinprog(problem)
LP: Optimal objective value is -12.000000. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
sol = 3×1
0
5.5000
1.0000
fval = -12
exitflag = 1
output = struct with fields:
relativegap: 0
absolutegap: 0
numfeaspoints: 1
numnodes: 0
constrviolation: 0
message: 'Optimal solution found....'
sol(1) と sol(3) はどちらもバイナリ値です。バイナリ最適化変数 xb に対応するのはどの値でしょう。
prob.Variables
ans = struct with fields:
x: [2x1 optim.problemdef.OptimizationVariable]
xb: [1x1 optim.problemdef.OptimizationVariable]
変数 xb は Variables で最後に表示されるため、xb が sol(3) = 1 に対応します。詳細は、アルゴリズムを参照してください。
MILP の解とプロセスを調べる
より多くの出力をもつ intlinprog を呼び出して、解の詳細とプロセスを確認します。
目標は次の問題を解くことです。
ソルバーの入力を指定します。
f = [-3;-2;-1];
intcon = 3;
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1]; % enforces x(3) is binaryすべての出力をもつ intlinprog を呼び出します。
[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
LP: Optimal objective value is -12.000000. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
x = 3×1
0
5.5000
1.0000
fval = -12
exitflag = 1
output = struct with fields:
relativegap: 0
absolutegap: 0
numfeaspoints: 1
numnodes: 0
constrviolation: 0
message: 'Optimal solution found....'
出力構造体は numnodes が 0 であることを示します。これは intlinprog が分枝前に問題を解いたことを示します。これは結果が信頼できることを示す 1 つの指標になります。また、absolutegap および relativegap フィールドも 0 です。これは結果が信頼できることを示すもう 1 つの指標になります。
入力引数
出力引数
制限
通常、解
x(intCon)の整数値と推定される要素は厳密に整数ではありません。intlinprogでは整数のIntegerTolerance内の解の値はすべて整数と見なされます。整数と推定されるすべての数値を厳密に整数に丸めるには、関数
roundを使用します。x(intcon) = round(x(intcon));
注意
丸めによって解が実行不可能になる場合があります。丸めを行った後に実行可能性をチェックします。
max(A*x - b) % See if entries are not too positive, so have small infeasibility max(abs(Aeq*x - beq)) % See if entries are near enough to zero max(x - ub) % Positive entries are violated bounds max(lb - x) % Positive entries are violated bounds
intlinprogは、絶対値が2.1e9を超える場合、解の要素に整数値を適用しません。このような要素が解に含まれる場合、intlinprogは警告を表示します。この警告が表示された場合は、解をチェックして、解の整数値と推定される要素が整数に近いかどうかを確認します。intlinprogでは、f、Aまたはubの係数など、問題の要素が絶対値の1e25を超えることはできません。このような問題をもつintlinprogを実行しようとすると、intlinprogでエラーが発生します。現在、最適化アプリ で
intlinprogを実行することはできません。
ヒント
2 値変数を指定するには、変数が
intconで整数となるように設定し、下限に0、上限に1を指定します。スパース線形制約行列
AとAeqを指定してメモリを節約します。ただし、bとbeqにスパース行列を指定することはできません。x0引数を含めると、intlinprogはその値をヒューリスティックな方法で使用します。特に、rinsやガイド付きダイビングなどの改善のためのヒューリスティックな方法は、x0から開始でき、その点を改善しようとします。そのため、x0を指定する場合は、'Heuristics'オプションを'rins-diving'に設定すると、効果的な場合があります。ただし、ギャップが小さい場合はヒューリスティックな方法は実行されないため、'rins-diving'を選択しても常に実行時間が改善されるとは限りません。整数要素、つまり整数を示す
1をもつバイナリ ベクトルの論理インデックスを提供するには、findを使用してintcon形式に変換します。たとえば、logicalindices = [1,0,0,1,1,0,0]; intcon = find(logicalindices)
intcon = 1 4 5bintprogはintlinprogに置き換えられています。古いbintprogコードをintlinprogで使用するように更新するには、次の変更を行います。intconを1:numVarsに設定します。ここで、numVarsは問題の変数の数です。lbをzeros(numVars,1)に設定します。ubをones(numVars,1)に設定します。関連するオプションを更新します。
optimoptionsを使用してintlinprogオプションを作成します。呼び出しを
bintprogに変更します。以下のようになります。[x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options) % Change your call to: [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,x0,options)
