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

설명

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

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

$\min_{x} f^{T} x subject to {\begin{array}{l} x (intcon) are integers or extended integers \\ bl \leq A \cdot x \leq b \\ Aeq \cdot x = beq \\ lb \leq x \leq ub . \end{array}$

f, x, b, bl, 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라는 조건이 적용됩니다. 또는 b가 요소를 2개 가진 셀형 배열 {bl,b}인 경우 bl ≤ 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을 반환합니다.

예제

모두 축소

선형 부등식이 있는 MILP 풀기

라이브 스크립트 열기

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

$\min_{x} (8 x_{1} + x_{2}) s u b j e c t t o {\begin{array}{llllllllllllllllllll} x_{2} i s a n i n t e g e r \\ x_{1} + 2 x_{2} \geq - 14 \\ - 4 x_{1} - x_{2} \leq - 33 \\ 2 x_{1} + x_{2} \leq 20 . \end{array}$

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

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.

모든 유형의 제약 조건이 있는 MILP 풀기

라이브 스크립트 열기

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

$\min_{x} (- 3 x_{1} - 2 x_{2} - x_{3}) s u b j e c t t o {\begin{array}{llllllllllllllllllll} x_{3} b i n a r y \\ x_{1}, x_{2} \geq 0 \\ x_{1} + x_{2} + x_{3} \leq 7 \\ 4 x_{1} + 2 x_{2} + x_{3} = 12 . \end{array}$

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

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.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.

초기점 사용하기

라이브 스크립트 열기

초기 실현가능점을 사용하는 경우와 사용하지 않는 경우에 정수 계획법 문제를 푸는 데 실행되는 스텝의 개수를 비교합니다. 문제에는 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.5s
 T   21917    1000      8515  86.43%   1736.378236     2113              17.82%       36      5   9873     24182     2.2s
 T   26514     250     10328  96.20%   1778.832142     1854               4.05%       31      5   4853     28216     2.5s
     26903       0     10609 100.00%   1854            1854               0.00%       39     11   3699     28606     2.5s

Solving report
  Status            Optimal
  Primal bound      1854
  Dual bound        1854
  Gap               0% (tolerance: 0.01%)
  P-D integral      0.332196201182
  Solution status   feasible
                    1854 (objective)
                    0 (bound viol.)
                    9.63673585375e-14 (int. viol.)
                    0 (row viol.)
  Timing            2.50 (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.111476662697
  Solution status   feasible
                    1854 (objective)
                    0 (bound viol.)
                    1.13686837722e-13 (int. viol.)
                    0 (row viol.)
  Timing            0.57 (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는 약 25,000회의 LP 반복과 25,000개의 분기한정 노드를 사용합니다.
초기점을 사용하는 경우 intlinprog가 사용하는 LP 반복 횟수는 1/3 미만으로 줄고, 노드 개수도 훨씬 크게 감소합니다. 해를 구하는 시간도 훨씬 더 빨라집니다.

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

문제 기반 접근법을 사용하여 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.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.

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에 해당합니다. Conversion to Solver Form 항목을 참조하십시오.

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.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.

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.'

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

입력 인수

모두 축소

`f` — 계수 벡터
실수형 벡터 | 실수형 배열

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

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

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

데이터형: double

`intcon` — 정수 변수 인덱스
정수 벡터 | `IntegerConstraint` 객체

정수 변수 인덱스로, 양의 정수 벡터나 integerConstraint 함수로 생성된 IntegerConstraint 객체로 지정됩니다. 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` — 선형 부등식 제약 조건
실수 행렬

선형 부등식 제약 조건으로, 실수 행렬로 지정됩니다. A는 M×N 행렬입니다. 여기서 M은 부등식 개수이고 N은 변수 개수(x0의 요소 개수)입니다. 대규모 문제의 경우, A를 희소 행렬로 전달하십시오.

A는 다음과 같이 M개의 선형 부등식을 인코딩합니다.

A*x <= b,

여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, b는 M개의 요소를 갖는 벡터입니다.

b가 요소를 2개 가진 셀형 배열 {bl,b}인 경우 A는 다음 선형 부등식을 인코딩합니다.

bl <= A*x <= b. (1)

예를 들어, 다음 부등식을 살펴보겠습니다.

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30,

다음 제약 조건을 입력하여 부등식을 지정합니다.

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

마찬가지로, 다음과 같은 추가 제약 조건이 있는 경우

4x₁ – x₂ ≥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

`b` — 선형 부등식 제약 조건
실수형 벡터 | 실수형 배열로 구성된, 요소를 2개 가진 셀형 배열

선형 부등식 제약 조건으로, 실수형 벡터로 지정되거나 실수형 배열로 구성된, 요소를 2개 가진 셀형 배열로 지정됩니다.

b가 요소를 M개 가진 벡터인 경우 b는 다음과 같이 M개의 선형 부등식을 인코딩합니다.
A*x <= b, (3)
여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, A는 크기가 M×N인 행렬입니다.
b가 요소를 2개 가진 셀형 배열 {bl,b}인 경우 bl과 b 중 하나 또는 둘 다 비어 있지 않아야 합니다. b의 비어 있지 않은 요소(entries)는 다음과 같은 선형 부등식을 인코딩하는 M개의 요소(element)를 포함합니다.
bl <= A*x <= b, (4)
여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, A는 크기가 M×N인 행렬입니다.

b 또는 bl을 행 벡터로 전달하면 솔버는 내부적으로 이를 열 벡터 b(:) 또는 bl(:)으로 변환합니다.

예를 들어, 다음 부등식을 살펴보겠습니다.

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30.

다음 제약 조건을 입력하여 부등식을 지정합니다.

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

다음과 같은 추가 제약 조건을 고려합니다.

4x₁ – x₂ ≥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` — 선형 등식 제약 조건
실수 행렬

선형 등식 제약 조건으로, 실수 행렬로 지정됩니다. Aeq는 Me×N 행렬입니다. 여기서 Me는 등식 개수이고 N은 변수 개수(f의 길이)입니다. 대규모 문제의 경우, Aeq를 희소 행렬로 전달하십시오.

Aeq는 다음과 같이 Me개의 선형 등식을 인코딩합니다.

Aeq*x = beq,

여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, beq는 Me개의 요소를 갖는 열 벡터입니다.

예를 들어, 다음 등식을 살펴보겠습니다.

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 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는 다음과 같이 Me개의 선형 등식을 인코딩합니다.

Aeq*x = beq,

여기서 x는 N개의 변수 x(:)으로 구성된 열 벡터이고, Aeq는 크기가 Me×N인 행렬입니다.

예를 들어, 다음 등식을 살펴보겠습니다.

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

다음 제약 조건을 입력하여 등식을 지정합니다.

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

예: x 성분의 합이 1이 되도록 지정하려면 Aeq = ones(1,N) 및 beq = 1을 사용하십시오.

데이터형: single | 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(:)으로 변환합니다.

intlinprog는 제공된 x0을 사용하려고 시도하며, 실현가능성을 위해 필요한 경우 점을 수정합니다.

x0을 제공하면 intlinprog가 수렴하는 데 걸리는 시간이 달라질 수 있습니다. x0이 솔버에 미치는 영향은 예측하기가 어렵습니다.

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

데이터형: double

`options` — `intlinprog`에 대한 옵션
`optimoptions`를 사용하여 생성되는 옵션

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

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

옵션	설명	디폴트 값
`AbsoluteGapTolerance`	음이 아닌 실수입니다. 목적 함수에 대해 내부적으로 계산된 상한(`U`)과 하한(`L`) 사이의 차이가 `AbsoluteGapTolerance`보다 작거나 같은 경우 `intlinprog` 실행이 중지됩니다. `U – L <= AbsoluteGapTolerance`.	`1e-6`
`ConstraintTolerance`	정수 또는 선형 제약 조건의 최대 허용 가능 위반을 나타내는 `1e-10`부터 `1e-3`까지의 실수 값입니다. "`ConstraintTolerance`는 중지 기준이 아닙니다.	`1e-6`
`Display`	표시 수준입니다(반복 과정 표시 참조): `"off"` 또는 `"none"` — 반복 과정 표시 안 함 `"final"` — 최종 값만 표시 `"iter"` — 반복 과정 표시	`"iter"`
`MaxFeasiblePoints`	순양수(Strictly Positive) 정수입니다. `intlinprog`는 `MaxFeasiblePoints` 정수 실현가능점을 구한 경우 중지됩니다.	`Inf`
`MaxNodes`	`intlinprog`가 분기한정 과정에서 탐색하는 최대 노드 개수를 나타내는 순양수(Strictly Positive) 정수입니다.	`1e7`
`MaxTime`	`intlinprog`가 실행되는 최대 시간(단위: 초)을 나타내는 음이 아닌 실수입니다.	`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`가 중지합니다. 중지 테스트는 다음과 같습니다. `(U – L)/\|U\| <= RelativeGapTolerance`. `U` = 0이고 `L` = 0인 경우, 반환되는 비율 `(U – L)/\|U\|`는 0입니다. `U` = 0이고 `L`이 0이 아닌 경우, 반환되는 비율은 `Inf`입니다. 참고 사용자는 `RelativeGapTolerance`를 소수로 지정하지만, 반복 과정 표시에서는 간격을 백분율, 즉 측정된 상대적인 간격에 100을 곱한 값으로 보고합니다. 종료 메시지가 상대적인 간격을 언급하는 경우 이 값은 백분율이 아니라 측정된 상대적인 간격에 해당합니다.	`1e-4`

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

`problem` — 입력값과 옵션을 캡슐화하는 구조체
구조체

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

`f`	목적 함수 `f'*x`를 나타내는 벡터(필수)
`intcon`	정수 값을 받는 변수를 나타내는 벡터 또는 확장된 정수 제약 조건을 지정하는 `integerConstraint` 객체(필수)
`Aineq`	선형 부등식 제약 조건 `Aineq*x` ≤ `bineq`에 포함되는 행렬
`bineq`	선형 부등식 제약 조건 `Aineqx` ≤ `bineq`에 포함되는 벡터, 또는 `bl` ≤`Aineqx` ≤ `b`의 경우 셀형 배열 `{bl,b}`. 셀형 배열을 사용하는 경우 배열은 단일 1×1 셀 형식이어야 합니다. 예를 들면 다음과 같습니다. bcons = {bl b}; problem.bineq = {bcons};
`Aeq`	선형 등식 제약 조건 `Aeq*x = beq`에 포함되는 행렬
`beq`	선형 등식 제약 조건 `Aeq*x = beq`에 포함되는 벡터
`lb`	하한으로 구성된 벡터
`ub`	상한으로 구성된 벡터
`x0`	초기점
`solver`	`'intlinprog'`(필수)
`options`	`optimoptions`를 사용하여 생성되는 옵션(필수)

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

f
intcon
solver
options

주의

problem 인수는 스칼라 구조체여야 합니다. 선형 제약 조건을 셀형 배열 {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

출력 인수

모두 축소

`x` — 해(Solution)
실수형 벡터

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

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

`fval` — 목적 함수 값
실수형 스칼라

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

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

`exitflag` — 알고리즘 중지 조건
정수

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

`3`	이 해는 상대 `ConstraintTolerance` 허용오차를 기준으로는 실현 가능하지만, 절대 허용오차를 기준으로는 실현 불가능합니다.
`2`	`intlinprog`가 중도에 중지되었습니다. 정수 실현가능점을 찾았습니다.
`1`	`intlinprog`가 해 `x`로 수렴되었습니다.
`0`	`intlinprog`가 중도에 중지되었습니다. 정수 실현가능점을 찾지 못했습니다.
`-1`	`intlinprog`가 출력 함수나 플롯 함수에 의해 중지되었습니다.
`-2`	실현가능점을 찾지 못했습니다.
`-3`	루트 LP 문제가 비유계입니다.
`-9`	솔버가 실현가능성을 잃었습니다.

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

종료 플래그 3과 -9는 실현불가능성이 큰 해와 관계가 있습니다. 이런 종료 플래그는 보통 큰 조건수를 갖는 선형 제약 조건 행렬이나 큰 해 성분이 있는 문제에서 비롯됩니다. 이런 문제를 해결하려면 계수 행렬을 스케일링하거나 중복된 선형 제약 조건을 제거하거나 변수에 대해 더 엄밀한 범위를 지정해 보십시오.

`output` — 풀이 과정 요약
구조체

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

`relativegap`	분기한정 알고리즘에서 `intlinprog`가 계산하는 목적 함수의 상한(`U`)과 하한(`L`) 사이의 상대 차이입니다. 구체적으로, 다음과 같습니다. `relativegap = (U - L) / abs(U)`. `intcon = []`이면 `relativegap = []`입니다. 참고 사용자는 `RelativeGapTolerance`를 소수로 지정하지만, 반복 과정 표시에서는 간격을 백분율, 즉 측정된 상대적인 간격에 100을 곱한 값으로 보고합니다. 종료 메시지가 상대적인 간격을 언급하는 경우 이 값은 백분율이 아니라 측정된 상대적인 간격에 해당합니다.
`absolutegap`	분기한정 알고리즘에서 `intlinprog`가 계산하는 목적 함수의 상한과 하한 사이의 차이입니다. `intcon = []`이면 `absolutegap = []`입니다.
`numfeaspoints`	발견된 정수 실현가능점의 개수입니다. `intcon = []`이면 `numfeaspoints = []`입니다. 또한, 완화된 초기 문제가 실현 가능하지 않을 경우 `numfeaspoints = []`입니다.
`numnodes`	분기한정 알고리즘의 노드 개수입니다. 전처리 또는 초기 절단 중에 해가 발견된 경우 `numnodes = 0`입니다. `intcon = []`이면 `numnodes = []`입니다.
`constrviolation`	위반된 제약 조건에 대해 양수를 나타내는 제약 조건 위반 값입니다. `constrviolation = max([0; norm(Aeqx-beq, inf); (lb-x); (x-ub); (Aix-bi)])`
`message`	종료 메시지입니다.

제한 사항

해 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는 f, b 또는 ub의 계수와 같은 문제의 성분이 절댓값 1e20을 초과할 수 없도록 하며, 선형 제약 조건 행렬 A와 Aeq가 절댓값 1e15와 같거나 이를 초과하는 것을 허용하지 않습니다. 이러한 문제에 intlinprog를 실행하려고 하면 intlinprog가 오류를 발생시킵니다.

세부 정보

모두 축소

확장된 정수 변수

확장된 정수 변수는 정수 값, 반연속 또는 반정수(semi-integer)인 변수입니다.

정수 값 변수는 -12나 1234567과 같이 표준 배정밀도 변수로 표현된 모든 정수 값을 받을 수 있습니다. 정수 변수에 대해 범위를 지정할 필요가 없습니다.
반연속 변수는 값 0을 받거나 하한에서 상한 사이의 임의의 실수 값을 받을 수 있습니다. 범위는 순양수(Strictly Positive)여야 하며 1e5를 초과하지 않아야 합니다.
반정수(semi-integer) 변수는 정수 값을 가지며, 값 0을 받거나 하한에서 상한 사이의 임의의 정수 값을 받을 수 있습니다. 범위는 순양수(Strictly Positive)여야 하며 1e5를 초과하지 않아야 합니다.

intlinprog 솔버는 모두 MATLAB^® double형을 갖는 정수 변수와 확장된 정수 변수를 지원합니다. integerConstraint 함수를 사용하여 변수 유형을 지정합니다. 다음 이름을 사용하여 정수 또는 확장된 정수인 변수 인덱스를 지정합니다.

Integer — 정수 변수 인덱스
SemiContinuous — 반연속 변수 인덱스
SemiInteger — 반정수(semi-integer) 변수 인덱스

지정되지 않은 변수 인덱스의 디폴트 유형은 연속입니다. 즉, 임의의 실수 값을 받을 수 있는 변수입니다.

예를 들어, 변수 1~5를 정수로, 변수 11~20을 반연속으로, 나머지를 연속으로 지정하려면 다음을 입력합니다.

intcon = integerConstraint(Integer=1:5,SemiContinuous=11:20);

향상된 종료 메시지

다음 몇 가지 항목은 intlinprog에서 반환될 수 있는 향상된 종료 메시지를 나열한 것입니다. 향상된 종료 메시지에는 자세한 정보를 볼 수 있는 링크가 메시지의 첫 문장으로 제공됩니다.

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

intlinprog가 최적해를 구하지 못했을 수 있습니다. 그러나 적어도 하나의 정수 실현가능점을 찾았습니다. 정수 실현가능점은 범위, 선형 제약 조건, 정수 제약 조건을 포함하여 모든 제약 조건을 충족하는 점입니다.

최대 노드 수에 도달함

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가 정수 실현가능점을 찾지 못했음을 의미합니다. 정수 실현가능점은 범위, 선형 제약 조건, 정수 제약 조건을 포함하여 모든 제약 조건을 충족하는 점입니다.

루트 LP 문제를 푸는 동안 반복 한도를 초과함

RootLPMaxIterations 반복 한도에 도달했기 때문에 intlinprog가 완화된 LP를 풀 수 없습니다. intlinprog는 RootLPMaxIterations 옵션(허용오차)을 중지 기준으로 사용합니다.

할당된 메모리를 초과함

intlinprog에 메모리가 부족합니다. 문제를 다시 구성하면 해를 구하는 것이 가능할 수도 있습니다. Williams [1]를 참조하십시오.

실현 가능한 해를 찾지 못함

문제에 대한 해가 없으므로 intlinprog가 중지되었습니다. 범위와 선형 제약 조건이 모순되거나, 정수 제약 조건이 범위 및 선형 제약 조건과 모순됩니다.

원인을 확인하려면 intcon = []을 사용하여 문제를 다시 실행하십시오. 결과 선형 계획법에 해가 없으면 범위와 선형 제약 조건이 모순됩니다. 그렇지 않으면, 원래 문제의 정수 제약 조건이 범위 및 선형 제약 조건과 모순됩니다.

루트 LP 문제가 비유계임

루트 선형 계획법(LP) 문제는 원래 혼합 정수 선형 계획법(MILP) 문제이지만, 정수 제약 조건을 갖지 않습니다. 루트 LP 문제가 비유계이므로 intlinprog가 중지되었습니다.

원래 문제는 실현 가능하지 않을 수 있습니다. 루트 LP 문제가 비유계일 때 intlinprog는 실현가능성을 확인하지 않습니다.

문제가 비유계임

선형 계획법 문제의 해가 없으므로 intlinprog가 중지되었습니다. 모든 목표값에 대해 목적 함수 값이 목표값보다 작은 실현가능점이 있습니다.

종료 메시지에 대한 정의

다음 몇 가지 항목은 intlinprog 종료 메시지에 나오는 용어에 대한 정의를 포함합니다.

허용오차

일반적으로, 허용오차는 이 값을 넘는 경우 솔버의 반복이 중지되는 임계값입니다. 허용오차에 대한 자세한 내용은 허용오차와 중지 기준 항목을 참조하십시오.

노드

분기한정 또는 분기절단 트리의 노드는 x의 값과 x의 성분 j입니다. 여기서 x(j)는 소수부를 가집니다. 분기한정 노드에는 두 개의 하위 문제가 있습니다. 제한 x(j) ≥ ceil(x(j))로 선형 계획법 문제를 계산하는 문제와, 제한 x(j) ≤ floor(x(j))로 선형 계획법 문제를 계산하는 문제입니다. 자세한 내용은 분기한정 항목을 참조하십시오.

허용오차 내에 있는 정수

intlinprog는 intcon에 지정한 변수가 정수 값의 허용오차 TolInteger 내에 있을 뿐, 정확히 정수임을 보장하지는 않습니다. Some “Integer” Solutions Are Not Integers 항목을 참조하십시오.

루트 노드

intlinprog가 루트 노드에서 중지되는 경우 아무 분기한정 탐색도 실행할 필요가 없었습니다. intlinprog가 풀이 전처리 중에 문제를 풀었거나, 분기를 생성하지 않고 후속 처리 중에 문제를 풀 수 있었습니다.

루트 노드는 원래 혼합 정수 선형 계획법(MILP)를 기반으로 하는 완화된 선형 계획법 문제입니다. 자세한 내용은 분기한정 항목을 참조하십시오.

팁

이진 변수를 지정하려면 변수를 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
```
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에 개발됨

모두 확장

R2026a: `intlinprog`의 `"legacy"` 알고리즘은 제거됨

intlinprog의 "legacy" 알고리즘은 제거되었습니다. "legacy" 알고리즘과 관련된 다음 옵션도 모두 제거되었습니다.

BranchRule
CutGeneration
CutMaxIterations
Heuristics
HeuristicsMaxNodes
IntegerPreprocess
IntegerTolerance
LPMaxIterations
LPOptimalityTolerance
LPPreprocess
NodeSelection
ObjectiveImprovementThreshold
RootLPAlgorithm
RootLPMaxIterations

또한 intlinprog 알고리즘 하나만 있으므로, Algorithm 옵션이 제거되었습니다. 마찬가지로, intlinprog output 구조체는 더 이상 algorithm 필드를 포함하지 않습니다.

phase 필드는 "legacy" 알고리즘에서만 사용되었으므로, 출력 함수 또는 플롯 함수(intlinprog Output Function and Plot Function Syntax 항목 참조)에서 사용되는 optimValues 구조체는 더 이상 이 필드를 포함하지 않습니다.

R2026a: 선형 범위 제약 조건을 사용하여 문제 풀기

intlinprog 솔버는 선형 범위 제약 조건, 즉 상한 및 하한 선형 제약 조건을 지원합니다.

$bl \leq A x \leq b .$

선형 제약 조건 벡터를 셀형 배열 {bl b}로 지정합니다. 예제는 선형 범위 제약 조건 항목을 참조하십시오.

R2025a: 확장된 정수 변수 지원

"highs" 알고리즘을 사용하는 intlinprog는 반연속 변수와 반정수(semi-integer) 변수를 지원하며, 이는 integerConstraint 함수를 사용하여 지정할 수 있습니다. 예를 들어, 변수 10~20을 반정수(semi-integer)로, 변수 1~9를 반연속으로 지정하려면 다음을 입력합니다.

intcon = integerConstraint(SemiInteger=10:20,SemiContinuous=1:9);

자세한 내용은 확장된 정수 변수 항목을 참조하십시오.

R2024b: `"highs"` 알고리즘은 출력 함수, 플롯 함수 및 `MaxFeasiblePoints` 옵션을 지원함

"highs" 알고리즘은 이제 출력 함수와 플롯 함수를 지원합니다. 자세한 내용은 intlinprog Output Function and Plot Function Syntax 항목을 참조하십시오. 내장 플롯 함수를 사용하는 예제를 보려면 Factory, Warehouse, Sales Allocation Model: Solver-Based 항목을 참조하십시오.

출력 함수 및 플롯 함수에 대한 optimValues Structure는 이제 필드 이름 dualbound를 lowerbound 대신 사용합니다. dualbound는 최소화 문제의 전역 하한이나 최대화 문제의 전역 상한을 의미합니다. optimplotmilp 플롯 함수는 이제 Branch/bound UB 및 Branch/bound LB 대신 Primal Bound 및 Dual Bound 레이블을 사용합니다.

"highs" 알고리즘은 이제 MaxFeasiblePoints 옵션을 지원합니다. "highs" 알고리즘에 대한 output 구조체는 이제 numfeaspoints 필드를 지원합니다.

R2024b: `"legacy"` 알고리즘은 제거될 예정임

intlinprog "legacy" 알고리즘은 향후 릴리스에서 제거될 예정입니다. 이때, "legacy" 알고리즘에만 유효한 모든 options와 Algorithm 옵션이 제거됩니다. 또한 output 구조체의 algorithm 필드도 제거됩니다.

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'로 설정하십시오.

참고 항목

intlinprog

구문

설명

예제

선형 부등식이 있는 MILP 풀기

모든 유형의 제약 조건이 있는 MILP 풀기

초기점 사용하기

디폴트가 아닌 옵션을 사용하여 MILP 풀기

문제 기반 접근법을 사용하여 MILP 풀기

MILP 해와 과정 검토하기

입력 인수

f — 계수 벡터 실수형 벡터 | 실수형 배열

intcon — 정수 변수 인덱스 정수 벡터 | IntegerConstraint 객체

A — 선형 부등식 제약 조건 실수 행렬

b — 선형 부등식 제약 조건 실수형 벡터 | 실수형 배열로 구성된, 요소를 2개 가진 셀형 배열

Aeq — 선형 등식 제약 조건 실수 행렬

beq — 선형 등식 제약 조건 실수형 벡터

lb — 하한 [] (디폴트 값) | 실수형 벡터 또는 배열

ub — 상한 [] (디폴트 값) | 실수형 벡터 또는 배열

x0 — 초기점 [] (디폴트 값) | 실수형 배열

options — intlinprog에 대한 옵션 optimoptions를 사용하여 생성되는 옵션

problem — 입력값과 옵션을 캡슐화하는 구조체 구조체

출력 인수

x — 해(Solution) 실수형 벡터

fval — 목적 함수 값 실수형 스칼라

exitflag — 알고리즘 중지 조건 정수

output — 풀이 과정 요약 구조체

제한 사항

세부 정보

확장된 정수 변수

향상된 종료 메시지

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

최대 노드 수에 도달함

시간 제한을 초과함

한 노드에서 반복 한도를 초과함

실현가능점의 최대 개수에 도달함

목적 함수 값이 격차 허용오차 내에 있음

정수 변수가 지정되지 않음.

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

루트 LP 문제를 푸는 동안 반복 한도를 초과함

할당된 메모리를 초과함

실현 가능한 해를 찾지 못함

루트 LP 문제가 비유계임

문제가 비유계임

종료 메시지에 대한 정의

허용오차

노드

허용오차 내에 있는 정수

루트 노드

팁

대체 기능

앱

버전 내역

R2026a: intlinprog의 "legacy" 알고리즘은 제거됨

R2026a: 선형 범위 제약 조건을 사용하여 문제 풀기

R2025a: 확장된 정수 변수 지원

R2024b: "highs" 알고리즘은 출력 함수, 플롯 함수 및 MaxFeasiblePoints 옵션을 지원함

R2024b: "legacy" 알고리즘은 제거될 예정임

R2024a: 새 "highs" 알고리즘이 디폴트 값임

R2019a: 디폴트 BranchRule은 'reliability'임

참고 항목

도움말 항목

`f` — 계수 벡터
실수형 벡터 | 실수형 배열

`intcon` — 정수 변수 인덱스
정수 벡터 | `IntegerConstraint` 객체

`A` — 선형 부등식 제약 조건
실수 행렬

`b` — 선형 부등식 제약 조건
실수형 벡터 | 실수형 배열로 구성된, 요소를 2개 가진 셀형 배열

`Aeq` — 선형 등식 제약 조건
실수 행렬

`beq` — 선형 등식 제약 조건
실수형 벡터

`lb` — 하한
`[]` (디폴트 값) | 실수형 벡터 또는 배열

`ub` — 상한
`[]` (디폴트 값) | 실수형 벡터 또는 배열

`x0` — 초기점
`[]` (디폴트 값) | 실수형 배열

`options` — `intlinprog`에 대한 옵션
`optimoptions`를 사용하여 생성되는 옵션

`problem` — 입력값과 옵션을 캡슐화하는 구조체
구조체

`x` — 해(Solution)
실수형 벡터

`fval` — 목적 함수 값
실수형 스칼라

`exitflag` — 알고리즘 중지 조건
정수

`output` — 풀이 과정 요약
구조체

R2026a: `intlinprog`의 `"legacy"` 알고리즘은 제거됨

R2024b: `"highs"` 알고리즘은 출력 함수, 플롯 함수 및 `MaxFeasiblePoints` 옵션을 지원함

R2024b: `"legacy"` 알고리즘은 제거될 예정임

R2024a: 새 `"highs"` 알고리즘이 디폴트 값임

R2019a: 디폴트 `BranchRule`은 `'reliability'`임