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

説明

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

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

$\min_{x} f^{T} x subject to {\begin{array}{l} x (intcon) are integers \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b . \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 を解く

ライブスクリプトを開く

問題を解く

$\min_{x} 8 x_{1} + x_{2} s u b j e c t t o {\begin{array}{llllllllllllllllllll} x_{2} i s a n i n t e g e r \\ x_{1} + 2 x_{2} \geq - 14 \\ - 4 x_{1} - x_{2} \leq - 33 \\ 2 x_{1} + x_{2} \leq 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)

Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
3 rows, 2 cols, 6 nonzeros
3 rows, 2 cols, 6 nonzeros

Solving MIP model with:
   3 rows
   2 cols (0 binary, 1 integer, 0 implied int., 1 continuous)
   6 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -inf            inf                  inf        0      0      0         0     0.0s
 T       0       0         0   0.00%   -inf            59                 Large        0      0      0         3     0.0s

Solving report
  Status            Optimal
  Primal bound      59
  Dual bound        59
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    59 (objective)
                    0 (bound viol.)
                    1.7763568394e-15 (int. viol.)
                    0 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             1
  LP iterations     3 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.

すべてのタイプの制約を使用して MILP を解く

ライブスクリプトを開く

問題を解く

$\min_{x} (- 3 x_{1} - 2 x_{2} - x_{3}) s u b j e c t t o {\begin{array}{llllllllllllllllllll} x_{3} b i n a r y \\ x_{1}, x_{2} \geq 0 \\ x_{1} + x_{2} + x_{3} \leq 7 \\ 4 x_{1} + 2 x_{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)

Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
2 rows, 3 cols, 6 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal

Solving report
  Status            Optimal
  Primal bound      -12
  Dual bound        -12
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    -12 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.

初期点の使用

ライブスクリプトを開く

初期実行可能点がある場合とない場合の両方について整数計画問題を解くためのステップ数を比較します。問題には 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);

Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
4 rows, 8 cols, 32 nonzeros
4 rows, 8 cols, 27 nonzeros
Objective function is integral with scale 1

Solving MIP model with:
   4 rows
   8 cols (0 binary, 8 integer, 0 implied int., 0 continuous)
   27 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   0               inf                  inf        0      0      0         0     0.0s
         0       0         0   0.00%   1554.047531     inf                  inf        0      0      4         4     0.0s
 T   20753     210      8189  98.04%   1783.696925     1854               3.79%       30      8   9884     19222     2.8s

Solving report
  Status            Optimal
  Primal bound      1854
  Dual bound        1854
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    1854 (objective)
                    0 (bound viol.)
                    9.63673585375e-14 (int. viol.)
                    0 (row viol.)
  Timing            2.85 (total)
                    0.01 (presolve)
                    0.00 (postsolve)
  Nodes             21163
  LP iterations     19608 (total)
                    223 (strong br.)
                    76 (separation)
                    1018 (heuristics)

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.

比較するため、初期実行可能点を使用して解を求めます。

x0 = [8 62 23 103 53 84 46 34];
[x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);

Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Solution has               num          max          sum
Col     infeasibilities      0            0            0
Integer infeasibilities      0            0            0
Row     infeasibilities      0            0            0
Row     residuals            0            0            0
Presolving model
4 rows, 8 cols, 32 nonzeros
4 rows, 8 cols, 27 nonzeros

MIP start solution is feasible, objective value is 3901
Objective function is integral with scale 1

Solving MIP model with:
   4 rows
   8 cols (0 binary, 8 integer, 0 implied int., 0 continuous)
   27 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   0               3901             100.00%        0      0      0         0     0.0s
         0       0         0   0.00%   1554.047531     3901              60.16%        0      0      4         4     0.0s
 T    6266     708      2644  73.61%   1662.791423     3301              49.63%       20      6   9746     10699     1.3s
 T    9340     919      3970  80.72%   1692.410008     2687              37.01%       29      6   9995     16120     2.0s
 T   21750     192      9514  96.83%   1791.542628     1854               3.37%       20      6   9984     40278     4.9s

Solving report
  Status            Optimal
  Primal bound      1854
  Dual bound        1854
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    1854 (objective)
                    0 (bound viol.)
                    1.42108547152e-13 (int. viol.)
                    0 (row viol.)
  Timing            4.97 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             22163
  LP iterations     40863 (total)
                    538 (strong br.)
                    64 (separation)
                    2782 (heuristics)

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.

初期点がない場合、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)

問題ベースのアプローチを使用して 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)

Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
2 rows, 3 cols, 6 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal

Solving report
  Status            Optimal
  Primal bound      -12
  Dual bound        -12
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    -12 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.

fval = -12

exitflag = 1

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: []
           numnodes: 0
    constrviolation: 0
          algorithm: 'highs'
            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)

Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
2 rows, 3 cols, 6 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal

Solving report
  Status            Optimal
  Primal bound      -12
  Dual bound        -12
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    -12 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.

fval = -12

exitflag = 1

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: []
           numnodes: 0
    constrviolation: 0
          algorithm: 'highs'
            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` — 線形不等式制約
実数行列

実数行列として指定される線形不等式制約です。A は M 行 N 列の行列で、M は不等式の数、N は変数の数 (f の長さ) です。大規模な問題の場合は、A をスパース行列として渡します。

A は M 個の線形不等式を符号化します。

A*x <= b,

ここで、x は N 個の変数 x(:) の列ベクトル、b は M 個の要素をもつ列ベクトルです。

たとえば、次の不等式を考えてみましょう。

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30.

次の制約を入力することによって、不等式を指定します。

A = [1,2;3,4;5,6];
b = [10;20;30];

例: x 成分の和が 1 以下になるように指定するために、A = ones(1,N) と b = 1 をとります。

データ型: double

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

実数ベクトルで指定される線形不等式制約です。b は、行列 A に関連する M 要素ベクトルです。b を行ベクトルとして渡す場合、ソルバーは b を列ベクトル b(:) に内部的に変換します。大規模な問題の場合は、b をスパースベクトルとして渡します。

b は M 個の線形不等式を符号化します。

A*x <= b,

ここで、x は N 個の変数 x(:) の列ベクトル、A は M 行 N 列の行列です。

たとえば、次の不等式を考えてみましょう。

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30.

次の制約を入力することによって、不等式を指定します。

A = [1,2;3,4;5,6];
b = [10;20;30];

例: x の成分の和が 1 以下であることを指定するには、A = ones(1,N) と b = 1 を使用します。

データ型: double

`Aeq` — 線形等式制約
実数行列

実数行列として指定される線形等式制約です。Aeq は Me 行 N 列の行列で、Me は等式の数、N は変数の数 (f の長さ) です。大規模な問題の場合は、Aeq をスパース行列として渡します。

Aeq は Me 個の線形等式を符号化します。

Aeq*x = beq,

ここで、x は N 個の変数 x(:) の列ベクトル、beq は Me 個の要素をもつ列ベクトルです。

たとえば、次の等式を考えてみましょう。

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

次の制約を入力することによって、等式を指定します。

Aeq = [1,2,3;2,4,1];
beq = [10;20];

例: x 成分の和が 1 になるように指定するために、Aeq = ones(1,N) と beq = 1 をとります。

データ型: double

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

実数ベクトルで指定される線形等式制約です。beq は、行列 Aeq に関連する Me 要素ベクトルです。beq を行ベクトルとして渡す場合、ソルバーは beq を列ベクトル beq(:) に内部的に変換します。大規模な問題の場合は、beq をスパースベクトルとして渡します。

beq は Me 個の線形等式を符号化します。

Aeq*x = beq,

ここで、x は N 個の変数 x(:) の列ベクトル、Aeq は Me 行 N 列の行列です。

たとえば、次の等式を考えてみましょう。

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

次の制約を入力することによって、等式を指定します。

Aeq = [1,2,3;2,4,1];
beq = [10;20];

例: x の成分の和が 1 であることを指定するには、Aeq = ones(1,N) と beq = 1 を使用します。

データ型: 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 を使用する方法については、ヒントを参照してください。

"legacy" アルゴリズムの場合、x0 はすべての制約に関して実行可能でなければなりません。x0 が実行可能でない場合、ソルバーで警告が表示されて x0 が無視されます。このアルゴリズムに対して実行可能な x0 がない場合は、x0 = [] と設定します。

"highs" アルゴリズムは、与えられたすべての x0 の使用を試み、必要に応じて点を変更し実行可能にします。

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

データ型: double

`options` — `intlinprog` のオプション
`optimoptions` を使用して作成されたオプション

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

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

すべてのアルゴリズム
オプション	説明	既定の設定
`AbsoluteGapTolerance`	非負の実数。`intlinprog` は、オブジェクト関数で内部的に計算された上限 (`U`) と下限 (`L`) の範囲の差が `AbsoluteGapTolerance` 以下の場合に停止します。 `U – L <= AbsoluteGapTolerance`.	`"highs"` では `1e-6`、`"legacy"` では `0`
`Algorithm`	最適化アルゴリズムを選択します。 `"highs"` (既定の設定) `"legacy"`	`"highs"`
`ConstraintTolerance`	`"highs"` アルゴリズムの場合、整数制約または線形制約の許容される最大の違反を表す `1e-10` ～ `1e-3` の実数値。 `"legacy"` アルゴリズムの場合、線形制約を満たすことができ、満たしていると見なされる最大の不一致である `1e-10` ～ `1e-3` の実数値。 `ConstraintTolerance` は停止条件ではありません。	`"highs"` では `1e-6`、`"legacy"` では `1e-4`
`Display`	表示レベル (反復表示を参照): `"off"` または `"none"` — 反復表示を使用しない `"final"` — 最終値のみを表示する `"iter"` — 反復表示を使用する	`"iter"`
`MaxNodes`	`intlinprog` が分枝限定プロセスで探索するノードの最大数である厳密に正の整数。	`1e7`
`MaxTime`	`intlinprog` の最大実行時間 (秒単位) である非負の実数。	`7200`
`ObjectiveCutOff`	`-Inf` より大きい実数。分枝限定法の計算時に、線形計画法の解が `ObjectiveCutOff` を超える目的値をもつ場合、`intlinprog` はノードを破棄します。	`Inf`
`RelativeGapTolerance`	`0` ～ `1` の実数。`intlinprog` は、オブジェクト関数で内部的に計算された上限 (`U`) と下限 (`L`) の範囲の相対差が `RelativeGapTolerance` 以下の場合に停止します。 `"highs"` アルゴリズムでは、停止テストは次のようになります。 `(U – L)/\|U\| <= RelativeGapTolerance`. `U` = 0 で `L` = 0 の場合、返される比 `(U – L)/\|U\|` は 0 です。`U` = 0 で `L` が 0 でない場合、返される比は `Inf` です。 `"legacy"` アルゴリズムでは、停止テストは次のようになります。 `(U – L)/(\|U\| + 1) <= RelativeGapTolerance`. メモ `RelativeGapTolerance` を 10 進数として指定しても、反復表示はそのギャップをパーセントでレポートします。これは、測定された相対ギャップの 100 倍であることを意味します。終了メッセージが相対ギャップを示している場合、この値は測定された相対ギャップで、割合ではありません。	`1e-4`
レガシアルゴリズム
`BranchRule`	分枝の要素を選択するルール: `'maxpscost'` — 最大擬似コストをもつ分数要素。詳細については、分枝限定法を参照してください。 `'strongpscost'` — 最大擬似コストをもつ分数要素。擬似コストは `'maxpscost'` より正確に見積もられます。詳細については、分枝限定法を参照してください。 `'reliability'` — 最大擬似コストをもつ分数要素。擬似コストは `'strongpscost'` よりさらに正確に見積もられます。詳細については、分枝限定法を参照してください。 `'mostfractional'` — 小数部が `1/2` に最も近い要素。 `'maxfun'` — 目的ベクトル `f` の絶対値の最大の対応する要素をもつ分数要素。	`'reliability'`
`CutGeneration`	カット生成のレベル (詳細についてはカットの生成を参照): `'none'` — カットを生成しない。`CutMaxIterations` を不要にします。 `'basic'` — 通常のカットを生成。 `'intermediate'` — より多くのカットのタイプを使用。 `'advanced'` — 最も多くのカットのタイプを使用。	`'basic'`
`CutMaxIterations`	分枝限定段階に入る前にすべてのカット生成方法を経由するパスの数は `1` ～ `50` の整数です。`CutGeneration` オプションを `'none'` に設定してカット生成を無効にします。	`10`
`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-10` ～ `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'`
`MaxFeasiblePoints`	厳密に正の整数。`MaxFeasiblePoints` 整数実行可能点を見つけると、`intlinprog` は停止します。	`Inf`
`NodeSelection`	次に探索するノードを選択します。 `'simplebestproj'` — 最良の投影。詳細については、分枝限定法を参照してください。 `'minobj'` — 最小オブジェクト関数をもつノードを探索。 `'mininfeas'` — 実行不可能な整数の最小合計値をもつノードを探索。詳細については、分枝限定法を参照してください。	`'simplebestproj'`
`ObjectiveImprovementThreshold`	非負の実数。`intlinprog` は、少なくとも `ObjectiveImprovementThreshold` の下限である目的関数値をもつ別の実行可能解を検出した場合にのみ現在の実行可能解を変更します。(fold – fnew)/(1 + \|fold\|) > ObjectiveImprovementThreshold	`0`
`OutputFcn`	イベントで最適化関数が呼び出す 1 つ以上の関数。`'savemilpsolutions'`、関数ハンドル、または関数ハンドルの cell 配列として指定します。カスタム出力関数の場合は、関数ハンドルを渡します。出力関数はソルバーを停止できます。 `'savemilpsolutions'` は、整数実行可能点をワークスペースにある行列 `xIntSol` に収集します。行列の各列が 1 つの整数実行可能点を表します。カスタム出力関数の記述については、intlinprog の出力関数とプロット関数の構文を参照してください。	`[]`
`PlotFcn`	アルゴリズムが実行中のさまざまな進行状況の測定値をプロットします。事前定義されたプロットから選択するか、独自のコードを記述してください。`'optimplotmilp'`、関数ハンドル、または関数ハンドルの cell 配列を渡します。カスタムプロット関数の場合は、関数ハンドルを渡します。既定の設定はなし (`[]`) です。 `'optimplotmilp'` は、解の目的値について内部計算された上限と下限をプロットします。カスタムプロット関数の記述については、intlinprog の出力関数とプロット関数の構文を参照してください。	`[]`
`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`	`"legacy"` アルゴリズムの場合は `intlinprog` が分枝限定アルゴリズムで計算する目的関数の上限 (`U`) と下限 (`L`) の相対割合差、`"highs"` アルゴリズムの場合は相対差。具体的には次のようになります。 `"legacy"` アルゴリズムの場合は `relativegap = 100*(U - L) / (abs(U) + 1)` `"highs"` アルゴリズムの場合は `relativegap = (U - L) / abs(U)` `intcon = []` の場合、`relativegap = []` です。メモ `RelativeGapTolerance` を 10 進数として指定しても、反復表示はそのギャップをパーセントでレポートします。これは、測定された相対ギャップの 100 倍であることを意味します。終了メッセージが相対ギャップを示している場合、この値は測定された相対ギャップで、割合ではありません。
`absolutegap`	`intlinprog` が分枝限定アルゴリズムで計算する目的関数の上限と下限の差。 `intcon = []` の場合、`absolutegap = []` です。
`numfeaspoints`	検出された整数実行可能点の数です。 `"highs"` アルゴリズムの場合は `numfeaspoints = []` です。`intcon = []` の場合、`numfeaspoints = []` です。また、初期の緩和された問題が実行不可能な場合、`numfeaspoints = []` です。
`numnodes`	`"legacy"` アルゴリズムの場合は分枝限定アルゴリズムのノードの数。`"highs"` アルゴリズムの場合は `numnodes = []` です。前処理中または初期カット中に解が見つかった場合、`numnodes = 0` です。 `intcon = []` の場合、`numnodes = []` です。
`constrviolation`	違反された制約について明らかな制約違反。 `constrviolation = max([0; norm(Aeqx-beq, inf); (lb-x); (x-ub); (Aix-bi)])`
`message`	終了メッセージ。

制限

通常、解 x(intCon) の整数値と推定される要素は厳密に整数ではありません。intlinprog では整数の ConstraintTolerance ("legacy" アルゴリズムの場合は 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 では、絶対値が 1e20 ("legacy" アルゴリズムの場合は 1e25) を超える問題の要素 (f、b、ub の係数など) は受け入れられません。また、絶対値が 1e15 以上の線形制約行列 A および Aeq も受け入れられません。このような問題をもつ intlinprog を実行しようとすると、intlinprog でエラーが発生します。

ヒント

2 値変数を指定するには、変数がintcon で整数となるように設定し、下限に 0、上限に 1 を指定します。
スパース線形制約行列 A と Aeq を指定してメモリを節約します。ただし、b と beq にスパース行列を指定することはできません。
整数要素、つまり整数を示す 1 をもつバイナリベクトルの論理インデックスを提供するには、find を使用して intcon 形式に変換します。たとえば、
```
logicalindices = [1,0,0,1,1,0,0];
intcon = find(logicalindices)
```
```
intcon =

     1     4     5
```
このヒントは "legacy" アルゴリズムに適用されます。
x0 引数を含めると、intlinprog でより良い整数実行可能点が見つかるまで、'rins' およびガイド付きダイビングヒューリスティックでその値が使用されます。そのため、x0 を指定する場合には、'Heuristics' オプションを 'rins-diving' に設定するか、'rins' を使用する別の設定にすることによって、良好な結果を得ることができます。
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)

代替機能

アプリ

[最適化] ライブエディタータスクが intlinprog にビジュアルインターフェイスを提供します。

バージョン履歴

R2014a で導入

すべて展開する

R2024a: 新しい既定の `"highs"` アルゴリズム

intlinprog に Algorithm オプションが追加され、新しいアルゴリズムが既定のアルゴリズムとして加わりました。"highs" アルゴリズムはオープンソースの HiGHS コードに基づいています。現時点で、"highs" アルゴリズムは出力関数やプロット関数をサポートしていません。

以前のアルゴリズムを使用するには、optimoptions を使用して Algorithm="legacy" を設定します。

ConstraintTolerance オプション値の許容範囲が、どちらのアルゴリズムも 1e-10 ～ 1e-3 になりました。"legacy" アルゴリズムについては、IntegerTolerance オプション値の許容範囲も同様です。

R2019a: 既定の `BranchRule` は `'reliability'`

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

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

参考

linprog | mpsread | optimoptions | prob2struct | 最適化

intlinprog

構文

説明

例

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

すべてのタイプの制約を使用して MILP を解く

初期点の使用

既定ではないオプションを使用して MILP を解く

問題ベースのアプローチを使用して MILP を解く

MILP の解とプロセスを調べる

入力引数

f — 係数ベクトル 実数ベクトル | 実数配列

intcon — 整数制約のベクトル 整数のベクトル

A — 線形不等式制約 実数行列

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

Aeq — 線形等式制約 実数行列

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

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

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

x0 — 初期点 [] (既定値) | 実数配列

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

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

出力引数

x — 解 実数ベクトル

fval — 目的値 実数スカラー

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

output — 解法プロセスの概要 構造体

制限

ヒント

代替機能

アプリ

バージョン履歴

R2024a: 新しい既定の "highs" アルゴリズム

R2019a: 既定の BranchRule は 'reliability'

参考

トピック

`f` — 係数ベクトル
実数ベクトル | 実数配列

`intcon` — 整数制約のベクトル
整数のベクトル

`A` — 線形不等式制約
実数行列

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

`Aeq` — 線形等式制約
実数行列

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

`lb` — 下限
`[]` (既定値) | 実数ベクトルまたは配列

`ub` — 上限
`[]` (既定値) | 実数ベクトルまたは配列

`x0` — 初期点
`[]` (既定値) | 実数配列

`options` — `intlinprog` のオプション
`optimoptions` を使用して作成されたオプション

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

`x` — 解
実数ベクトル

`fval` — 目的値
実数スカラー

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

`output` — 解法プロセスの概要
構造体

R2024a: 新しい既定の `"highs"` アルゴリズム

R2019a: 既定の `BranchRule` は `'reliability'`