intlinprog
혼합 정수 선형 계획법(MILP)
구문
설명
혼합 정수 선형 계획법 솔버입니다.
다음으로 지정된 문제의 최솟값을 구합니다.
f, x, intcon, b, beq, lb, ub는 벡터이고 A와 Aeq는 행렬입니다.
f, intcon, lb, ub를 벡터 또는 배열로 지정할 수 있습니다. 행렬 인수 항목을 참조하십시오.
참고
intlinprog
솔버는 솔버 기반 접근법에만 적용됩니다. 두 가지 최적화 접근법에 대한 설명은 먼저 문제 기반 접근법 또는 솔버 기반 접근법 중 선택하기 항목을 참조하십시오.
은 x
= intlinprog(problem
)problem
구조체를 사용하여 모든 솔버 입력값을 캡슐화합니다. mpsread
를 사용하여 MPS 파일에서 problem
구조체를 가져올 수 있습니다. 또는 prob2struct
를 사용하여 OptimizationProblem
객체에서 problem
구조체를 만들 수도 있습니다.
예제
선형 부등식이 있는 MILP 풀기
다음 문제를 풀어 보겠습니다.
목적 함수 벡터와 정수 변수로 구성된 벡터를 작성합니다.
f = [8;1]; intcon = 2;
“보다 큼” 부등식에 -1
을 곱하여 모든 부등식을 A*x <= b
형식으로 변환합니다.
A = [-1,-2; -4,-1; 2,1]; b = [14;-33;20];
intlinprog
를 호출합니다.
x = intlinprog(f,intcon,A,b)
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms Presolving model 3 rows, 2 cols, 6 nonzeros 3 rows, 2 cols, 6 nonzeros Solving MIP model with: 3 rows 2 cols (0 binary, 1 integer, 0 implied int., 1 continuous) 6 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% -inf inf inf 0 0 0 0 0.0s T 0 0 0 0.00% -inf 59 Large 0 0 0 3 0.0s Solving report Status Optimal Primal bound 59 Dual bound 59 Gap 0% (tolerance: 0.01%) Solution status feasible 59 (objective) 0 (bound viol.) 1.7763568394e-15 (int. viol.) 0 (row viol.) Timing 0.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
모든 유형의 제약 조건이 있는 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
intlinprog
를 호출합니다.
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms Presolving model 2 rows, 3 cols, 6 nonzeros 0 rows, 0 cols, 0 nonzeros Presolve: Optimal Solving report Status Optimal Primal bound -12 Dual bound -12 Gap 0% (tolerance: 0.01%) Solution status feasible -12 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.00 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 0 LP iterations 0 (total) 0 (strong br.) 0 (separation) 0 (heuristics) Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.
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.6.0: Copyright (c) 2023 HiGHS under MIT licence terms Presolving model 4 rows, 8 cols, 32 nonzeros 4 rows, 8 cols, 27 nonzeros Objective function is integral with scale 1 Solving MIP model with: 4 rows 8 cols (0 binary, 8 integer, 0 implied int., 0 continuous) 27 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 1554.047531 inf inf 0 0 4 4 0.0s T 20753 210 8189 98.04% 1783.696925 1854 3.79% 30 8 9884 19222 2.7s 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.79 (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.6.0: Copyright (c) 2023 HiGHS under MIT licence terms Solution has num max sum Col infeasibilities 0 0 0 Integer infeasibilities 0 0 0 Row infeasibilities 0 0 0 Row residuals 0 0 0 Presolving model 4 rows, 8 cols, 32 nonzeros 4 rows, 8 cols, 27 nonzeros MIP start solution is feasible, objective value is 3901 Objective function is integral with scale 1 Solving MIP model with: 4 rows 8 cols (0 binary, 8 integer, 0 implied int., 0 continuous) 27 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 3901 100.00% 0 0 0 0 0.0s 0 0 0 0.00% 1554.047531 3901 60.16% 0 0 4 4 0.0s T 6266 708 2644 73.61% 1662.791423 3301 49.63% 20 6 9746 10699 1.3s T 9340 919 3970 80.72% 1692.410008 2687 37.01% 29 6 9995 16120 2.0s T 21750 192 9514 96.83% 1791.542628 1854 3.37% 20 6 9984 40278 4.7s Solving report Status Optimal Primal bound 1854 Dual bound 1854 Gap 0% (tolerance: 0.01%) Solution status feasible 1854 (objective) 0 (bound viol.) 1.42108547152e-13 (int. viol.) 0 (row viol.) Timing 4.80 (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)
x = 3×1
0
6
0
문제 기반 접근법을 사용하여 MILP 풀기
이 예제에서는 문제 기반 접근법을 사용하여 문제를 설정한 다음 솔버 기반 접근법을 사용하여 이 문제를 푸는 방법을 보여줍니다. 문제는 다음과 같습니다.
이 문제를 나타내는 prob
라는 OptimizationProblem
객체를 만듭니다. 이진 변수를 지정하려면 하한이 0이고 상한이 1인 정수형의 최적화 변수를 만드십시오.
x = optimvar('x',2,'LowerBound',0); xb = optimvar('xb','LowerBound',0,'UpperBound',1,'Type','integer'); prob = optimproblem('Objective',-3*x(1)-2*x(2)-xb); cons1 = sum(x) + xb <= 7; cons2 = 4*x(1) + 2*x(2) + xb == 12; prob.Constraints.cons1 = cons1; prob.Constraints.cons2 = cons2;
문제 객체를 문제 구조체로 변환합니다.
problem = prob2struct(prob);
결과로 생성된 문제 구조체를 풉니다.
[sol,fval,exitflag,output] = intlinprog(problem)
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms Presolving model 2 rows, 3 cols, 6 nonzeros 0 rows, 0 cols, 0 nonzeros Presolve: Optimal Solving report Status Optimal Primal bound -12 Dual bound -12 Gap 0% (tolerance: 0.01%) Solution status feasible -12 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.01 (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: []
numnodes: 0
constrviolation: 0
algorithm: 'highs'
message: 'Optimal solution found....'
sol(1)
과 sol(3)
은 모두 이진 값입니다. 어떤 값이 이진 최적화 변수 xb
에 해당될까요?
prob.Variables
ans = struct with fields:
x: [2x1 optim.problemdef.OptimizationVariable]
xb: [1x1 optim.problemdef.OptimizationVariable]
변수 xb
는 Variables
에서 마지막에 표시되므로 xb
는 sol(3) = 1
에 해당합니다. Algorithms 항목을 참조하십시오.
MILP 해와 과정 검토하기
출력값을 더 추가하고 intlinprog
를 호출하여 해의 세부 정보와 풀이 과정을 확인합니다.
다음 문제를 푸는 것이 목적입니다.
솔버 입력값을 지정합니다.
f = [-3;-2;-1];
intcon = 3;
A = [1,1,1];
b = 7;
Aeq = [4,2,1];
beq = 12;
lb = zeros(3,1);
ub = [Inf;Inf;1]; % enforces x(3) is binary
모든 출력값을 사용하여 intlinprog
를 호출합니다.
[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms Presolving model 2 rows, 3 cols, 6 nonzeros 0 rows, 0 cols, 0 nonzeros Presolve: Optimal Solving report Status Optimal Primal bound -12 Dual bound -12 Gap 0% (tolerance: 0.01%) Solution status feasible -12 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.03 (total) 0.02 (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: []
numnodes: 0
constrviolation: 0
algorithm: 'highs'
message: 'Optimal solution found....'
output 구조체에 numnodes
가 0
으로 표시됩니다. 이는 intlinprog
가 분기 전에 문제를 풀었음을 의미합니다. 이는 결과를 신뢰할 수 있음을 나타냅니다. 또한, absolutegap
필드와 relativegap
필드가 0
입니다. 이 또한 결과를 신뢰할 수 있음을 나타냅니다.
입력 인수
f
— 계수 벡터
실수형 벡터 | 실수형 배열
계수 벡터로, 실수형 벡터나 실수형 배열로 지정됩니다. 계수 벡터는 목적 함수 f'*x
를 나타냅니다. 이 표기법은 f
가 열 벡터라고 가정하지만, 원하는 경우 자유롭게 행 벡터 또는 배열을 사용할 수 있습니다. 내부적으로 linprog
는 f
를 열 벡터 f(:)
으로 변환합니다.
f = []
을 지정할 경우 intlinprog
는 목적 함수를 최소화하려고 하지 않고 실현가능점을 구하려고 합니다.
예: f = [4;2;-1.7];
데이터형: double
intcon
— 정수 제약 조건으로 구성된 벡터
정수 벡터
정수 제약 조건으로 구성된 벡터로, 양의 정수로 구성된 벡터로 지정됩니다. intcon
의 값은 정수 값을 갖는 결정 변수 x
의 성분을 나타냅니다. intcon
은 1
에서 numel(f)
까지의 값을 가집니다.
intcon
은 배열일 수도 있습니다. 내부적으로 intlinprog
는 배열 intcon
을 벡터 intcon(:)
으로 변환합니다.
예: intcon = [1,2,7]
은 x(1)
, x(2)
, x(7)
이 정수 값만 받는다는 것을 의미합니다.
데이터형: double
A
— 선형 부등식 제약 조건
실수 행렬
선형 부등식 제약 조건으로, 실수 행렬로 지정됩니다. A
는 M
×N
행렬입니다. 여기서 M
은 부등식 개수이고 N
은 변수 개수(f
의 길이)입니다. 대규모 문제의 경우, A
를 희소 행렬로 전달하십시오.
A
는 다음과 같이 M
개의 선형 부등식을 인코딩합니다.
A*x <= b
,
여기서 x
는 N
개의 변수 x(:)
으로 구성된 열 벡터이고, b
는 M
개의 요소를 갖는 열 벡터입니다.
예를 들어, 다음 부등식을 살펴보겠습니다.
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.
다음 제약 조건을 입력하여 부등식을 지정합니다.
A = [1,2;3,4;5,6]; b = [10;20;30];
예: 총합이 1보다 작거나 같도록 x 성분을 지정하려면 A = ones(1,N)
및 b = 1
을 지정하십시오.
데이터형: double
b
— 선형 부등식 제약 조건
실수형 벡터
선형 부등식 제약 조건으로, 실수 벡터로 지정됩니다. b
는 A
행렬과 관련된, 요소를 M
개 가진 벡터입니다. b
를 행 벡터로 전달하면 솔버는 내부적으로 b
를 열 벡터 b(:)
으로 변환합니다. 대규모 문제의 경우, b
를 희소 벡터로 전달하십시오.
b
는 다음과 같이 M
개의 선형 부등식을 인코딩합니다.
A*x <= b
,
여기서 x
는 N
개의 변수 x(:)
으로 구성된 열 벡터이고, A
는 크기가 M
×N
인 행렬입니다.
예를 들어, 다음 부등식을 살펴보겠습니다.
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
Aeq
— 선형 등식 제약 조건
실수 행렬
선형 등식 제약 조건으로, 실수 행렬로 지정됩니다. 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];
예: 합이 1이 되도록 x 성분을 지정하려면 Aeq = ones(1,N)
및 beq = 1
을 지정하십시오.
데이터형: double
beq
— 선형 등식 제약 조건
실수형 벡터
선형 등식 제약 조건으로, 실수 벡터로 지정됩니다. beq
는 Aeq
행렬과 관련된, 요소를 Me
개 가진 벡터입니다. beq
를 행 벡터로 전달하면 솔버는 내부적으로 beq
를 열 벡터 beq(:)
으로 변환합니다. 대규모 문제의 경우, beq
를 희소 벡터로 전달하십시오.
beq
는 다음과 같이 Me
개의 선형 등식을 인코딩합니다.
Aeq*x = beq
,
여기서 x
는 N
개의 변수 x(:)
으로 구성된 열 벡터이고, Aeq
는 크기가 Me
×N
인 행렬입니다.
예를 들어, 다음 등식을 살펴보겠습니다.
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
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 | 음이 아닌 실수입니다. 목적 함수에 대해 내부적으로 계산된 상한(
| 1e-6 ("highs" 의 경우), 0 ("legacy" 의 경우) |
Algorithm | 다음 최적화 알고리즘을 선택합니다.
| "highs" |
ConstraintTolerance |
" | 1e-6 ("highs" 의 경우), 1e-4 ("legacy" 의 경우) |
Display | 표시 수준입니다(반복 과정 표시 참조):
| "iter" |
MaxNodes | intlinprog 가 분기한정 과정에서 탐색하는 최대 노드 개수를 나타내는 순양수(Strictly Positive) 정수입니다. | 1e7 |
MaxTime | intlinprog 가 실행되는 최대 시간(단위: 초)을 나타내는 음이 아닌 실수입니다. | 7200 |
ObjectiveCutOff | -Inf 보다 큰 실수입니다. 분기한정 계산 중에 intlinprog 는 선형 계획법 해가 ObjectiveCutOff 를 초과하는 목적 함수 값을 가지는 모든 노드를 삭제합니다. | Inf |
RelativeGapTolerance |
참고 사용자는 | 1e-4 |
레거시 알고리즘 | ||
BranchRule | 분기 생성을 위한 성분을 선택하는 규칙:
| 'reliability' |
CutGeneration | 절단 생성의 수준입니다(절단 생성 참조).
| 'basic' |
CutMaxIterations | 1 에서 50 사이의 정수로, 분기한정 단계에 진입하기 전에 모든 절단 생성 방법을 거치는 패스의 횟수입니다. CutGeneration 옵션을 'none' 으로 설정하여 절단 생성을 비활성화할 수 있습니다. | 10 |
Heuristics | 실현가능점을 찾기 위한 알고리즘입니다(실현 가능한 해를 구하는 데 활용할 수 있는 발견법 참조).
| 'basic' |
HeuristicsMaxNodes | intlinprog 가 실현가능점에 대한 분기한정 탐색에서 탐색할 수 있는 노드 수의 범위를 지정하는 순양수(Strictly Positive) 정수입니다. 'rss' 및 'rins' 에만 적용됩니다. 실현 가능한 해를 구하는 데 활용할 수 있는 발견법 항목을 참조하십시오. | 50 |
IntegerPreprocess | 정수 전처리 유형입니다(혼합 정수 계획 전처리 참조).
| 'basic' |
IntegerTolerance | 1e-10 에서 1e-3 사이의 실수로, 해 x 의 성분이 정수로 간주될 수 있는 최대 편차입니다. IntegerTolerance 는 중지 기준이 아닙니다. | 1e-5 |
LPMaxIterations | 순양수 정수로, 분기한정 과정 중에 실행되는 단체 알고리즘의 노드당 최대 반복 횟수입니다. |
이 표현식에서 |
LPOptimalityTolerance | 음이 아닌 실수입니다. 여기서 감소된 비용은 기저로 사용되는 변수에 대한 LPOptimalityTolerance 를 초과해야 합니다. | 1e-7 |
LPPreprocess | 완화된 선형 계획의 해에 사용할 전처리 유형입니다(선형 계획 전처리 참조).
| 'basic' |
MaxFeasiblePoints | 순양수(Strictly Positive) 정수입니다. intlinprog 는 MaxFeasiblePoints 정수 실현가능점을 구한 경우 중지됩니다. | Inf |
NodeSelection | 다음으로 탐색할 노드를 선택합니다.
| 'simplebestproj' |
ObjectiveImprovementThreshold | 음이 아닌 실수입니다. intlinprog 는 목적 함수 값이 적어도 ObjectiveImprovementThreshold 보다 낮은, 즉 다음을 충족하는 다른 해를 찾은 경우에만 현재 실현 가능 해를 변경합니다. (fold – fnew)/(1 + |fold|) > ObjectiveImprovementThreshold. | 0 |
OutputFcn | 최적화 함수가 이벤트에서 호출하는 하나 이상의 함수입니다. 함수 핸들 또는 함수 핸들로 구성된 셀형 배열인
사용자 지정 출력 함수를 작성하는 방법에 대한 자세한 내용은 intlinprog Output Function and Plot Function Syntax 항목을 참조하십시오. | [] |
PlotFcn | 알고리즘이 실행되는 동안 다양한 진행률 측정값을 플로팅합니다. 미리 정의된 플롯에서 선택하거나 사용자가 직접 작성할 수 있습니다.
사용자 지정 플롯 함수를 작성하는 방법에 대한 자세한 내용은 intlinprog Output Function and Plot Function Syntax 항목을 참조하십시오. | [] |
RootLPAlgorithm | 다음과 같은 선형 계획 문제를 풀기 위한 알고리즘입니다.
| 'dual-simplex' |
RootLPMaxIterations | 음이 아닌 정수로, 초기 선형 계획법 문제를 풀기 위해 실행되는 최대 단체 알고리즘 반복 횟수입니다. |
이 표현식에서 |
예: options = optimoptions('intlinprog','MaxTime',120)
problem
— 입력값과 옵션을 캡슐화하는 구조체
구조체
입력값과 옵션을 캡슐화하는 구조체로, 다음 필드를 사용하여 지정됩니다.
f | 목적 함수 f'*x 를 나타내는 벡터(필수) |
intcon | 정수 값을 받는 변수를 나타내는 벡터(필수) |
Aineq | 선형 부등식 제약 조건 Aineq*x ≤ bineq 에 포함되는 행렬 |
| 선형 부등식 제약 조건 Aineq*x ≤ bineq 에 포함되는 벡터 |
| 선형 등식 제약 조건 Aeq*x = beq 에 포함되는 행렬 |
| 선형 등식 제약 조건 Aeq*x = beq 에 포함되는 벡터 |
lb | 하한으로 구성된 벡터 |
ub | 상한으로 구성된 벡터 |
x0 | 초기 실현가능점 |
solver | 'intlinprog' (필수) |
| 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
— 해(Solution)
실수형 벡터
해로, f'*x
를 최소화하는 벡터로 반환됩니다. 여기에는 모든 범위, 정수 제약 조건, 선형 제약 조건이 적용됩니다.
문제가 실현 가능하지 않거나 비유계인 경우, x
는 []
입니다.
fval
— 목적 함수 값
실수형 스칼라
목적 함수 값으로, 해 x
에서 계산된 스칼라 값 f'*x
로 반환됩니다.
문제가 실현 가능하지 않거나 비유계인 경우, fval
은 []
입니다.
exitflag
— 알고리즘 중지 조건
정수
알고리즘 중지 조건으로, 알고리즘이 중지된 이유를 나타내는 정수로 반환됩니다. 다음에는 exitflag
의 값과 이에 해당하는, intlinprog
가 중지된 이유가 나열되어 있습니다.
| 이 해는 상대 |
|
|
|
|
|
|
|
|
| 실현가능점을 찾지 못했습니다. |
| 루트 LP 문제가 비유계입니다. |
| 솔버가 실현가능성을 잃었습니다. |
종료 메시지에 허용오차 초과와 같이 intlinprog
가 중지된 이유에 대한 자세한 정보가 제공될 수 있습니다.
종료 플래그 3
과 -9
는 실현불가능성이 큰 해와 관계가 있습니다. 이런 종료 플래그는 보통 큰 조건수를 갖는 선형 제약 조건 행렬이나 큰 해 성분이 있는 문제에서 비롯됩니다. 이런 문제를 해결하려면 계수 행렬을 스케일링하거나 중복된 선형 제약 조건을 제거하거나 변수에 대해 더 엄밀한 범위를 지정해 보십시오.
output
— 풀이 과정 요약
구조체
풀이 과정 요약으로, 최적화 과정에 대한 정보를 포함하는 구조체로 반환됩니다.
|
참고 사용자는 |
| 분기한정 알고리즘에서
|
| 발견된 정수 실현가능점의 개수입니다.
|
|
|
| 위반된 제약 조건에 대해 양수를 나타내는 제약 조건 위반 값입니다.
|
| 종료 메시지입니다. |
제한 사항
해
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
는f
,b
또는ub
의 계수와 같은 문제의 성분이 절댓값1e20
을 초과할 수 없도록 하며("legacy"
알고리즘의 경우1e25
), 선형 제약 조건 행렬A
와Aeq
가 절댓값1e15
와 같거나 이를 초과하는 것을 허용하지 않습니다. 이러한 문제에intlinprog
를 실행하려고 하면intlinprog
가 오류를 발생시킵니다.
팁
이진 변수를 지정하려면 변수를
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'
를 사용하는 다른 설정을 사용하여 좋은 결과를 얻을 수 있습니다.intlinprog
는bintprog
를 대체합니다.intlinprog
를 사용하기 위해 이전bintprog
코드를 업데이트하려면 다음과 같이 변경하십시오.intcon
을1:numVars
로 설정합니다. 여기서numVars
는 문제에 포함된 변수의 개수입니다.lb
를zeros(numVars,1)
로 설정합니다.ub
를ones(numVars,1)
로 설정합니다.관련된 모든 옵션을 업데이트합니다.
optimoptions
를 사용하여intlinprog
에 대한 옵션을 만듭니다.bintprog
에 대한 호출을 다음과 같이 변경합니다.[x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options) % Change your call to: [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,x0,options)
대체 기능
앱
최적화 라이브 편집기 작업은 intlinprog
에 대한 시각적 인터페이스를 제공합니다.
버전 내역
R2014a에 개발됨R2024a: 새 "highs"
알고리즘이 디폴트 값임
intlinprog
는 Algorithm
옵션을 알고리즘으로 가지며, 또한 새로운 디폴트 알고리즘을 가집니다. "highs"
알고리즘은 오픈소스 HiGHS 코드를 기반으로 합니다. 현재 "highs"
알고리즘은 출력 함수 또는 플롯 함수를 지원하지 않습니다.
이전 알고리즘을 사용하려면 optimoptions
를 사용하여 Algorithm="legacy"
를 설정하십시오.
"legacy"
알고리즘에 대한 IntegerTolerance
옵션 값의 허용 가능 범위와 같이 ConstraintTolerance
옵션 값의 허용 가능 범위도 이제 두 알고리즘 모두에 대해 1e-10
에서 1e-3
이 됩니다.
R2019a: 디폴트 BranchRule
은 'reliability'
임
BranchRule
옵션의 디폴트 값은 'maxpscost'
가 아니라 'reliability'
입니다. 테스트 결과에 따르면, 풀이 시간 및 탐색한 분기 노드 개수 두 가지 측면 모두에서 이 값이 다수의 문제에서 더 뛰어난 성능을 제공했습니다.
몇 가지 문제에서는 이전의 분기 규칙이 더 나은 성능을 보입니다. 이전 동작을 원한다면 BranchRule
옵션을 'maxpscost'
로 설정하십시오.
참고 항목
linprog
| mpsread
| optimoptions
| prob2struct
| 최적화
MATLAB 명령
다음 MATLAB 명령에 해당하는 링크를 클릭했습니다.
명령을 실행하려면 MATLAB 명령 창에 입력하십시오. 웹 브라우저는 MATLAB 명령을 지원하지 않습니다.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- 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)