intlinprog
混合整数線形計画法 (MILP)
構文
説明
混合整数線形計画法ソルバー。
以下で指定された問題の最小値を見つけます。
f、x、b、bl、beq、lb、ub はベクトル、intcon はベクトルまたは integerConstraint オブジェクト、A と Aeq は行列です。
f、intcon、lb、および ub はベクトルまたは配列として指定できます。行列引数を参照してください。
メモ
intlinprog は、ソルバーベースのアプローチのみに適用されます。問題ベースのアプローチの場合は、solve を使用してください。2 つの最適化アプローチの詳細については、はじめに問題ベース アプローチまたはソルバーベース アプローチを選択を参照してください。
x = intlinprog(problem)problem 構造体を使用してすべてのソルバーの入力をカプセル化します。mpsread を使用して MPS ファイルから problem 構造体をインポートできます。prob2struct を使用して OptimizationProblem オブジェクトから構造体 problem を作成することもできます。
例
問題を解く
目的関数ベクトルと整数変数のベクトルを記述します。
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.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 3 rows; 2 cols; 6 nonzeros; 1 integer variables (0 binary)
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, 0 domain fixed)
6 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
J 0 0 0 0.00% -inf 80 Large 0 0 0 0 0.0s
T 0 0 0 0.00% -inf 59 Large 0 0 0 3 0.0s
1 0 1 100.00% 59 59 0.00% 0 0 0 3 0.0s
Solving report
Status Optimal
Primal bound 59
Dual bound 59
Gap 0% (tolerance: 0.01%)
P-D integral 0
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 (solve)
0.00 (postsolve)
Max sub-MIP depth 0
Nodes 1
Repair LPs 0 (0 feasible; 0 iterations)
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
問題を解く
目的関数ベクトルと整数変数のベクトルを記述します。
f = [-3;-2;-1]; intcon = 3;
線形不等式制約を記述します。
A = [1,1,1]; b = 7;
線形等式制約を記述します。
Aeq = [4,2,1]; beq = 12;
範囲制約を記述します。
lb = zeros(3,1);
ub = [Inf;Inf;1]; % Enforces x(3) is binaryintlinprog を呼び出します。
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
Running HiGHS 1.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 2 rows; 3 cols; 6 nonzeros; 1 integer variables (1 binary)
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
Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% -12 -12 0.00% 0 0 0 0 0.0s
Solving report
Status Optimal
Primal bound -12
Dual bound -12
Gap 0% (tolerance: 0.01%)
P-D integral 0
Solution status feasible
-12 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (solve)
0.00 (postsolve)
Max sub-MIP depth 0
Nodes 0
Repair LPs 0 (0 feasible; 0 iterations)
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];
初期点を使用せずに問題を解き、表示を調べて解法プロセスの分枝限定ノード数と LP 反復回数を確認します。
[x1,fval1,exitflag1,output1] = intlinprog(f,intcon,[],[],Aeq,beq,lb);
Running HiGHS 1.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 4 rows; 8 cols; 32 nonzeros; 8 integer variables (0 binary)
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, 0 domain fixed)
27 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src 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 14284 1214 5620 78.42% 1690.169125 2849 40.68% 39 5 9987 17146 1.6s
T 21917 1000 8515 86.43% 1736.378236 2113 17.82% 36 5 9873 24182 2.4s
T 26514 250 10328 96.20% 1778.832142 1854 4.05% 31 5 4853 28216 2.7s
26903 0 10609 100.00% 1854 1854 0.00% 39 11 3699 28606 2.7s
Solving report
Status Optimal
Primal bound 1854
Dual bound 1854
Gap 0% (tolerance: 0.01%)
P-D integral 0.352619102888
Solution status feasible
1854 (objective)
0 (bound viol.)
9.63673585375e-14 (int. viol.)
0 (row viol.)
Timing 2.71 (total)
0.00 (presolve)
0.00 (solve)
0.00 (postsolve)
Max sub-MIP depth 3
Nodes 26903
Repair LPs 0 (0 feasible; 0 iterations)
LP iterations 28606 (total)
240 (strong br.)
77 (separation)
2156 (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 = [16 60 12 0 0 86 34 219]; [x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);
Running HiGHS 1.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 4 rows; 8 cols; 32 nonzeros; 8 integer variables (0 binary)
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 2113
Objective function is integral with scale 1
Solving MIP model with:
4 rows
8 cols (0 binary, 8 integer, 0 implied int., 0 continuous, 0 domain fixed)
27 nonzeros
Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 2113 100.00% 0 0 0 0 0.0s
0 0 0 0.00% 1554.047531 2113 26.45% 0 0 4 4 0.0s
T 3313 105 1293 95.83% 1687.4271 1854 8.98% 56 6 9402 6902 0.5s
3996 0 1630 100.00% 1854 1854 0.00% 30 6 9989 8272 0.6s
Solving report
Status Optimal
Primal bound 1854
Dual bound 1854
Gap 0% (tolerance: 0.01%)
P-D integral 0.116495047223
Solution status feasible
1854 (objective)
0 (bound viol.)
1.13686837722e-13 (int. viol.)
0 (row viol.)
Timing 0.60 (total)
0.00 (presolve)
0.00 (solve)
0.00 (postsolve)
Max sub-MIP depth 3
Nodes 3996
Repair LPs 0 (0 feasible; 0 iterations)
LP iterations 8272 (total)
240 (strong br.)
79 (separation)
565 (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の LP 反復回数は約 25,000、分枝限定ノード数も約 25,000 です。初期点を使用する場合、
intlinprogの LP 反復回数は 1/3 未満となり、ノード数はさらに少なくなります。解を得るまでの時間もはるかに短くなります。
初期点を与えることが常に役立つとは限りません。この問題の場合、初期点を与えると、時間と計算ステップが節減されます。ただし、問題によっては、初期点を与えることで 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
x0 = [];表示を指定しません。
options = optimoptions("intlinprog",Display="off");
ソルバーを実行します。
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)
x = 3×1
0
6
0
この例では、問題ベースのアプローチを使用して問題を設定し、次にソルバーベースのアプローチを使用してその問題を解く方法を示します。問題は、次のとおりです。
この問題を表す、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.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 2 rows; 3 cols; 6 nonzeros; 1 integer variables (1 binary)
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
Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% -12 -12 0.00% 0 0 0 0 0.0s
Solving report
Status Optimal
Primal bound -12
Dual bound -12
Gap 0% (tolerance: 0.01%)
P-D integral 0
Solution status feasible
-12 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (solve)
0.00 (postsolve)
Max sub-MIP depth 0
Nodes 0
Repair LPs 0 (0 feasible; 0 iterations)
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
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 を呼び出して、解の詳細とプロセスを確認します。
ゴールは次の問題を解くことです。
ソルバーの入力を指定します。
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.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 2 rows; 3 cols; 6 nonzeros; 1 integer variables (1 binary)
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
Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% -12 -12 0.00% 0 0 0 0 0.0s
Solving report
Status Optimal
Primal bound -12
Dual bound -12
Gap 0% (tolerance: 0.01%)
P-D integral 0
Solution status feasible
-12 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.01 (total)
0.00 (presolve)
0.00 (solve)
0.00 (postsolve)
Max sub-MIP depth 0
Nodes 0
Repair LPs 0 (0 feasible; 0 iterations)
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
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 オブジェクトとして指定します。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 は変数の数 (x0 の要素数) です。大規模な問題の場合は、A をスパース行列として渡します。
A は M 個の線形不等式を符号化します。
A*x <= b,
ここで、x は N 個の変数 x(:) の列ベクトル、b は M 個の要素をもつベクトルです。
b が 2 要素 cell 配列 {bl,b} の場合、A は線形不等式を符号化します。
bl <= A*x <= b. | (1) |
たとえば、次の不等式を考えてみましょう。
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30
次の制約を入力することによって、不等式を指定します。
A = [1,2;3,4;5,6]; b = [10;20;30];
追加の制約がある場合も同様です。
| 4x1 – x2 ≥ 2 | (2) |
この場合は次のように指定します。
bb = {[-inf;-inf;-inf;2] [b;inf]};
AA = [A;[4 -1]];AA と bb を線形不等式制約として渡します。
例: x の成分の和が 1 以下であることを指定するには、A = ones(1,N) と b = 1 を使用します。
データ型: single | double
線形不等式制約。実数ベクトル、または実数配列の 2 要素 cell 配列として指定します。
bがM要素ベクトルの場合、bはM個の線形不等式を符号化します。A*x <= b,(3) ここで、
xはN個の変数x(:)の列ベクトル、AはM行N列の行列です。bが 2 要素 cell 配列{bl,b}の場合、blとbのいずれかまたは両方が空以外でなければなりません。bの空でないエントリに、線形不等式を符号化するM個の要素を含めます。bl <= A*x <= b,(4) ここで、
xはN個の変数x(:)の列ベクトル、AはM行N列の行列です。
b または bl を行ベクトルとして渡す場合、ソルバーはこれを列ベクトル b(:) または bl(:) に内部的に変換します。
たとえば、次の不等式を考えてみましょう。
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.
次の制約を入力することによって、不等式を指定します。
A = [1,2;3,4;5,6]; b = [10;20;30];
次の追加の制約について考えます。
| 4x1 – x2 ≥ 2 | (5) |
A および b を拡張する線形不等式行列 AA および bb として制約を指定します。
bb = {[-inf;-inf;-inf;2] [b;inf]};
AA = [A;[4 -1]];例: 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 は 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(:) に内部的に変換します。
intlinprog は、与えられたすべての x0 の使用を試み、必要に応じて点を変更し実行可能にします。
x0 を指定すると、intlinprog が収束に要する時間が変わる場合があります。x0 がソルバーに及ぼす影響を予測することは困難です。
例: x0 = 100*rand(size(f))
データ型: double
intlinprog のオプションは optimoptions の出力として指定されます。
一部のオプションは、optimoptions に表示されません。このようなオプションは、次の表ではイタリックで示されています。詳細については、最適化オプションの表示を参照してください。
| オプション | 説明 | 既定の設定 |
AbsoluteGapTolerance | 非負の実数。
| 1e-6 |
ConstraintTolerance | 整数制約または線形制約の許容される最大の違反を表す
| 1e-6 |
Display | 表示レベル (反復表示を参照):
| "iter" |
MaxFeasiblePoints | 厳密に正の整数。MaxFeasiblePoints 整数実行可能点を見つけると、intlinprog は停止します。 | Inf |
MaxNodes | intlinprog が分枝限定プロセスで探索するノードの最大数である厳密に正の整数。 | 1e7 |
MaxTime | intlinprog の最大実行時間 (秒単位) である非負の実数。 | 7200 |
ObjectiveCutOff | -Inf より大きい実数。分枝限定法の計算時に、線形計画法の解が ObjectiveCutOff を超える目的値をもつ場合、intlinprog はノードを破棄します。 | Inf |
OutputFcn | イベントで最適化関数が呼び出す 1 つ以上の関数。
カスタム出力関数の記述については、intlinprog の出力関数とプロット関数の構文を参照してください。 | [] |
PlotFcn | アルゴリズムが実行中のさまざまな進行状況の測定値をプロットします。事前定義されたプロットから選択するか、独自のコードを記述してください。
カスタム プロット関数の記述については、intlinprog の出力関数とプロット関数の構文を参照してください。 | [] |
RelativeGapTolerance |
停止テストは次のようになります。
メモ
| 1e-4 |
例: options = optimoptions("intlinprog",MaxTime=120)
以下のフィールドで指定された、入力とオプションをカプセル化する構造体。
f | 目的関数 f'*x を表すベクトル (必須) |
intcon | 整数値を取る変数を示すベクトル、または拡張整数制約を指定する integerConstraint オブジェクト (必須) |
Aineq | 線形不等式制約 Aineq*x ≤ bineq の行列 |
| 線形不等式制約 bcons = {bl b};
problem.bineq = {bcons}; |
| 線形等式制約 Aeq*x = beq の行列 |
| 線形等式制約 Aeq*x = beq のベクトル |
lb | 下限のベクトル |
ub | 上限のベクトル |
x0 | 初期点 |
solver | 'intlinprog' (必須) |
| optimoptions を使用して作成されたオプション (必須) |
少なくとも以下のフィールドを問題の構造体で指定しなければなりません。その他のフィールドはオプションです。
fintconsolveroptions
注意
problem 引数はスカラー構造体でなければなりません。線形制約を cell 配列 {bl,b} として作成すると、結果として得られる問題構造体が非スカラーの構造体配列になることがあります。problem が必ずスカラーになるように、{{bl,b}} を渡します。
例: 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 が停止した対応する理由を以下に示します。
| 解は、相対許容誤差 |
|
|
|
|
|
|
|
|
| 実行可能点が検出されませんでした。 |
| ルート LP 問題が非有界です。 |
| ソルバーが実行可能性を失いました。 |
終了メッセージは、許容誤差の超過など、intlinprog が停止した理由に関する情報をより詳細に提供します。
終了フラグ 3 と -9 は、実行可能性が大きい解に関連しています。これらは通常、条件数が大きい線形制約行列、または大きな解の成分を含む問題から生じます。これらの問題を修正するには、係数行列のスケーリング、冗長な線形制約の除去、または変数に対するより狭い範囲の指定を試します。
最適化プロセスに関する情報を含む構造体として返された解法プロセスの概要。
|
メモ
|
|
|
| 検出された整数実行可能点の数です。
|
| 分枝限定アルゴリズムのノードの数。前処理中または初期カット中に解が見つかった場合、
|
| 違反された制約について明らかな制約違反。
|
| 終了メッセージ。 |
制限
通常、解
x(intCon)の整数値と推定される成分は厳密に整数ではありません。intlinprogでは整数のConstraintTolerance内の解の値はすべて整数と見なされます。整数と推定されるすべての数値を厳密に整数に丸めるには、関数
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を超える問題の成分 (f、b、ubの係数など) は受け入れられません。また、絶対値が1e15以上の線形制約行列AおよびAeqも受け入れられません。このような問題をもつintlinprogを実行しようとすると、intlinprogでエラーが発生します。
詳細
"拡張整数変数" は、整数値、"半連続"、または "半整数" の変数です。
整数値変数は、–12 や 1234567 などの標準的な倍精度変数で表される任意の整数値を取ることができます。整数変数の範囲を指定する必要はありません。
半連続変数は、値
0または下限から上限までの任意の実数値を取ることができます。範囲は厳密に正でなければならず、1e5以下にする必要があります。半整数変数は整数値であり、値
0または下限から上限までの任意の整数値を取ることができます。範囲は厳密に正でなければならず、1e5以下にする必要があります。
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 で整数実行可能点が見つからなかったというだけです。整数実行可能点は範囲、線形制約、整数制約など、すべての制約を満たすポイントです。
intlinprog は、RootLPMaxIterations 反復制限に達したため緩和された LP を解くことができませんでした。intlinprog は RootLPMaxIterations オプション (許容誤差) を停止条件として使用します。
intlinprog でメモリ不足が発生しました。問題の再定式化によって解が得られる可能性があります。Williams [1]を参照してください。
問題の解が存在しないため、intlinprog が停止しました。範囲制約と線形制約に矛盾があるか、または整数制約が範囲制約および線形制約と一致していません。
原因を特定するには、intcon = [] を使用して問題を再実行します。得られる線形計画法が解をもたない場合、範囲制約と線形制約が矛盾しています。そうでない場合は、元の問題にある整数制約が範囲制約および線形制約と一致していません。
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 5bintprogはintlinprogに置き換えられています。古いbintprogコードをintlinprogで使用するように更新するには、次の変更を行います。intconを1:numVarsに設定します。ここで、numVarsは問題の変数の数です。lbをzeros(numVars,1)に設定します。ubをones(numVars,1)に設定します。関連するオプションを更新します。
optimoptionsを使用してintlinprogオプションを作成します。呼び出しを
bintprogに変更します。以下のようになります。[x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options) % Change your call to: [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,x0,options)
代替機能
アプリ
[最適化] ライブ エディター タスクが intlinprog にビジュアル インターフェイスを提供します。
バージョン履歴
R2014a で導入intlinprog の "legacy" アルゴリズムは削除されました。"legacy" アルゴリズムに固有のオプションもすべて削除されています。
BranchRuleCutGenerationCutMaxIterationsHeuristicsHeuristicsMaxNodesIntegerPreprocessIntegerToleranceLPMaxIterationsLPOptimalityToleranceLPPreprocess
NodeSelectionObjectiveImprovementThresholdRootLPAlgorithmRootLPMaxIterations
また、intlinprog アルゴリズムは 1 つしかないため、Algorithm オプションは削除されました。同様に、intlinprog の output 構造体に algorithm フィールドは含まれなくなりました。
phase フィールドは "legacy" アルゴリズムのみで使用されていたため、出力関数やプロット関数 (intlinprog の出力関数とプロット関数の構文を参照) で使用される optimValues 構造体に含まれなくなりました。
intlinprog ソルバーで線形範囲制約、つまり線形制約の上限と下限がサポートされます。
線形制約ベクトルを cell 配列 {bl b} として指定します。例については、線形範囲制約を参照してください。
"highs" アルゴリズムを使用する intlinprog は、integerConstraint 関数を使用して指定する半連続変数と半整数変数をサポートします。たとえば、変数 10 ～ 20 が半整数、変数 1 ～ 9 が半連続であると指定するには、次のように入力します。
intcon = integerConstraint(SemiInteger=10:20,SemiContinuous=1:9);
詳細については、拡張整数変数を参照してください。
"highs" アルゴリズムで出力関数とプロット関数がサポートされるようになりました。詳細については、intlinprog の出力関数とプロット関数の構文を参照してください。組み込みプロット関数の使用例については、工場、倉庫、販売店割り当てモデル: ソルバーベースを参照してください。
出力関数とプロット関数のoptimValues 構造体で、lowerbound の代わりに dualbound というフィールド名が使用されるようになりました。dualbound は、最小化問題の場合はグローバル下限、最大化問題の場合はグローバル上限を意味します。optimplotmilp プロット関数で、Branch/bound UB と Branch/bound LB の代わりに Primal Bound と Dual Bound というラベルが使用されるようになりました。
"highs" アルゴリズムで MaxFeasiblePoints オプションがサポートされるようになりました。"highs" アルゴリズムの output 構造体で numfeaspoints フィールドがサポートされるようになりました。
intlinprog に Algorithm オプションが追加され、新しいアルゴリズムが既定のアルゴリズムとして加わりました。"highs" アルゴリズムはオープンソースの HiGHS コードに基づいています。現時点で、"highs" アルゴリズムは出力関数やプロット関数をサポートしていません。
以前のアルゴリズムを使用するには、optimoptions を使用して Algorithm="legacy" を設定します。
ConstraintTolerance オプション値の許容範囲が、どちらのアルゴリズムも 1e-10 ～ 1e-3 になりました。"legacy" アルゴリズムについては、IntegerTolerance オプション値の許容範囲も同様です。
BranchRule オプションの既定値は 'maxpscost' ではなく 'reliability' です。テストでは、この値を使用することで、多くの問題で求解にかかる時間と探索される分岐ノード数の両方に関するパフォーマンスが向上します。
いくつかの問題では、以前の分岐ルールの方が優れたパフォーマンスを示します。以前の動作にするには、BranchRule オプションを 'maxpscost' に設定します。
MATLAB Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Web サイトの選択
Web サイトを選択すると、翻訳されたコンテンツにアクセスし、地域のイベントやサービスを確認できます。現在の位置情報に基づき、次のサイトの選択を推奨します:
また、以下のリストから Web サイトを選択することもできます。
最適なサイトパフォーマンスの取得方法
中国のサイト (中国語または英語) を選択することで、最適なサイトパフォーマンスが得られます。その他の国の MathWorks のサイトは、お客様の地域からのアクセスが最適化されていません。
南北アメリカ
- América Latina (Español)
- Canada (English)
- United States (English)
ヨーロッパ
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)