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를 사용하십시오. 두 가지 최적화 접근법에 대한 설명은 먼저 문제 기반 접근법 또는 솔버 기반 접근법 중 선택하기 항목을 참조하십시오.

x = intlinprog(f,intcon,A,b)는 최솟값 f'*x를 구합니다. 여기서는 intcon의 x 성분은 정수 또는 확장된 정수 변수이고 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 구조체를 가져올 수 있습니다. 또는 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.00 (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     2.6s

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.64 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             21163
  LP iterations     19608 (total)
                    223 (strong br.)
                    76 (separation)
                    1018 (heuristics)

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.

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

x0 = [8 62 23 103 53 84 46 34];
[x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);
Running HiGHS 1.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [3e+00, 4e+01]
  Cost   [2e+00, 2e+01]
  Bound  [0e+00, 0e+00]
  RHS    [8e+03, 1e+04]
Assessing feasibility of MIP using primal feasibility and integrality tolerance of       1e-06
Solution has               num          max          sum
Col     infeasibilities      0            0            0
Integer infeasibilities      0            0            0
Row     infeasibilities      0            0            0
Row     residuals            0            0            0
Presolving model
4 rows, 8 cols, 32 nonzeros  0s
4 rows, 8 cols, 27 nonzeros  0s

MIP start solution is feasible, objective value is 3901
Objective function is integral with scale 1

Solving MIP model with:
   4 rows
   8 cols (0 binary, 8 integer, 0 implied int., 0 continuous)
   27 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   0               3901             100.00%        0      0      0         0     0.0s
         0       0         0   0.00%   1554.047531     3901              60.16%        0      0      4         4     0.0s
 T    6266     708      2644  73.61%   1662.791423     3301              49.63%       20      6   9746     10699     1.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.9s

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.99 (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 객체를 만듭니다. 이진 변수를 지정하려면 하한이 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에 해당합니다. Algorithms 항목을 참조하십시오.

라이브 스크립트 열기

출력값을 더 추가하고 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.'

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

입력 인수

모두 축소

계수 벡터로, 실수형 벡터나 실수형 배열로 지정됩니다. 계수 벡터는 목적 함수 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(:)으로 변환합니다.

참고

반정수(semi-integer) 변수와 반연속 변수는 1e5를 초과하지 않는 순양수(Strictly Positive) 범위를 가져야 합니다.

예: 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];

예: 총합이 1보다 작거나 같도록 x 성분을 지정하려면 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];

예: 합이 1이 되도록 x 성분을 지정하려면 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

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

U – L <= AbsoluteGapTolerance.

1e-6("highs"의 경우), 0("legacy"의 경우)
Algorithm

다음 최적화 알고리즘을 선택합니다.

  • "highs"(디폴트 값)

  • "legacy"

"highs"
ConstraintTolerance

"highs" 알고리즘의 경우, 정수 또는 선형 제약 조건의 최대 허용 가능 위반을 나타내는 1e-10부터 1e-3까지의 실수 값입니다.

"legacy" 알고리즘의 경우, 선형 제약 조건과의 최대 차이로, 1e-10부터 1e-3까지의 실수 값입니다. 이 최대 차이 이내라면 선형 제약 조건을 충족하는 것으로 간주됩니다.

"ConstraintTolerance는 중지 기준이 아닙니다.

1e-6("highs"의 경우), 1e-4("legacy"의 경우)
Display

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

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

  • "final" — 최종 값만 표시

  • "iter" — 반복 과정 표시

"iter"
MaxFeasiblePoints순양수(Strictly Positive) 정수입니다. intlinprog는 MaxFeasiblePoints 정수 실현가능점을 구한 경우 중지됩니다.Inf
MaxNodesintlinprog가 분기한정 과정에서 탐색하는 최대 노드 개수를 나타내는 순양수(Strictly Positive) 정수입니다.1e7
MaxTimeintlinprog가 실행되는 최대 시간(단위: 초)을 나타내는 음이 아닌 실수입니다.7200
ObjectiveCutOff-Inf보다 큰 실수입니다. 분기한정 계산 중에 intlinprog는 선형 계획법 해가 ObjectiveCutOff를 초과하는 목적 함수 값을 가지는 모든 노드를 삭제합니다.Inf
OutputFcn

최적화 함수가 이벤트에서 호출하는 하나 이상의 함수입니다. 함수 핸들 또는 함수 핸들로 구성된 셀형 배열인 'savemilpsolutions'로 지정합니다. 사용자 지정 출력 함수에 대해서는 함수 핸들을 전달합니다. 출력 함수는 솔버를 중지할 수 있습니다.

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

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

[]
PlotFcn

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

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

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

[]
RelativeGapTolerance

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

"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를 소수로 지정하지만, 반복 과정 표시에서는 간격을 백분율, 즉 측정된 상대적인 간격에 100을 곱한 값으로 보고합니다. 종료 메시지가 상대적인 간격을 언급하는 경우 이 값은 백분율이 아니라 측정된 상대적인 간격에 해당합니다.

1e-4
레거시 알고리즘
BranchRule

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

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

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

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

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

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

'reliability'
CutGeneration

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

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

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

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

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

'basic'
CutMaxIterations1에서 50 사이의 정수로, 분기한정 단계에 진입하기 전에 모든 절단 생성 방법을 거치는 패스의 횟수입니다. CutGeneration 옵션을 'none'으로 설정하여 절단 생성을 비활성화할 수 있습니다.10
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-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' — 최적의 투영입니다. 분기한정(Branch-and-Bound) 항목을 참조하십시오.

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

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

'simplebestproj'
ObjectiveImprovementThreshold음이 아닌 실수입니다. intlinprog는 목적 함수 값이 적어도 ObjectiveImprovementThreshold보다 낮은, 즉 다음을 충족하는 다른 해를 찾은 경우에만 현재 실현 가능 해를 변경합니다. (fold – fnew)/(1 + |fold|) > ObjectiveImprovementThreshold.0
RootLPAlgorithm

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

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

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

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

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

이 표현식에서 numberOfEqualities는 Aeq의 행 개수를 의미하고, numberOfInequalities는 A의 행 개수를 의미하며, numberOfVariables는 f의 요소 개수를 의미합니다.

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

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

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를 소수로 지정하지만, 반복 과정 표시에서는 간격을 백분율, 즉 측정된 상대적인 간격에 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는 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에 개발됨

모두 확장

참고 항목

| | | | |

도움말 항목