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 \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b . \end{array}$

f、x、intcon、b、beq、lb 和 ub 是向量，A 和 Aeq 是矩阵。

您可以将 f、intcon、lb 和 ub 指定为向量或数组。请参阅矩阵参量。

注意

intlinprog 仅适用于基于求解器的方法。有关这两种优化方法的讨论，请参阅首先选择基于问题或基于求解器的方法。

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) 定义设计变量 x 的一组下界和上界，使解始终在 lb ≤ x ≤ ub 范围内。如果不存在等式，请设置 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.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.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.

求解具有所有类型的约束的 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.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.

使用初始点

打开实时脚本

比较在具有和没有初始可行点的情况下求解整数规划问题的步数。此问题有八个变量、四个线性等式约束，所有变量都约束为正值。

定义线性等式约束矩阵和向量。

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

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.85 (total)
                    0.01 (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.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.97 (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 执行了大约 30000 个分支定界步。
使用初始点时，intlinprog 执行了大约 5000 步。

给出初始点并非始终有帮助。对于此问题，给出初始点可以节省时间和计算步骤。但是，对于某些问题，给定初始点可能会导致 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.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.

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。请参阅算法。

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

fval = -12

exitflag = 1

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: []
           numnodes: 0
    constrviolation: 0
          algorithm: 'highs'
            message: 'Optimal solution found....'

输出结构体显示 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 个元素的列向量。

例如，假设有以下不等式：

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

通过输入以下约束来指定不等式。

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

示例: 要指定 x 的各个分量加起来等于或小于 1，请指定 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 的矩阵。

例如，假设有以下不等式：

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 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 个元素的列向量。

例如，请参考以下等式：

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。

数据类型: double

`beq` — 线性等式约束
实数向量

线性等式约束，指定为实数向量。beq 是与 Aeq 矩阵相关的包含 Me 个元素的向量。如果将 beq 作为行向量传递，求解器会在内部将 beq 转换为列向量 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。

数据类型: double

`lb` — 下界
`[]` (默认) | 实数向量或数组

下界，指定为双精度值组成的向量或数组。lb 按元素表示下界，形如 lb ≤ x ≤ ub。

intlinprog 在内部将数组 lb 转换为向量 lb(:)。

示例: lb = [0;-Inf;4] 表示 x(1) ≥ 0，x(3) ≥ 4。

数据类型: double

`ub` — 上界
`[]` (默认) | 实数向量或数组

上界，指定为双精度值组成的向量或数组。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`	非负实数。如果内部计算的目标函数的上界 (`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"`
`MaxNodes`	严格正整数，它是 `intlinprog` 在分支定界过程中探查的最大节点数。	`1e7`
`MaxTime`	非负实数，它是 `intlinprog` 运行的最长时间（以秒为单位）。	`7200`
`ObjectiveCutOff`	大于 `-Inf` 的实数。在分支定界计算过程中，`intlinprog` 丢弃那些线性规划解所对应目标函数值超过 `ObjectiveCutOff` 的节点。	`Inf`
`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'` - 具有最大伪代价的小数分量。请参阅分支定界。 `'strongpscost'` - 具有最大伪代价且伪代价估计值比在 `'maxpscost'` 中更准确的小数分量。请参阅分支定界。 `'reliability'` - 具有最大伪代价且伪代价估计值比在 `'strongpscost'` 中还要准确的小数分量。请参阅分支定界。 `'mostfractional'` - 小数部分最接近 `1/2` 的分量。 `'maxfun'` - 目标向量 `f` 中绝对值最大的分量所对应的小数分量。	`'reliability'`
`CutGeneration`	切割生成的级别（请参阅切割生成）： `'none'` - 无切割。使 `CutMaxIterations` 不相关。 `'basic'` - 正常切割生成。 `'intermediate'` - 使用更多切割类型。 `'advanced'` - 使用大多数切割类型。	`'basic'`
`CutMaxIterations`	在进入分支定界阶段之前经历所有切割生成方法的次数，从 `1` 到 `50` 的整数。通过将 `CutGeneration` 选项设置为 `'none'` 可禁用切割生成。	`10`
`Heuristics`	搜索可行点的算法（请参阅使用启发式方法求出可行解）： `'basic'` `'intermediate'` `'advanced'` `'rss'` `'rins'` `'round'` `'diving'` `'rss-diving'` `'rins-diving'` `'round-diving'` `'none'`	`'basic'`
`HeuristicsMaxNodes`	严格正整数，它限制 `intlinprog` 在分支定界搜索可行点的过程中可探查的节点数。仅适用于 `'rss'` 和 `'rins'`。请参阅使用启发式方法求出可行解。	`50`
`IntegerPreprocess`	整数预处理的类型（请参阅混合整数规划预处理）： `'none'` - 使用非常少的整数预处理步骤。 `'basic'` - 使用中等数量的整数预处理步骤。 `'advanced'` - 使用所有可用的整数预处理步骤。	`'basic'`
`IntegerTolerance`	`1e-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'`
`MaxFeasiblePoints`	严格正整数。`intlinprog` 在找到 `MaxFeasiblePoints` 个整数可行点时停止。	`Inf`
`NodeSelection`	选择下一步要探查的节点。 `'simplebestproj'` - 最佳投影。请参阅分支定界。 `'minobj'` - 探查目标函数值最小的节点。 `'mininfeas'` - 探查整数不可行性之和最小的节点。请参阅分支定界。	`'simplebestproj'`
`ObjectiveImprovementThreshold`	非负实数。`intlinprog` 仅在找到目标函数值比当前可行解的目标函数值低至少 `ObjectiveImprovementThreshold` 的另一个解时，才会更改当前可行解：(fold – fnew)/(1 + \|fold\|) > ObjectiveImprovementThreshold。	`0`
`OutputFcn`	优化函数在事件中调用的一个或多个函数。指定为 `'savemilpsolutions'`、函数句柄或函数句柄元胞数组。对于自定义输出函数，传递函数句柄。输出函数可以停止求解器。 `'savemilpsolutions'` 收集工作区中 `xIntSol` 矩阵中的整数可行点，其中每列均为一个整数可行点。有关编写自定义输出函数的信息，请参阅intlinprog 输出函数和绘图函数语法。	`[]`
`PlotFcn`	对算法执行过程中的各种进度测量值绘图，可以选择预定义的绘图，也可以自行编写绘图函数。传递 `'optimplotmilp'`、函数句柄或函数句柄组成的元胞数组。对于自定义绘图函数，传递函数句柄。默认值是“无”(`[]`)： `'optimplotmilp'` 绘制内部计算的与解对应的目标函数值上界和下界。有关编写自定义绘图函数的信息，请参阅intlinprog 输出函数和绘图函数语法。	`[]`
`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)

`problem` — 封装输入和选项的结构体
结构体

封装输入和选项的结构体，用下列字段指定。

`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

输出参量

全部折叠

`x` — 解
实数向量

解，以向量形式返回，它在所有边界、整数约束和线性约束的限制下最小化 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`) 之间的相对百分比差异，对于 `"legacy"` 算法是百分比差异，对于 `"highs"` 算法是相对差异。具体而言，对于 `"legacy"` 算法，`relativegap = 100*(U - L) / (abs(U) + 1)` 对于 `"highs"` 算法，`relativegap = (U - L) / abs(U)` 如果 `intcon = []`，则 `relativegap = []`。注意虽然您将 `RelativeGapTolerance` 指定为十进制数字，但迭代输出以百分比形报告该间隙，即测量的相对间隙的 100 倍。如果退出消息涉及相对间隙，则该值是测量的相对间隙，而不是百分比。
`absolutegap`	`intlinprog` 在分支定界算法中计算的目标函数上界和下界之间的差。如果 `intcon = []`，则 `absolutegap = []`。
`numfeaspoints`	找到的整数可行点的数量。对于 `"highs"` 算法，`numfeaspoints = []`。如果 `intcon = []`，则 `numfeaspoints = []`。此外，如果初始松弛问题不可行，则 `numfeaspoints = []`。
`numnodes`	`"legacy"` 算法的分支定界算法中的节点数；对于 `"highs"` 算法，`numnodes = []`。如果在预处理或初始切割过程中找到了解，则 `numnodes = 0`。如果 `intcon = []`，则 `numnodes = []`。
`constrviolation`	约束违反值，在违反约束时为正值。 `constrviolation = max([0; norm(Aeqx-beq, inf); (lb-x); (x-ub); (Aix-bi)])`
`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。要更新使用 bintprog 的旧代码以使用 intlinprog，请进行以下更改：
- 将 intcon 设置为 1:numVars，其中 numVars 是问题中变量的数目。
- 将 lb 设置为 zeros(numVars,1)。
- 将 ub 设置为 ones(numVars,1)。
- 更新任何相关选项。使用 optimoptions 为 intlinprog 创建选项。
- 按以下方式更改您对 bintprog 的调用：
  [x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options) % Change your call to: [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,x0,options)

替代功能

App

优化实时编辑器任务为 intlinprog 提供可视化界面。

版本历史记录

在 R2014a 中推出

全部展开

R2024a: 新的 `"highs"` 算法成为默认值

intlinprog 增加了一种算法、一个Algorithm 选项和一种新的默认算法。"highs" 算法基于开源 HiGHS 代码。"highs" 算法目前不支持输出函数或绘图函数。

要使用先前的算法，请使用 optimoptions 设置 Algorithm="legacy"。

现在这两种算法 ConstraintTolerance 选项值的允许范围都是 1e-10 到 1e-3，"legacy" 算法 IntegerTolerance 选项值的允许范围也是这个范围。

R2019a: `BranchRule` 的默认值是 `'reliability'`。

BranchRule 选项的默认值为 'reliability'，而不再是 'maxpscost'。在测试中，此值在许多问题中表现出更好的性能，无论是在求解时间方面还是在探查的分支节点数量方面。

对于一部分问题，以前的默认分支规则性能更好。要获得以前版本的行为，请将 BranchRule 选项设置为 'maxpscost'。

另请参阅

linprog | mpsread | optimoptions | prob2struct | 优化

intlinprog

语法

说明

示例

求解具有线性不等式的 MILP

求解具有所有类型的约束的 MILP

使用初始点

使用非默认选项求解 MILP

用基于问题的方法求解 MILP

检查 MILP 解和过程

输入参数

f — 系数向量 实数向量 | 实数数组

intcon — 整数约束组成的向量 整数向量

A — 线性不等式约束 实矩阵

b — 线性不等式约束 实数向量

Aeq — 线性等式约束 实矩阵

beq — 线性等式约束 实数向量

lb — 下界 [] (默认) | 实数向量或数组

ub — 上界 [] (默认) | 实数向量或数组

x0 — 初始点 [] (默认) | 实数数组

options — intlinprog 的选项 使用 optimoptions 创建的选项

problem — 封装输入和选项的结构体 结构体

输出参量

x — 解 实数向量

fval — 目标值 实数标量

exitflag — 算法停止条件 整数

output — 求解过程摘要 结构体

局限性

提示

替代功能

App

版本历史记录

R2024a: 新的 "highs" 算法成为默认值

R2019a: BranchRule 的默认值是 'reliability'。

另请参阅

主题

WeChat

`f` — 系数向量
实数向量 | 实数数组

`intcon` — 整数约束组成的向量
整数向量

`A` — 线性不等式约束
实矩阵

`b` — 线性不等式约束
实数向量

`Aeq` — 线性等式约束
实矩阵

`beq` — 线性等式约束
实数向量

`lb` — 下界
`[]` (默认) | 实数向量或数组

`ub` — 上界
`[]` (默认) | 实数向量或数组

`x0` — 初始点
`[]` (默认) | 实数数组

`options` — `intlinprog` 的选项
使用 `optimoptions` 创建的选项

`problem` — 封装输入和选项的结构体
结构体

`x` — 解
实数向量

`fval` — 目标值
实数标量

`exitflag` — 算法停止条件
整数

`output` — 求解过程摘要
结构体

R2024a: 新的 `"highs"` 算法成为默认值

R2019a: `BranchRule` 的默认值是 `'reliability'`。