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 or extended 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、b、beq、lb、ub はベクトル、intcon はベクトルまたは integerConstraint オブジェクト、A と Aeq は行列です。

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

メモ

intlinprog は、ソルバーベースのアプローチのみに適用されます。問題ベースのアプローチの場合は、solve を使用してください。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.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e+00, 4e+00]
  Cost   [1e+00, 8e+00]
  Bound  [0e+00, 0e+00]
  RHS    [1e+01, 3e+01]
Presolving model
3 rows, 2 cols, 6 nonzeros  0s
3 rows, 2 cols, 6 nonzeros  0s

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.01 (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.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e+00, 4e+00]
  Cost   [1e+00, 3e+00]
  Bound  [1e+00, 1e+00]
  RHS    [7e+00, 1e+01]
Presolving model
2 rows, 3 cols, 6 nonzeros  0s
0 rows, 0 cols, 0 nonzeros  0s
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.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [3e+00, 4e+01]
  Cost   [2e+00, 2e+01]
  Bound  [0e+00, 0e+00]
  RHS    [8e+03, 1e+04]
Presolving model
4 rows, 8 cols, 32 nonzeros  0s
4 rows, 8 cols, 27 nonzeros  0s
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.9s

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.92 (total)
                    0.00 (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.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [3e+00, 4e+01]
  Cost   [2e+00, 2e+01]
  Bound  [0e+00, 0e+00]
  RHS    [8e+03, 1e+04]
Assessing feasibility of MIP using primal feasibility and integrality tolerance of       1e-06
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  0s
4 rows, 8 cols, 27 nonzeros  0s

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.5s
 T    9340     919      3970  80.72%   1692.410008     2687              37.01%       29      6   9995     16120     2.2s
 T   21750     192      9514  96.83%   1791.542628     1854               3.37%       20      6   9984     40278     5.3s

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            5.39 (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.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e+00, 4e+00]
  Cost   [1e+00, 3e+00]
  Bound  [1e+00, 1e+00]
  RHS    [7e+00, 1e+01]
Presolving model
2 rows, 3 cols, 6 nonzeros  0s
0 rows, 0 cols, 0 nonzeros  0s
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: 1
           numnodes: 0
    constrviolation: 0
          algorithm: 'highs'
            message: '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.'

sol(1) と sol(3) はどちらもバイナリ値です。バイナリ最適化変数 xb に対応するのはどの値でしょう。

prob.Variables

ans = struct with fields:
     x: [2×1 optim.problemdef.OptimizationVariable]
    xb: [1×1 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.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e+00, 4e+00]
  Cost   [1e+00, 3e+00]
  Bound  [1e+00, 1e+00]
  RHS    [7e+00, 1e+01]
Presolving model
2 rows, 3 cols, 6 nonzeros  0s
0 rows, 0 cols, 0 nonzeros  0s
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: 1
           numnodes: 0
    constrviolation: 0
          algorithm: 'highs'
            message: '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.'

出力構造体は numnodes が 0 であることを示します。これは intlinprog が分枝前に問題を解いたことを示します。これは結果が信頼できることを示す 1 つの指標になります。また、absolutegap および relativegap フィールドも 0 です。これは結果が信頼できることを示すもう 1 つの指標になります。

入力引数

すべて折りたたむ

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

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

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

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

データ型: double

`intcon` — 整数変数インデックス
整数のベクトル | `IntegerConstraint` オブジェクト

整数変数インデックス。正の整数のベクトル、または integerConstraint 関数で作成された IntegerConstraint オブジェクトとして指定します。"legacy" アルゴリズムは拡張整数変数をサポートしていません。intcon の値は、整数値または拡張整数値 (拡張整数変数を参照) である決定変数 x の要素を示します。intcon のインデックスの値は 1 ～ numel(f) です。

intcon は整数の配列にできます。intlinprog は配列 intcon をベクトル intcon(:) に内部的に変換します。

メモ

半整数変数と半連続変数の範囲は、1e5 を超えない厳密に正の範囲でなければなりません。

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

例: intcon = integerConstraint(SemiContinuous=[1,4],Integer=[2,3]) は、x(1) と x(4) が半連続、x(2) と x(3) が整数であると指定します。

`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 は 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 を使用します。

データ型: single | 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 は 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 を使用します。

データ型: single | 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"`
`MaxFeasiblePoints`	厳密に正の整数。`MaxFeasiblePoints` 整数実行可能点を見つけると、`intlinprog` は停止します。	`Inf`
`MaxNodes`	`intlinprog` が分枝限定プロセスで探索するノードの最大数である厳密に正の整数。	`1e7`
`MaxTime`	`intlinprog` の最大実行時間 (秒単位) である非負の実数。	`7200`
`ObjectiveCutOff`	`-Inf` より大きい実数。分枝限定法の計算時に、線形計画法の解が `ObjectiveCutOff` を超える目的値をもつ場合、`intlinprog` はノードを破棄します。	`Inf`
`OutputFcn`	イベントで最適化関数が呼び出す 1 つ以上の関数。`'savemilpsolutions'`、関数ハンドル、または関数ハンドルの cell 配列として指定します。カスタム出力関数の場合は、関数ハンドルを渡します。出力関数はソルバーを停止できます。 `'savemilpsolutions'` は、整数実行可能点をワークスペースにある行列 `xIntSol` に収集します。行列の各列が 1 つの整数実行可能点を表します。カスタム出力関数の記述については、intlinprog の出力関数とプロット関数の構文を参照してください。	`[]`
`PlotFcn`	アルゴリズムが実行中のさまざまな進行状況の測定値をプロットします。事前定義されたプロットから選択するか、独自のコードを記述してください。`'optimplotmilp'`、関数ハンドル、または関数ハンドルの cell 配列を渡します。カスタムプロット関数の場合は、関数ハンドルを渡します。既定の設定はなし (`[]`) です。 `'optimplotmilp'` は、解の目的値について内部計算された上限と下限をプロットします。カスタムプロット関数の記述については、intlinprog の出力関数とプロット関数の構文を参照してください。	`[]`
`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'`
`NodeSelection`	次に探索するノードを選択します。 `'simplebestproj'` — 最良の投影。詳細については、分枝限定法を参照してください。 `'minobj'` — 最小オブジェクト関数をもつノードを探索。 `'mininfeas'` — 実行不可能な整数の最小合計値をもつノードを探索。詳細については、分枝限定法を参照してください。	`'simplebestproj'`
`ObjectiveImprovementThreshold`	非負の実数。`intlinprog` は、少なくとも `ObjectiveImprovementThreshold` の下限である目的関数値をもつ別の実行可能解を検出した場合にのみ現在の実行可能解を変更します。(fold – fnew)/(1 + \|fold\|) > `ObjectiveImprovementThreshold`	`0`
`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`	整数値を取る変数を示すベクトル、または拡張整数制約を指定する `integerConstraint` オブジェクト (必須)
`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`	検出された整数実行可能点の数です。 `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)])`
`algorithm`	使用されるアルゴリズム。`'highs'` または `'legacy'` のいずれかです。
`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 でエラーが発生します。

詳細

すべて折りたたむ

拡張整数変数

"拡張整数変数" は、整数値、"半連続"、または "半整数" の変数です。

整数値変数は、–12 や 1234567 などの標準的な倍精度変数で表される任意の整数値を取ることができます。整数変数の範囲を指定する必要はありません。
半連続変数は、値 0 または下限から上限までの任意の実数値を取ることができます。範囲は厳密に正でなければならず、1e5 以下にする必要があります。
半整数変数は整数値であり、値 0 または下限から上限までの任意の整数値を取ることができます。範囲は厳密に正でなければならず、1e5 以下にする必要があります。

既定の "highs" アルゴリズムを使用する intlinprog ソルバーは、整数変数と拡張整数変数をサポートし、そのすべてが MATLAB^® double 型をもちます。integerConstraint 関数を使用して変数の型を指定します。次の名前を使用して、整数または拡張整数である変数インデックスを指定します。

Integer — 整数変数インデックス
SemiContinuous — 半連続変数インデックス
SemiInteger — 半整数変数インデックス

指定されていない変数インデックスの既定の型は連続、つまり任意の実数値を取ることができる変数です。

たとえば、変数 1 ～ 5 が整数、11 ～ 20 が半連続、残りが連続であると指定するには、次のようにします。

intcon = integerConstraint(Integer=1:5,SemiContinuous=11:20);

より詳細な終了メッセージ

次のいくつかの項目は、intlinprog から表示される可能性がある、より詳細な終了メッセージをリストしたものです。より詳細な終了メッセージでは、詳細な情報のリンクがメッセージの最初の文として提供されます。

ソルバーが途中で停止しました。整数実行可能点が検出されました。

intlinprog では、必ずしも最適解が検出されるとは限りません。しかし、少なくとも 1 つの整数実行可能点を検出しました。整数実行可能点は範囲、線形制約、整数制約など、すべての制約を満たすポイントです。

最大ノード数に到達

intlinprog では分枝限定アルゴリズムを使用します。詳細については、分枝限定法に記載されています。アルゴリズム内の各分枝は新しいノードを作成します。intlinprog は MaxNodes オプション ("許容誤差") を停止条件として使用します。

ドット表記を使用してオプションの値を変更できます。

options.MaxNodes = 5e4;

optimoptions を使用して値を変更することも可能です。

options = optimoptions(options,'MaxNodes',5e4);

制限時間を超過

intlinprog は MaxTime オプション (許容誤差) を停止条件として使用します。

ドット表記を使用してオプションの値を変更できます。

options.MaxTime = 5e4;

optimoptions を使用して値を変更することも可能です。

options = optimoptions(options,'MaxTime',5e4);

ノードの反復制限を超過

intlinprog が反復制限を超えました。intlinprog は LPMaxIterations オプション (許容誤差) を停止条件として使用します。

ドット表記を使用してオプションの値を変更できます。

options.LPMaxIterations = 5e4;

optimoptions を使用して値を変更することも可能です。

options = optimoptions(options,'LPMaxIterations',5e4);

実行可能点の最大ノード数に到達

intlinprog は少なくとも MaxNumFeasPoints 個の整数実行可能点を見つけました。intlinprog では、必ずしも最適解が検出されませんでした。

整数実行可能点は範囲、線形制約、整数制約など、すべての制約を満たすポイントです。

intlinprog は MaxNumFeasPoints オプション (許容誤差) を停止条件として使用します。

ドット表記を使用してオプションの値を変更できます。

options.MaxNumFeasPoints = 5e4;

optimoptions を使用して値を変更することも可能です。

options = optimoptions(options,'MaxNumFeasPoints',5e4);

目的値はギャップの許容誤差内にある

intlinprog は、解における目的関数の値の上限と下限の両方を内部計算します。これら内部計算された範囲の "ギャップ" とは、上限と下限の間の差異です。"相対ギャップ" は、下限の絶対値に 1 を加えた値とギャップとの比です。intlinprog は TolGapAbs オプション (ギャップの許容誤差) と TolGapRel オプション (相対ギャップの許容誤差) を停止条件として使用します。

整数変数の指定なし

intcon 引数が空であったため、intlinprog が線形計画問題を解きました。

ソルバーが途中で停止しました。整数実行可能点は検出されませんでした。

intlinprog によって整数実行可能点が検出されなかったため、処理を続行できませんでした。これは、必ずしも問題が実行不可能であることを意味するものではありません。intlinprog で整数実行可能点が見つからなかったというだけです。整数実行可能点は範囲、線形制約、整数制約など、すべての制約を満たすポイントです。

ルートの LP 問題を解く際の反復制限を超過

intlinprog は、RootLPMaxIterations 反復制限に達したため緩和された LP を解くことができませんでした。intlinprog は RootLPMaxIterations オプション (許容誤差) を停止条件として使用します。

割り当てられたメモリを超過

intlinprog でメモリ不足が発生しました。問題の再定式化によって解が得られる可能性があります。Williams [1]を参照してください。

実行可能解が見つかりません

問題の解が存在しないため、intlinprog が停止しました。範囲制約と線形制約に矛盾があるか、または整数制約が範囲制約および線形制約と一致していません。

原因を特定するには、intcon = [] を使用して問題を再実行します。得られる線形計画法が解をもたない場合、範囲制約と線形制約が矛盾しています。そうでない場合は、元の問題にある整数制約が範囲制約および線形制約と一致していません。

ルート LP 問題が非有界

LP (ルート線形計画) 問題は整数制約をもたない元の MILP 問題です。ルート LP 問題が非有界のため、intlinprog が停止しました。

元の問題は実行不可能である場合があります。ルート LP 問題が非有界の場合、intlinprog は実行可能性をチェックしません。

問題が非有界

線形計画問題の解が存在しないため、intlinprog が停止しました。任意のターゲット値には、ターゲットより小さい目的値をもつ実行可能点が存在します。

終了メッセージの定義

次のいくつかの項目は、intlinprog の終了メッセージに含まれる用語の定義を示したものです。

許容誤差

許容誤差は、一般的に、それを超えた場合にソルバーの反復を停止するしきい値です。許容誤差の詳細については、許容誤差と停止条件を参照してください。

ノード

分枝限定または分枝切断ツリーのノードは x の値であり、x(j) に小数部がある場合は x の成分 j です。分枝限定ノードには次の 2 つの部分問題があります。つまり、x(j) ≥ ceil(x(j)) という制限を伴う線形計画問題と、x(j) ≤ floor(x(j)) という制限を伴う線形計画問題を評価します。詳細については、分枝限定を参照してください。

許容誤差内の整数

intlinprog は intcon に指定する変数が厳密に整数であることを保証するものではありません。これらが整数値の TolInteger 許容誤差内にあることを保証するだけです。詳細については、一部の “整数” 解は整数ではないを参照してください。

ルートノード

intlinprog がルートノードで停止する場合は、分枝限定検索を実行する必要がなかったということです。intlinprog は前処理中に問題を解決したか、後続の処理で問題を解決したため、分枝する必要はありません。

ルートノードは、元の MILP (混合整数線形計画法) に基づく緩和線形計画問題です。詳細については、分枝限定を参照してください。

ヒント

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 で導入

すべて展開する

R2025a: 拡張整数変数のサポート

"highs" アルゴリズムを使用する intlinprog は、integerConstraint 関数を使用して指定する半連続変数と半整数変数をサポートします。たとえば、変数 10 ～ 20 が半整数、変数 1 ～ 9 が半連続であると指定するには、次のように入力します。

intcon = integerConstraint(SemiInteger=10:20,SemiContinuous=1:9);

詳細については、拡張整数変数を参照してください。

R2024b: `"highs"` アルゴリズムで出力関数、プロット関数、`MaxFeasiblePoints` オプションをサポート

"highs" アルゴリズムで出力関数とプロット関数がサポートされるようになりました。詳細については、intlinprog の出力関数とプロット関数の構文を参照してください。組み込みプロット関数の使用例については、工場、倉庫、販売店割り当てモデル: ソルバーベースを参照してください。

出力関数とプロット関数のoptimValues 構造体で、lowerbound の代わりに dualbound というフィールド名が使用されるようになりました。dualbound は、最小化問題の場合はグローバル下限、最大化問題の場合はグローバル上限を意味します。optimplotmilp プロット関数で、Branch/bound UB と Branch/bound LB の代わりに Primal Bound と Dual Bound というラベルが使用されるようになりました。

"highs" アルゴリズムで MaxFeasiblePoints オプションがサポートされるようになりました。"highs" アルゴリズムの output 構造体で numfeaspoints フィールドがサポートされるようになりました。

R2024b: `"legacy"` アルゴリズムは削除予定

intlinprog の "legacy" アルゴリズムは将来のリリースで削除される予定です。その時点で、"legacy" アルゴリズムに対してのみ有効な options はすべて削除され、Algorithm オプションが削除されます。また、output 構造体の algorithm フィールドもその時点で削除されます。

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' に設定します。

参考

intlinprog

構文

説明

例

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

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

初期点の使用

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

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

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

入力引数

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

intcon — 整数変数インデックス 整数のベクトル | IntegerConstraint オブジェクト

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

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

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

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

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

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

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

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

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

出力引数

x — 解 実数ベクトル

fval — 目的値 実数スカラー

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

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

制限

詳細

拡張整数変数

より詳細な終了メッセージ

ソルバーが途中で停止しました。整数実行可能点が検出されました。

最大ノード数に到達

制限時間を超過

ノードの反復制限を超過

実行可能点の最大ノード数に到達

目的値はギャップの許容誤差内にある

整数変数の指定なし

ソルバーが途中で停止しました。整数実行可能点は検出されませんでした。

ルートの LP 問題を解く際の反復制限を超過

割り当てられたメモリを超過

実行可能解が見つかりません

ルート LP 問題が非有界

問題が非有界

終了メッセージの定義

許容誤差

ノード

許容誤差内の整数

ルート ノード

ヒント

代替機能

アプリ

バージョン履歴

R2025a: 拡張整数変数のサポート

R2024b: "highs" アルゴリズムで出力関数、プロット関数、MaxFeasiblePoints オプションをサポート

R2024b: "legacy" アルゴリズムは削除予定

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

R2019a: 既定の BranchRule は 'reliability'

参考

トピック

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

`intcon` — 整数変数インデックス
整数のベクトル | `IntegerConstraint` オブジェクト

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

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

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

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

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

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

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

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

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

`x` — 解
実数ベクトル

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

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

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

ルートノード

R2024b: `"highs"` アルゴリズムで出力関数、プロット関数、`MaxFeasiblePoints` オプションをサポート

R2024b: `"legacy"` アルゴリズムは削除予定

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

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