最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

intlinprog

混合整数線形計画法 (MILP)

構文

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(___)

説明

混合整数線形計画法ソルバー。

以下で指定された問題の最小値を見つけます。

$$\underset{x}{\min }{f}^{T}x\text{ subject to }\{\begin{array}{l}x(\text{intcon})\text{ are integers}\hfill \\ A\cdot x\le b\hfill \\ Aeq\cdot x=beq\hfill \\ lb\le x\le ub.\hfill \end{array}$$

f、x、intcon、b、beq、lb、ub はベクトル、A と Aeq は行列です。

f、intcon、lb および ub をベクトルまたは配列として指定することができます。詳細は、行列引数を参照してください。

メモ

intlinprog は、ソルバーベースのアプローチのみに適用されます。2 つの最適化アプローチの詳細については、はじめに問題ベース アプローチまたはソルバーベース アプローチを選択を参照してください。

x = intlinprog(f,intcon,A,b) は、intcon の x 要素が整数、および A*x ≤ b を条件として最小の f'*x を解きます。

x = intlinprog(f,intcon,A,b,Aeq,beq) は、等式制約 Aeq*x = beq を満たしながら上記の問題を解きます。不等式が存在しない場合は A = [] および b = [] と設定してください。

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub) は、解が常に lb ≤ x ≤ ub の範囲に存在するように、設計変数 x に上限と下限を定義します。等式が存在しない場合には Aeq = [] および beq = [] と設定してください。

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0) は、初期実行可能点 x0 を使って最適化します。範囲が存在しない場合には lb = [] および ub = [] と設定してください。

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options) は、options で指定された最適化オプションを使って最小化します。optimoptions を使用してこれらのオプションを設定してください。初期点が存在しない場合は x0 = [] と設定してください。

x = intlinprog(problem) は problem 構造体を使用してすべてのソルバーの入力をカプセル化します。mpsread を使用して MPS ファイルから problem 構造体をインポートできます。prob2struct を使用して OptimizationProblem オブジェクトから構造体 problem を作成することもできます。

[x,fval,exitflag,output] = intlinprog(___) は、上述の任意の入力引数に対して、fval = f'*x、終了条件を示す値 exitflag および最適化プロセスに関する情報を含む構造体 output を返します。

例

線形不等式を使用して MILP を解く

問題を解く

$$\underset{x}{\min }8x_1+x_{2}subjectto\{\begin{array}{l}{x}_{2}isaninteger\\ x_1+2x_2\ge -14\\ -4x_1-x_2\le -33\\ 2x_1+x_2\le 20.\end{array}$$

目的関数ベクトルと整数変数のベクトルを記述します。

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 を解く

問題を解く

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12.\end{array}$$

目的関数ベクトルと整数変数のベクトルを記述します。

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 = 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 1591.000000.                                                      

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
   10000      0.71         0              -              -                                          
   18027      1.18         1   2.906000e+03   4.509804e+01                                          
   21859      1.49         2   2.073000e+03   2.270974e+01                                          
   23546      1.61         3   1.854000e+03   1.180593e+01                                          
   24121      1.65         3   1.854000e+03   1.563342e+00                                          
   24294      1.66         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 1591.000000.                                                      
                   Relative gap is 59.20%.                                                         

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
    3627      0.41         2   2.154000e+03   2.593968e+01                                          
    5844      0.56         3   1.854000e+03   1.180593e+01                                          
    6204      0.59         3   1.854000e+03   1.455526e+00                                          
    6400      0.61         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 を解く

問題を解く

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12\end{array}$$

反復表示を使用しません。

ソルバーの入力を指定します。

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 を解く

この例では、問題ベースのアプローチを使用して問題を設定し、次にソルバーベースのアプローチを使用してその問題を解く方法を示します。問題は、次のとおりです。

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12\end{array}$$

この問題を表す、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 を呼び出して、解の詳細とプロセスを確認します。

目標は次の問題を解くことです。

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_2+x_3=12.\end{array}$$

ソルバーの入力を指定します。

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 つの指標になります。

入力引数

f — 係数ベクトル

実数ベクトル | 実数配列

係数ベクトル。実数ベクトルまたは実数配列として指定されます。係数ベクトルは、目的関数 f'*x を表します。表記では、f は列ベクトルを前提としていますが、行ベクトルまたは配列を自由に使用できます。linprog は配列 f を列ベクトル f(:) に内部的に変換します。

f = [] を指定すると、intlinprog は、目的関数の最小化を試みることなく実行可能点を見つけようとします。

例: f = [4;2;-1.7];

データ型: double

intcon — 整数制約のベクトル

整数のベクトル

整数制約のベクトルは正の整数のベクトルとして指定されます。intcon の値は、整数値である決定変数 x の要素を示します。intcon は 1 ～ numel(f) の値をもちます。

intcon は配列とすることもできます。intlinprog は配列 intcon をベクトル intcon(:) に内部的に変換します。

例: intcon = [1,2,7] は x(1)、x(2)、x(7) が整数値のみを取ることを意味します。

データ型: double

A — 線形不等式制約行列

実数行列

線形不等式制約行列。double 型の行列として指定します。A は制約 A*x ≤ b の線形係数を表します。A は M 行 N 列のサイズをもちます。ここで、M は制約の数、N = numel(f) です。メモリを節約するために、A はスパースでもかまいません。

例: A = [4,3;2,0;4,-1]; は、2 つの決定変数 (2 列) 対する 3 つの線形不等式 (3 行) を意味します。

データ型: double

b — 線形不等式制約ベクトル

実数ベクトル

線形不等式制約ベクトル。double 型のベクトルとして指定します。b は、制約 A*x ≤ b の定数ベクトルを表します。b は長さ M をもちます。ここで、A は M 行 N 列です。

例: [4,0]

データ型: double

Aeq — 線形等式制約行列

[] (既定値) | 実数行列

線形等式制約行列。double 型の行列として指定します。Aeq は制約 Aeq*x = beq の線形係数を表します。Aeq は Meq 行 N 列のサイズをもちます。ここで、Meq は制約の数、N = numel(f) です。メモリを節約するために、Aeq はスパースでもかまいません。

例: A = [4,3;2,0;4,-1]; は、2 つの決定変数 (2 列) 対する 3 つの線形不等式 (3 行) を意味します。

データ型: double

beq — 線形等式制約ベクトル

[] (既定値) | 実数ベクトル

線形等式制約ベクトル。double 型のベクトルとして指定します。beq は、制約 Aeq*x = beq の定数ベクトルを表します。beq は長さ Meq をもちます。ここで、Aeq は Meq 行 N 列です。

例: [4,0]

データ型: double

lb — 下限

[] (既定値) | 実数ベクトルまたは配列

下限。double 型のベクトルまたは配列として指定します。lb は lb ≤ x ≤ ub の要素ごとの下限を表します。

intlinprog は配列 lb をベクトル lb(:) に内部的に変換します。

例: lb = [0;-Inf;4] は x(1) ≥ 0, x(3) ≥ 4 を意味します。

データ型: double

ub — 上限

[] (既定値) | 実数ベクトルまたは配列

上限。double 型のベクトルまたは配列として指定します。ub は lb ≤ x ≤ ub の要素ごとの上限を表します。

intlinprog は配列 ub をベクトル ub(:) に内部的に変換します。

例: ub = [Inf;4;10] は x(2) ≤ 4, x(3) ≤ 10 を意味します。

データ型: double

x0 — 初期点

[] (既定値) | 実数配列

初期点。実数配列として指定します。f が存在する場合、x0 の要素数は f の要素数と等しくなります。それ以外の場合、数は A または Aeq の列数と同じです。ソルバーは配列 x0 をベクトル x0(:) に内部的に変換します。

x0 を指定すると、intlinprog が収束に要する時間が変わる場合があります。x0 がソルバーに及ぼす影響を予測することは困難です。x0 と一緒に適切な Heuristics を使用する方法については、ヒントを参照してください。

x0 は、すべての制約に関して実行可能でなければなりません。x0 が実行不可能な場合、ソルバーでエラーが発生します。実行可能な x0 がない場合は、x0 = [] と設定します。

例: x0 = 100*rand(size(f))

データ型: double

options — intlinprog のオプション

optimoptions を使用して作成されたオプション

intlinprog のオプションは optimoptions の出力として指定されます。

一部のオプションは、optimoptions に表示されません。このようなオプションは、次の表ではイタリックで示されています。詳細は、表示オプションを参照してください。

オプション	説明	既定の設定
AbsoluteGapTolerance	非負の実数。intlinprog は、オブジェクト関数で内部的に計算された上限 (U) と下限 (L) の範囲の差が AbsoluteGapTolerance 以下の場合に停止します。 U – L <= AbsoluteGapTolerance	0
BranchRule	分枝の要素を選択するルール: 'maxpscost' — 最大擬似コストをもつ分数要素。詳細は、分枝限定法を参照してください。 'strongpscost' — 最大擬似コストをもつ分数要素。擬似コストは 'maxpscost' より正確に見積もられます。詳細は、分枝限定法を参照してください。 'reliability' — 最大擬似コストをもつ分数要素。擬似コストは 'strongpscost' よりさらに正確に見積もられます。詳細は、分枝限定法を参照してください。 'mostfractional' — 小数部が 1/2 に最も近い要素。 'maxfun' — 目的ベクトル f の絶対値の最大の対応する要素をもつ分数要素。	'reliability'
ConstraintTolerance	線形制約を満たすことができ、満たしていると見なされる最大の不一致である 1e-9 ～ 1e-3 の実数。ConstraintTolerance は停止条件ではありません。	1e-4
CutGeneration	カット生成のレベル (詳細はカットの生成を参照): 'none' — カットを生成しない。CutMaxIterations を不要にします。 'basic' — 通常のカットを生成。 'intermediate' — より多くのカットのタイプを使用。 'advanced' — 最も多くのカットのタイプを使用。	'basic'
CutMaxIterations	分枝限定段階に入る前にすべてのカット生成方法を経由するパスの数は 1 ～ 50 の整数です。CutGeneration オプションを 'none' に設定してカット生成を無効にします。	10
Display	表示レベル (反復表示を参照): 'off' または 'none' — 反復表示を使用しない 'final' — 最終値のみを表示する 'iter' — 反復表示を使用する	'iter'
Heuristics	実行可能点を検索するアルゴリズム (実行可能解を求めるためのヒューリスティックな方法を参照): 'basic' 'intermediate' 'advanced' 'rss' 'rins' 'round' 'diving' 'rss-diving' 'rins-diving' 'round-diving' 'none'	'basic'
HeuristicsMaxNodes	ノードの数を制限する厳密に正の整数。intlinprog は分枝限定検索によって実行可能点を探索することができます。'rss' および 'rins' にのみ適用されます。詳細は、実行可能解を求めるためのヒューリスティックな方法を参照してください。	50
IntegerPreprocess	整数前処理のタイプ (混合整数計画法の前処理を参照): 'none' — ごくわずかの整数前処理手順を使用。 'basic' — 適度な数の整数前処理手順を使用。 'advanced' — 利用可能なすべての整数前処理手順を使用。	'basic'
IntegerTolerance	1e-6 ～ 1e-3 の実数 (解 x の要素が整数をもつことができ、整数値と見なされる整数からの最大偏差)。IntegerTolerance は停止条件ではありません。	1e-5
LPMaxIterations	厳密に正の整数である分枝限定プロセス時のノードあたりシンプレックス アルゴリズム反復の最大数。	max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables)) この式では、numberOfEqualities は Aeq の行数を意味し、numberOfInequalities は A の行数を意味し、さらに、numberOfVariables は f の要素数を意味しています。
LPOptimalityTolerance	被約費用がそこで、基底に取り込まれる変数の LPOptimalityTolerance を超えなければならない、非負の実数。	1e-7
LPPreprocess	緩和された線形計画法の解に対する前処理のタイプ (線形計画法の前処理を参照) 'none' — 前処理を使用しない。 'basic' — 前処理を使用。	'basic'
MaxNodes	intlinprog が分枝限定プロセスで探索するノードの最大数である厳密に正の整数。	1e7
MaxFeasiblePoints	厳密に正の整数。MaxFeasiblePoints 整数実行可能点を見つけると、intlinprog は停止します。	Inf
MaxTime	intlinprog が実行する最大時間 (秒単位) である正の実数。	7200
NodeSelection	次に探索するノードを選択します。 'simplebestproj' — 最良の投影。詳細は、分枝限定法を参照してください。 'minobj' — 最小オブジェクト関数をもつノードを探索。 'mininfeas' — 実行不可能な整数の最小合計値をもつノードを探索。詳細は、分枝限定法を参照してください。	'simplebestproj'
ObjectiveCutOff	-Inf より大きい実数。分枝限定法の計算時に、線形計画法の解が ObjectiveCutOff を超える目的値をもつ場合、intlinprog はノードを破棄します。	Inf
ObjectiveImprovementThreshold	非負の実数。intlinprog は、少なくとも ObjectiveImprovementThreshold の下限である目的関数値をもつ別の実行可能解を検出した場合にのみ現在の実行可能解を変更します。(fold – fnew)/(1 + |fold|) > ObjectiveImprovementThreshold	0
OutputFcn	最適化関数がイベントで呼び出す 1 つ以上の関数を、'savemilpsolutions'、関数ハンドルまたは関数ハンドルの cell 配列として指定します。カスタム出力関数の場合は、関数ハンドルを渡します。 'savemilpsolutions' は、整数実行可能点をワークスペースにある行列 xIntSol に収集します。行列の各列が 1 つの整数実行可能点を表します。 カスタム出力関数の記述については、intlinprog の出力関数とプロット関数の構文を参照してください。	[]
PlotFcn	アルゴリズムが実行中のさまざまな進行状況の測定値をプロットします。事前定義されたプロットから選択するか、独自のコードを記述してください。'optimplotmilp'、関数ハンドル、または関数ハンドルの cell 配列を渡します。カスタム プロット関数の場合は、関数ハンドルを渡します。既定の設定はなし ([]) です。 'optimplotmilp' は、解の目的値について内部計算された上限と下限をプロットします。 カスタム プロット関数の記述については、intlinprog の出力関数とプロット関数の構文を参照してください。	[]
RelativeGapTolerance	0 ～ 1 の実数。intlinprog は、オブジェクト関数で内部的に計算された上限 (U) と下限 (L) の範囲の相対差が RelativeGapTolerance 以下の場合に停止します。 (U – L) / (abs(U) + 1) <= RelativeGapTolerance intlinprog は大きさ L が大きい場合に許容誤差を自動的に変更します。 許容誤差 = min(1/(1+|L|), RelativeGapTolerance) メモ RelativeGapTolerance を 10 進数として指定しても、反復表示と output.relativegap はそのギャップをパーセントでレポートします。これは、測定された相対ギャップの 100 倍であることを意味します。終了メッセージが相対ギャップを示している場合、この値は測定された相対ギャップで、割合ではありません。	1e-4
RootLPAlgorithm	線形計画法を解くアルゴリズム: 'dual-simplex' — 双対シンプレックス アルゴリズム 'primal-simplex' — 主シンプレックス アルゴリズム	'dual-simplex'
RootLPMaxIterations	初期線形計画問題を解くためのシンプレックス アルゴリズム反復の最大数である非負の整数。	max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables)) この式では、numberOfEqualities は Aeq の行数を意味し、numberOfInequalities は A の行数を意味し、さらに、numberOfVariables は f の要素数を意味しています。

例: options = optimoptions('intlinprog','MaxTime',120)

problem — 入力とオプションをカプセル化する構造体

構造体

以下のフィールドで指定された、入力とオプションをカプセル化する構造体。

f	目的関数 f'*x を表すベクトル (必須)
intcon	整数値を取る変数を示すベクトル (必須)
Aineq	線形不等式制約 Aineq*x ≤ bineq の行列
bineq	線形不等式制約 Aineq*x ≤ bineq のベクトル
Aeq	線形等式制約 Aeq*x = beq の行列
beq	線形等式制約 Aeq*x = beq のベクトル
lb	下限のベクトル
ub	上限のベクトル
x0	初期実行可能点
solver	'intlinprog' (必須)
options	optimoptions を使用して作成されたオプション (必須)

少なくとも以下のフィールドを問題の構造体で指定しなければなりません。その他のフィールドはオプションです。

• f

• intcon

• solver

• options

例: problem.f = [1,2,3];
problem.intcon = [2,3];
problem.options = optimoptions('intlinprog');
problem.Aineq = [-3,-2,-1];
problem.bineq = -20;
problem.lb = [-6.1,-1.2,7.3];
problem.solver = 'intlinprog';

データ型: struct

出力引数

x — 解

実数ベクトル

すべての範囲、整数制約、線形制約に従って f'*x を最小化するベクトルとして返された解。

問題が実行不可能または非有界の場合、x は [] です。

fval — 目的値

実数スカラー

解 x でスカラー値 f'*x として返された目的値。

問題が実行不可能または非有界の場合、fval は [] です。

exitflag — アルゴリズムの停止条件

整数

アルゴリズムの停止条件。アルゴリズムの停止理由を識別する整数として返されます。exitflag の値と intlinprog が停止した対応する理由を以下に示します。

3	解は、相対許容誤差 ConstraintTolerance に関しては実行可能ですが、絶対許容誤差に関しては実行不可能です。
2	intlinprog が途中で停止しました。整数実行可能点が検出されました。
1	intlinprog が解 x に収束しました。
0	intlinprog が途中で停止しました。整数実行可能点は検出されませんでした。
-1	intlinprog が出力関数またはプロット関数によって停止しました。
-2	実行可能点が検出されませんでした。
-3	ルート LP 問題が非有界です。
-9	ソルバーが実行可能性を失いました。

終了メッセージは、許容誤差の超過など、intlinprog が停止した理由に関する情報をより詳細に提供します。

終了フラグ 3 と -9 は、実行可能性が大きい解に関連しています。これらは通常、条件数が大きい線形制約行列、または大きな解の成分を含む問題から生じます。これらの問題を修正するには、係数行列のスケーリング、冗長な線形制約の除去、または変数に対するより狭い範囲の指定を試します。

output — 解法プロセスの概要

構造体

最適化プロセスに関する情報を含む構造体として返された解法プロセスの概要。

relativegap	intlinprog が分枝限定アルゴリズムで計算する目的関数の上限 (U) と下限 (L) の範囲の相対割合差。 relativegap = 100*(U - L) / (abs(U) + 1) intcon = [] の場合、relativegap = [] です。 メモ RelativeGapTolerance を 10 進数として指定しても、反復表示と output.relativegap はそのギャップをパーセントでレポートします。これは、測定された相対ギャップの 100 倍であることを意味します。終了メッセージが相対ギャップを示している場合、この値は測定された相対ギャップで、割合ではありません。
absolutegap	intlinprog が分枝限定アルゴリズムで計算する目的関数の上限と下限の差。 intcon = [] の場合、absolutegap = [] です。
numfeaspoints	検出された整数実行可能点の数です。 intcon = [] の場合、numfeaspoints = [] です。また、初期の緩和された問題が実行不可能な場合、numfeaspoints = [] です。
numnodes	分枝限定アルゴリズムのノードの数。前処理中または初期カット中に解が見つかった場合、numnodes = 0 です。 intcon = [] の場合、numnodes = [] です。
constrviolation	違反された制約について明らかな制約違反。 constrviolation = max([0; norm(Aeq*x-beq, inf); (lb-x); (x-ub); (Ai*x-bi)])
message	終了メッセージ。

制限

• 通常、解 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 を指定する場合には、'Heuristics' オプションを 'rins-diving' に設定するか、'rins' を使用する別の設定にすることによって、良好な結果を得ることができます。

• 整数要素、つまり整数を示す 1 をもつバイナリ ベクトルの論理インデックスを提供するには、find を使用して intcon 形式に変換します。たとえば、

  logicalindices = [1,0,0,1,1,0,0];
  intcon = find(logicalindices)

  intcon =
  
       1     4     5

• bintprog は 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)

互換性の考慮事項

既定の BranchRule は 'reliability'

R2019a での動作変更

BranchRule オプションの既定値は 'maxpscost' ではなく 'reliability' です。テストでは、この値を使用することで、多くの問題で求解にかかる時間と探索される分岐ノード数の両方に関するパフォーマンスが向上します。

いくつかの問題では、以前の分岐ルールの方が優れたパフォーマンスを示します。以前の動作にするには、BranchRule オプションを 'maxpscost' に設定します。

参考

linprog | mpsread | optimoptions | prob2struct

トピック

• 混合整数線形計画法の基礎: ソルバーベース
• 工場、倉庫、販売店割り当てモデル: ソルバーベース
• 巡回セールスマン問題: ソルバーベース
• 整数計画法により数独パズルを解く: ソルバーベース
• 混合整数二次計画法ポートフォリオ最適化問題: ソルバーベース
• 発電機の最適な運転スケジュール: ソルバーベース
• 混合整数線形計画法アルゴリズム
• 整数線形計画法の調整
• ソルバーベースの最適化問題の設定

R2014a で導入

×

例を開く

この例の変更されたバージョンがシステム上にあります。代わりにこのバージョンを開きますか?

いいえ、変更されたバージョンを上書きします。 はい