이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

intlinprog

혼합 정수 선형 계획법(MILP)

혼합 정수 선형 계획법 솔버입니다.

다음으로 지정된 문제의 최솟값을 구합니다.

minxfTx subject to {x(intcon) are integersAxbAeqx=beqlbxub.

f, x, intcon, b, beq, lb, ub는 벡터이고 A와 Aeq는 행렬입니다.

f, intcon, lb, ub를 벡터 또는 배열로 지정할 수 있습니다. 행렬 인수 항목을 참조하십시오.

구문

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

설명

예제

x = intlinprog(f,intcon,A,b)는 최솟값 f'*x를 구합니다. 여기서는 intconx 성분은 정수이고 A*x ≤ b이라는 조건이 적용됩니다.

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 구조체를 가져올 수 있습니다.

예제

[x,fval,exitflag,output] = intlinprog(___)는 위에 설명된 임의의 입력 인수에 대해 fval = f'*x, 종료 상황을 설명하는 값 exitflag, 그리고 최적화 과정에 대한 정보를 포함하는 구조체 output을 반환합니다.

예제

모두 축소

다음 문제를 풀어 보겠습니다.

목적 함수 벡터와 정수 변수로 구성된 벡터를 작성합니다.

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)
LP:                Optimal objective value is 59.000000.                                            


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
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 binary

intlinprog를 호출합니다.

x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
x = 3×1

         0
    5.5000
    1.0000

초기 실현가능점을 사용하는 경우와 사용하지 않는 경우에 정수 계획법 문제를 푸는 데 실행되는 스텝의 개수를 비교합니다. 문제에는 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);
LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1590.479592.                                                      

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
   10000      0.86         0              -              -                                          
   10947      0.92         1   2.481000e+03   3.585818e+01                                          
   14148      1.19         2   2.073000e+03   2.319190e+01                                          
   17131      1.44         3   1.854000e+03   1.180593e+01                                          
   17777      1.50         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).

비교를 위해 초기 실현가능점을 사용하여 해를 구합니다.

x0 = [8 62 23 103 53 84 46 34];
[x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);
LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1590.479592.                                                      
                   Relative gap is 59.21%.                                                         

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
    4535      0.62         2   2.262000e+03   2.965091e+01                                          
    6516      0.83         3   1.854000e+03   1.412399e+01                                          
    7795      0.94         3   1.854000e+03   2.695418e-01                                          
    7825      0.94         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).
  • 초기점을 사용하지 않는 경우 intlinprog는 약 30,000개의 분기한정 스텝을 실행합니다.

  • 초기점을 사용하는 경우 intlinprog는 약 5,000개의 스텝을 실행합니다.

초기점을 제공하는 것이 항상 도움이 되는 것은 아닙니다. 이 문제에서는 초기점을 제공함으로써 시간과 계산 스텝을 절약할 수 있습니다. 그러나, 일부 문제에서는 초기점을 제공할 경우 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
    5.5000
    1.0000

다음 문제를 풀어 보겠습니다.

이때 반복 과정을 표시합니다. problem 구조체를 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
options = optimoptions('intlinprog','Display','off');

입력값을 문제 구조체에 삽입합니다. 솔버 이름을 포함시킵니다.

problem = struct('f',f,'intcon',intcon,...
    'Aineq',A,'bineq',b,'Aeq',Aeq,'beq',beq,...
    'lb',lb,'ub',ub,'options',options,...
    'solver','intlinprog');

솔버를 실행합니다.

x = intlinprog(problem)
x = 3×1

         0
    5.5000
    1.0000

출력값을 더 추가하고 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)
LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
x = 3×1

         0
    5.5000
    1.0000

fval = -12
exitflag = 1
output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found....'

output 구조체에 numnodes0으로 표시됩니다. 이는 intlinprog가 분기 전에 문제를 풀었음을 의미합니다. 이는 결과를 신뢰할 수 있음을 나타냅니다. 또한, absolutegap 필드와 relativegap 필드가 0입니다. 이 또한 결과를 신뢰할 수 있음을 나타냅니다.

입력 인수

모두 축소

계수 벡터로, 실수형 벡터나 실수형 배열로 지정됩니다. 계수 벡터는 목적 함수 f'*x를 나타냅니다. 이 표기법은 f가 열 벡터라고 가정하지만, 원하는 경우 자유롭게 행 벡터 또는 배열을 사용할 수 있습니다. 내부적으로 linprogf를 열 벡터 f(:)으로 변환합니다.

f = []을 지정할 경우 intlinprog는 목적 함수를 최소화하려고 하지 않고 실현가능점을 구하려고 합니다.

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

데이터형: double

정수 제약 조건으로 구성된 벡터로, 양의 정수로 구성된 벡터로 지정됩니다. intcon의 값은 정수 값을 갖는 결정 변수 x의 성분을 나타냅니다. intcon1에서 numel(f)까지의 값을 가집니다.

intcon은 배열일 수도 있습니다. 내부적으로 intlinprog는 배열 intcon을 벡터 intcon(:)으로 변환합니다.

예: intcon = [1,2,7]x(1), x(2), x(7)이 정수 값만 받는다는 것을 의미합니다.

데이터형: double

선형 부등식 제약 조건 행렬로, double형으로 구성된 행렬로 지정됩니다. A는 제약 조건 A*x  b에서 선형 계수를 나타냅니다. A의 크기는 MxN이며, 여기서 M은 제약 조건 개수이고 N = numel(f)입니다. 메모리를 절약하기 위해 A를 희소 형식으로 지정할 수 있습니다.

예: A = [4,3;2,0;4,-1];은 두 개의 결정 변수(두 열)에 대한 세 개의 선형 부등식(세 행)을 의미합니다.

데이터형: double

선형 부등식 제약 조건 벡터로, double형으로 구성된 벡터로 지정됩니다. b는 제약 조건 A*x  b에서 상수 벡터를 나타냅니다. b는 길이가 M이며, 여기서 AMxN입니다.

예: [4,0]

데이터형: double

선형 등식 제약 조건 행렬로, double형으로 구성된 행렬로 지정됩니다. Aeq는 제약 조건 Aeq*x = beq에서 선형 계수를 나타냅니다. Aeq의 크기는 MeqxN이며, 여기서 Meq는 제약 조건 개수이고 N = numel(f)입니다. 메모리를 절약하기 위해 Aeq를 희소 형식으로 지정할 수 있습니다.

예: A = [4,3;2,0;4,-1];은 두 개의 결정 변수(두 열)에 대한 세 개의 선형 부등식(세 행)을 의미합니다.

데이터형: double

선형 등식 제약 조건 벡터로, double형으로 구성된 벡터로 지정됩니다. beq는 제약 조건 Aeq*x = beq에서 상수 벡터를 나타냅니다. beq는 길이가 Meq이며, 여기서 AeqMeqxN입니다.

예: [4,0]

데이터형: double

하한으로, double형으로 구성된 벡터 또는 배열로 지정됩니다. lblb  x  ub에서 요소별 하한을 나타냅니다.

내부적으로 intlinprog는 배열 lb를 벡터 lb(:)으로 변환합니다.

예: lb = [0;-Inf;4]x(1) ≥ 0, x(3) ≥ 4을 의미합니다.

데이터형: double

상한으로, double형으로 구성된 벡터 또는 배열로 지정됩니다. ublb  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를 사용하는 방법에 대한 권장 사항은 항목을 참조하십시오.

x0은 모든 제약 조건에 대해 실현 가능해야 합니다. x0이 실현 가능하지 않을 경우 솔버가 오류를 표시합니다. 실현 가능한 x0을 모르면 x0 = []을 설정하십시오.

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

데이터형: double

intlinprog에 대한 옵션으로, optimoptions의 출력값으로 지정됩니다.

일부 옵션은 optimoptions 표시에 나타나지 않습니다. 이러한 옵션은 기울임꼴로 표시되어 있습니다. 자세한 내용은 View Options 항목을 참조하십시오.

옵션설명디폴트
AbsoluteGapTolerance

음이 아닌 실수입니다. 목적 함수에 대해 내부적으로 계산된 상한(U)과 하한(L) 사이의 차이가 AbsoluteGapTolerance보다 작거나 같은 경우 intlinprog 실행이 중지됩니다.

U – L <= AbsoluteGapTolerance.

0
BranchRule

분기 생성을 위한 성분을 선택하는 규칙:

  • 'maxpscost' — 최대 의사 비용(pseudocost)을 갖는 소수 성분입니다. 분기한정(Branch-and-Bound) 항목을 참조하십시오.

  • 'strongpscost' — 최대 의사 비용과 'maxpscost'보다 더 정확한 의사 비용 추정값을 갖는 소수 성분입니다. 분기한정(Branch-and-Bound) 항목을 참조하십시오.

  • 'reliability' — 최대 의사 비용과 'strongpscost'보다 훨씬 더 정확한 의사 비용 추정값을 갖는 소수 성분입니다. 분기한정(Branch-and-Bound) 항목을 참조하십시오.

  • 'mostfractional' — 소수부가 1/2에 가장 가까운 성분입니다.

  • 'maxfun' — 목적 벡터 f의 절댓값에서 대응하는 최대 성분을 갖는 소수 성분입니다.

'maxpscost'
ConstraintTolerance선형 제약 조건과의 최대 차이로, 1e-9부터 1e-3까지의 실수입니다. 이 최대 차이 이내라면 선형 제약 조건을 충족하는 것으로 간주됩니다. ConstraintTolerance는 중지 기준이 아닙니다.1e-4
CutGeneration

절단 생성의 수준입니다(절단 생성 참조).

  • 'none' — 절단이 없습니다. CutGenMaxIter가 무의미해집니다.

  • 'basic' — 일반적인 절단 생성입니다.

  • 'intermediate' — 더 많은 절단 유형을 사용합니다.

  • 'advanced' — 대부분의 절단 유형을 사용합니다.

'basic'
CutMaxIterations1에서 50 사이의 정수로, 분기한정 단계에 진입하기 전에 모든 절단 생성 방법을 거치는 패스의 횟수입니다. CutGeneration 옵션을 'none'으로 설정하여 절단 생성을 비활성화할 수 있습니다.10
Display

표시 수준입니다(반복 표시 참조):

  • 'off' 또는 'none' — 반복 과정 표시 안 함

  • 'final' — 최종 값만 표시

  • 'iter' — 반복 과정 표시

'iter'
Heuristics

실현가능점을 찾기 위한 알고리즘입니다(실현 가능한 해를 구하는 데 활용할 수 있는 발견법 참조).

  • 'basic'

  • 'intermediate'

  • 'advanced'

  • 'rss'

  • 'rins'

  • 'round'

  • 'diving'

  • 'rss-diving'

  • 'rins-diving'

  • 'round-diving'

  • 'none'

'basic'
HeuristicsMaxNodesintlinprog가 실현가능점에 대한 분기한정 탐색에서 탐색할 수 있는 노드 수의 범위를 지정하는 순양수(Strictly Positive) 정수입니다. 'rss''rins'에만 적용됩니다. 실현 가능한 해를 구하는 데 활용할 수 있는 발견법 항목을 참조하십시오.50
IntegerPreprocess

정수 전처리 유형입니다(혼합 정수 계획 전처리 참조).

  • 'none' — 극히 적은 정수 전처리 스텝을 사용합니다.

  • 'basic' — 보통 정도 개수의 정수 전처리 스텝을 사용합니다.

  • 'advanced' — 사용 가능한 모든 정수 전처리 스텝을 사용합니다.

'basic'
IntegerTolerance1e-6에서 1e-3 사이의 실수로, 해 x의 성분이 정수로 간주될 수 있는 최대 편차입니다. IntegerTolerance는 중지 기준이 아닙니다.1e-5
LPMaxIterations순양수 정수로, 분기한정 과정 중에 실행되는 단체 알고리즘의 노드당 최대 반복 횟수입니다.

max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables))

이 표현식에서 numberOfEqualitiesAeq의 행 개수를 의미하고, numberOfInequalitiesA의 행 개수를 의미하며, numberOfVariablesf의 요소 개수를 의미합니다.

LPOptimalityTolerance음이 아닌 실수입니다. 여기서 감소된 비용은 기저로 사용되는 변수에 대한 LPOptimalityTolerance를 초과해야 합니다.1e-7
LPPreprocess

완화된 선형 계획의 해에 사용할 전처리 유형입니다(선형 계획 전처리 참조).

  • 'none' — 전처리가 없습니다.

  • 'basic' — 전처리를 사용합니다.

'basic'
MaxNodesintlinprog가 분기한정 과정에서 탐색하는 최대 노드 개수를 나타내는 순양수(Strictly Positive) 정수입니다.1e7
MaxFeasiblePoints순양수(Strictly Positive) 정수입니다. intlinprogMaxFeasiblePoints 정수 실현가능점을 구한 경우 중지됩니다.Inf
MaxTimeintlinprog가 실행되는 최대 시간(단위: 초)을 나타내는 양의 실수입니다.7200
NodeSelection

다음으로 탐색할 노드를 선택합니다.

  • 'simplebestproj' — 최적의 투영입니다. 분기한정(Branch-and-Bound) 항목을 참조하십시오.

  • 'minobj' — 최소 목적 함수를 갖는 노드를 탐색합니다.

  • 'mininfeas' — 정수 실현불가능성의 합이 가장 작은 노드를 탐색합니다. 분기한정(Branch-and-Bound) 항목을 참조하십시오.

'simplebestproj'
ObjectiveCutOff-Inf보다 큰 실수입니다. 분기한정 계산 중에 intlinprog는 선형 계획법 해가 ObjectiveCutOff를 초과하는 목적 함수 값을 가지는 모든 노드를 삭제합니다.Inf
ObjectiveImprovementThreshold음이 아닌 실수입니다. intlinprog는 목적 함수 값이 적어도 ObjectiveImprovementThreshold보다 낮은, 즉 다음을 충족하는 다른 해를 찾은 경우에만 현재 실현 가능 해를 변경합니다. (fold – fnew)/(1 + |fold|) > ObjectiveImprovementThreshold.0
OutputFcn

이벤트가 발생했을 때 최적화 함수가 'savemilpsolutions', 함수 핸들 또는 함수 핸들로 구성된 셀형 배열로 호출하는 하나 이상의 함수를 지정합니다. 사용자 지정 출력 함수에 대해서는 함수 핸들을 전달합니다.

  • 'savemilpsolutions'는 작업 공간의 xIntSol 행렬에 정수 실현가능점을 수집합니다. 이 행렬의 각 열은 하나의 정수 실현가능점입니다.

사용자 지정 출력 함수를 작성하는 방법에 대한 자세한 내용은 intlinprog Output Functions and Plot Functions 항목을 참조하십시오.

[]
PlotFcn

알고리즘이 실행되는 동안 다양한 진행률 측정값을 플로팅합니다. 미리 정의된 플롯에서 선택하거나 사용자가 직접 작성할 수 있습니다. 'optimplotmilp', 함수 핸들 또는 함수 핸들로 구성된 셀형 배열을 전달합니다. 사용자 지정 플롯 함수의 경우, 함수 핸들을 전달하십시오. 디폴트 값은 없음([])입니다.

  • 'optimplotmilp'는 해의 목적 함수 값에 대해 내부적으로 계산된 상한과 하한을 플로팅합니다.

사용자 지정 플롯 함수를 작성하는 방법에 대한 자세한 내용은 intlinprog Output Functions and Plot Functions 항목을 참조하십시오.

[]
RelativeGapTolerance

0에서 1 사이의 실수입니다. 목적 함수에 대해 내부적으로 계산된 상한(U)과 하한(L)의 상대 오차가 RelativeGapTolerance보다 작거나 같은 경우 intlinprog가 중지합니다.

(U – L) / (abs(U) + 1) <= RelativeGapTolerance.

intlinprog는 다음과 같이 대규모 L 크기에 대해 허용오차를 자동으로 수정합니다.

허용오차 = min(1/(1+|L|), RelativeGapTolerance)

참고

RelativeGapTolerance를 소수로 지정하면 반복 표시 화면과 output.relativegap이 간격을 백분율, 즉 측정된 상대적인 간격에 100을 곱한 값으로 보고합니다. 종료 메시지가 상대적인 간격을 언급하는 경우 이 값은 백분율이 아니라 측정된 상대적인 간격에 해당합니다.

1e-4
RootLPAlgorithm

다음과 같은 선형 계획 문제를 풀기 위한 알고리즘입니다.

  • 'dual-simplex' — 쌍대 문제 단체 알고리즘

  • 'primal-simplex' — 원문제 단체 알고리즘

'dual-simplex'
RootLPMaxIterations음이 아닌 정수로, 초기 선형 계획법 문제를 풀기 위해 실행되는 최대 단체 알고리즘 반복 횟수입니다.

max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables))

이 표현식에서 numberOfEqualitiesAeq의 행 개수를 의미하고, numberOfInequalitiesA의 행 개수를 의미하며, numberOfVariablesf의 요소 개수를 의미합니다.

예: options = optimoptions('intlinprog','MaxTime',120)

입력값과 옵션을 캡슐화하는 구조체로, 다음 필드를 사용하여 지정됩니다.

f목적 함수 f'*x를 나타내는 벡터(필수)
intcon정수 값을 받는 변수를 나타내는 벡터(필수)
Aineq선형 부등식 제약 조건 Aineq*x  bineq에 포함되는 행렬

bineq

선형 부등식 제약 조건 Aineq*x  bineq에 포함되는 벡터

Aeq

선형 등식 제약 조건 Aeq*x = beq에 포함되는 행렬

beq

선형 등식 제약 조건 Aeq*x = beq에 포함되는 벡터
lb하한으로 구성된 벡터
ub상한으로 구성된 벡터
x0초기 실현가능점
solver'intlinprog'(필수)

options

optimoptions를 사용하여 생성되는 옵션(필수)

문제 구조체에서는 적어도 다음 필드를 지정해야 합니다. 기타 다른 필드는 선택 사항입니다.

  • f

  • intcon

  • solver

  • options

예: problem.f = [1,2,3];
problem.intcon = [2,3];
problem.options = optimoptions('intlinprog');
problem.Aineq = [-3,-2,-1];
problem.bineq = -20;
problem.lb = [-6.1,-1.2,7.3];
problem.solver = 'intlinprog';

데이터형: struct

출력 인수

모두 축소

해로, f'*x를 최소화하는 벡터로 반환됩니다. 여기에는 모든 범위, 정수 제약 조건, 선형 제약 조건이 적용됩니다.

문제가 실현 가능하지 않거나 비유계인 경우, x[]입니다.

목적 함수 값으로, 해 x에서 계산된 스칼라 값 f'*x로 반환됩니다.

문제가 실현 가능하지 않거나 비유계인 경우, fval[]입니다.

알고리즘 중지 조건으로, 알고리즘이 중지된 이유를 나타내는 정수로 반환됩니다. 다음에는 exitflag의 값과 이에 해당하는, intlinprog가 중지된 이유가 나열되어 있습니다.

2

intlinprog가 중도에 중지되었습니다. 정수 실현가능점을 찾았습니다.

1

intlinprog가 해 x로 수렴되었습니다.

0

intlinprog가 중도에 중지되었습니다. 정수 실현가능점을 찾지 못했습니다.

-1

intlinprog가 출력 함수나 플롯 함수에 의해 중지되었습니다.

-2

실현가능점을 찾지 못했습니다.

-3

루트 LP 문제가 비유계입니다.

종료 메시지에 허용오차 초과와 같이 intlinprog가 중지된 이유에 대한 자세한 정보가 제공될 수 있습니다.

풀이 과정 요약으로, 최적화 과정에 대한 정보를 포함하는 구조체로 반환됩니다.

relativegap

분기한정 알고리즘에서 intlinprog가 계산하는 목적 함수의 상한(U)과 하한(L) 사이의 상대적인 백분율 차이입니다.

relativegap = 100*(U - L) / (abs(U) + 1)

intcon = []이면 relativegap = []입니다.

참고

RelativeGapTolerance를 소수로 지정하면 반복 표시 화면과 output.relativegap이 간격을 백분율, 즉 측정된 상대적인 간격에 100을 곱한 값으로 보고합니다. 종료 메시지가 상대적인 간격을 언급하는 경우 이 값은 백분율이 아니라 측정된 상대적인 간격에 해당합니다.

absolutegap

분기한정 알고리즘에서 intlinprog가 계산하는 목적 함수의 상한과 하한 사이의 차이입니다.

intcon = []이면 absolutegap = []입니다.

numfeaspoints

발견된 정수 실현가능점의 개수입니다.

intcon = []이면 numfeaspoints = []입니다. 또한, 완화된 초기 문제가 실현 가능하지 않을 경우 numfeaspoints = []입니다.

numnodes

분기한정 알고리즘의 노드 개수입니다. 전처리 또는 초기 절단 중에 해가 발견된 경우 numnodes = 0입니다.

intcon = []이면 numnodes = []입니다.

constrviolation

위반된 제약 조건에 대해 양수인 제약 조건 위반입니다.

constrviolation = max([0; norm(Aeq*x-beq, inf); (lb-x); (x-ub); (Ai*x-bi)])

message

종료 메시지입니다.

제한 사항

  • x(intCon)에서 정수 값을 가져야 하는 일부 성분이 정확하게는 정수가 아닐 때가 많습니다. intlinprog는 정수의 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가 경고 메시지를 표시합니다. 이러한 경고가 표시되면 해를 검토하여 해에서 정수 값을 가져야 하는 성분이 정수에 가까운지 확인하십시오.

  • intlinprogf의 계수, A의 계수 또는 ub의 계수와 같이 문제에 포함된 성분의 절댓값이 1e25를 초과하는 것을 허용하지 않습니다. 이러한 문제에 intlinprog를 실행하려고 하면 intlinprog가 오류를 발생시킵니다.

  • 현재로서는 최적화 앱에서 intlinprog를 실행할 수 없습니다.

  • 이진 변수를 지정하려면 변수를 intcon에서 정수가 되도록 설정하고 이에 대한 하한과 상한으로 각각 01을 지정하십시오.

  • 희소 선형 제약 조건 행렬 AAeq를 지정하면 메모리를 절약할 수 있습니다. 하지만, bbeq에는 희소 행렬을 사용할 수 없습니다.

  • x0 인수를 포함시키는 경우 intlinprog는 발견법에 이 값을 사용합니다. 특히, rins 및 유도 급강하와 같은 향상 발견법은 x0에서 시작하여 점을 향상시키려고 시도할 수 있습니다. 따라서 x0을 제공할 때 'Heuristics' 옵션을 'rins-diving'으로 설정하는 것이 효과적일 수 있습니다. 하지만, 간격이 작으면 발견법이 실행되지 않으므로 'rins-diving'을 선택하는 것이 항상 실행 시간을 향상시키는 것은 아닙니다.

  • 정수 성분에 대한 논리형 인덱스(정수를 나타내는 1을 값으로 갖는 이진 벡터를 의미함)를 제공하려면 find를 사용하여 intcon 형식으로 변환하십시오. 예를 들면 다음을 입력합니다.

    logicalindices = [1,0,0,1,1,0,0];
    intcon = find(logicalindices)
    intcon =
    
         1     4     5
  • intlinprogbintprog를 대체합니다. intlinprog를 사용하기 위해 이전 bintprog 코드를 업데이트하려면 다음과 같이 변경하십시오.

    • intcon1:numVars로 설정합니다. 여기서 numVars는 문제에 포함된 변수의 개수입니다.

    • lbzeros(numVars,1)로 설정합니다.

    • ubones(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)

R2014a에 개발됨