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

説明

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

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

minxfTx subject to {x(intcon) are integers or extended integersA⋅x≤bAeq⋅x=beqlb≤x≤ub.

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 を返します。

例

例

すべて折りたたむ

ライブ スクリプトを開く

問題を解く

minx(8x1+x2)subjectto{x2isanintegerx1+2x2≥-14-4x1-x2≤-332x1+x2≤20.

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

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.

x = 2×1

    6.5000
    7.0000
ライブ スクリプトを開く

問題を解く

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12.

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

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.

x = 3×1

     0
     6
     0
ライブ スクリプトを開く

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

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            4.30 (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     2.0s
 T    9340     919      3970  80.72%   1692.410008     2687              37.01%       29      6   9995     16120     3.0s
 T   21750     192      9514  96.83%   1791.542628     1854               3.37%       20      6   9984     40278     6.4s

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            6.54 (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 がより多くのステップを必要とする場合があります。

ライブ スクリプトを開く

問題を解く

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12

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

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

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
     6
     0
ライブ スクリプトを開く

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

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12

この問題を表す、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.

sol = 3×1

     0
     6
     0


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 に対応します。アルゴリズムを参照してください。

ライブ スクリプトを開く

より多くの出力をもつ intlinprog を呼び出して、解の詳細とプロセスを確認します。

ゴールは次の問題を解くことです。

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12.

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

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.

x = 3×1

     0
     6
     0


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'*x を表します。表記では、f は列ベクトルを前提としていますが、行ベクトルまたは配列を自由に使用できます。linprog は配列 f を列ベクトル f(:) に内部的に変換します。

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

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

データ型: double

整数変数インデックス。正の整数のベクトル、または 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 は M 行 N 列の行列で、M は不等式の数、N は変数の数 (f の長さ) です。大規模な問題の場合は、A をスパース行列として渡します。

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

A*x <= b,

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

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

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.

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

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

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

データ型: double

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

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

A*x <= b,

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

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

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.

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

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

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

データ型: single | double

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

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

Aeq*x = beq,

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

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

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20.

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

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

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

データ型: double

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

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

Aeq*x = beq,

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

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

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20.

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

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

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

データ型: single | double

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

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

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

データ型: double

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

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

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

データ型: double

初期点。実数配列として指定します。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

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
MaxNodesintlinprog が分枝限定プロセスで探索するノードの最大数である厳密に正の整数。1e7
MaxTimeintlinprog の最大実行時間 (秒単位) である非負の実数。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'
IntegerTolerance1e-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|) > ObjectiveImprovementThreshold0
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)

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

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

出力引数

すべて折りたたむ

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

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

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

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

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

3

解は、相対許容誤差 ConstraintTolerance に関しては実行可能ですが、絶対許容誤差に関しては実行不可能です。

2

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

1

intlinprog が解 x に収束しました。

0

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

-1

intlinprog が出力関数またはプロット関数によって停止しました。

-2

実行可能点が検出されませんでした。

-3

ルート LP 問題が非有界です。

-9

ソルバーが実行可能性を失いました。

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

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

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

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(Aeq*x-beq, inf); (lb-x); (x-ub); (Ai*x-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 でエラーが発生します。

詳細

すべて折りたたむ

ヒント

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

すべて展開する

参考

| | | | |

トピック