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)

LP:                Optimal objective value is 59.000000.                                            


Optimal solution found.

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

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

LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

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

使用初始点

打开实时脚本

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

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

Aeq = [22    13    26    33    21     3    14    26
    39    16    22    28    26    30    23    24
    18    14    29    27    30    38    26    26
    41    26    28    36    18    38    16    26];
beq = [ 7872
       10466
       11322
       12058];

设置下界以将所有变量限制为非负值。

N = 8;
lb = zeros(N,1);

指定所有变量均为整数值。

intcon = 1:N;

设置目标函数向量 f。

f = [2    10    13    17     7     5     7     3];

在不使用初始点的情况下求解问题，并检查显示以查看分支定界节点的数量。

[x1,fval1,exitflag1,output1] = intlinprog(f,intcon,[],[],Aeq,beq,lb);

LP:                Optimal objective value is 1554.047531.                                          

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

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
   10000      0.92         0              -              -                                          
   14739      1.27         1   2.154000e+03   2.593968e+01                                          
   18258      1.59         2   1.854000e+03   1.180593e+01                                          
   18673      1.62         2   1.854000e+03   1.563342e+00                                          
   18829      1.64         2   1.854000e+03   0.000000e+00                                          

Optimal solution found.

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

为了进行比较，使用初始可行点求得解。

x0 = [8 62 23 103 53 84 46 34];
[x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);

LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1591.000000.                                                      
                   Relative gap is 59.20%.                                                         

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
    3627      0.45         2   2.154000e+03   2.593968e+01                                          
    5844      0.64         3   1.854000e+03   1.180593e+01                                          
    6204      0.68         3   1.854000e+03   1.455526e+00                                          
    6400      0.69         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

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

在没有初始点的情况下，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)

LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

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

fval = -12

exitflag = 1

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            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)

LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

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

fval = -12

exitflag = 1

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            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 的建议，请参阅提示。

x0 必须关于所有约束都可行。如果 x0 不可行，求解器会出错。如果您没有可行的 x0，请设置 x0 = []。

示例： x0 = 100*rand(size(f))

数据类型： double

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

intlinprog 的选项，指定为 optimoptions 的输出。

optimoptions 显示中缺少某些选项。这些选项在下表中以斜体显示。有关详细信息，请参阅查看优化选项。

选项	说明	默认值
`AbsoluteGapTolerance`	非负实数。如果内部计算的目标函数的上界 (`U`) 和下界 (`L`) 之间的差小于或等于 `AbsoluteGapTolerance`，则 `intlinprog` 停止： `U – L <= AbsoluteGapTolerance`.	`0`
`BranchRule`	选择分支分量的规则： `'maxpscost'` - 具有最大伪代价的小数分量。请参阅分支定界。 `'strongpscost'` - 具有最大伪代价且伪代价估计值比在 `'maxpscost'` 中更准确的小数分量。请参阅分支定界。 `'reliability'` - 具有最大伪代价且伪代价估计值比在 `'strongpscost'` 中还要准确的小数分量。请参阅分支定界。 `'mostfractional'` - 小数部分最接近 `1/2` 的分量。 `'maxfun'` - 目标向量 `f` 中绝对值最大的分量所对应的小数分量。	`'reliability'`
`ConstraintTolerance`	`1e-9` 到 `1e-3` 范围内的实数，这是线性约束仍被视为满足时可具有的最大差异。`ConstraintTolerance` 不是停止条件。	`1e-4`
`CutGeneration`	切割生成的级别（请参阅切割生成）： `'none'` - 无切割。使 `CutMaxIterations` 不相关。 `'basic'` - 正常切割生成。 `'intermediate'` - 使用更多切割类型。 `'advanced'` - 使用大多数切割类型。	`'basic'`
`CutMaxIterations`	在进入分支定界阶段之前经历所有切割生成方法的次数，从 `1` 到 `50` 的整数。通过将 `CutGeneration` 选项设置为 `'none'` 可禁用切割生成。	`10`
`Display`	显示级别（请参阅迭代输出）： `'off'` 或 `'none'` - 不显示迭代输出 `'final'` - 仅显示最终值 `'iter'` - 显示迭代输出	`'iter'`
`Heuristics`	搜索可行点的算法（请参阅使用启发式方法求出可行解）： `'basic'` `'intermediate'` `'advanced'` `'rss'` `'rins'` `'round'` `'diving'` `'rss-diving'` `'rins-diving'` `'round-diving'` `'none'`	`'basic'`
`HeuristicsMaxNodes`	严格正整数，它限制 `intlinprog` 在分支定界搜索可行点的过程中可探查的节点数。仅适用于 `'rss'` 和 `'rins'`。请参阅使用启发式方法求出可行解。	`50`
`IntegerPreprocess`	整数预处理的类型（请参阅混合整数规划预处理）： `'none'` - 使用非常少的整数预处理步骤。 `'basic'` - 使用中等数量的整数预处理步骤。 `'advanced'` - 使用所有可用的整数预处理步骤。	`'basic'`
`IntegerTolerance`	`1e-6` 到 `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'`
`MaxNodes`	严格正整数，它是 `intlinprog` 在分支定界过程中探查的最大节点数。	`1e7`
`MaxFeasiblePoints`	严格正整数。`intlinprog` 在找到 `MaxFeasiblePoints` 个整数可行点时停止。	`Inf`
`MaxTime`	正实数，它是 `intlinprog` 运行的最长时间（以秒为单位）。	`7200`
`NodeSelection`	选择下一步要探查的节点。 `'simplebestproj'` - 最佳投影。请参阅分支定界。 `'minobj'` - 探查目标函数值最小的节点。 `'mininfeas'` - 探查整数不可行性之和最小的节点。请参阅分支定界。	`'simplebestproj'`
`ObjectiveCutOff`	大于 `-Inf` 的实数。在分支定界计算过程中，`intlinprog` 丢弃那些线性规划解所对应目标函数值超过 `ObjectiveCutOff` 的节点。	`Inf`
`ObjectiveImprovementThreshold`	非负实数。`intlinprog` 仅在找到目标函数值比当前可行解的目标函数值低至少 `ObjectiveImprovementThreshold` 的另一个解时，才会更改当前可行解：(fold – fnew)/(1 + \|fold\|) > ObjectiveImprovementThreshold。	`0`
`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\| + 1) <= RelativeGapTolerance`. 注意虽然您将 `RelativeGapTolerance` 指定为十进制数字，但迭代输出和 `output.relativegap` 以百分比形报告该间隙，即测量的相对间隙的 100 倍。如果退出消息涉及相对间隙，则该值是测量的相对间隙，而不是百分比。	`1e-4`
`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`) 之间的相对百分比差。 `relativegap = 100*(U - L) / (abs(U) + 1)` 如果 `intcon = []`，则 `relativegap = []`。注意虽然您将 `RelativeGapTolerance` 指定为十进制数字，但迭代输出和 `output.relativegap` 以百分比形报告该间隙，即测量的相对间隙的 100 倍。如果退出消息涉及相对间隙，则该值是测量的相对间隙，而不是百分比。
`absolutegap`	`intlinprog` 在分支定界算法中计算的目标函数上界和下界之间的差。如果 `intcon = []`，则 `absolutegap = []`。
`numfeaspoints`	找到的整数可行点的数量。如果 `intcon = []`，则 `numfeaspoints = []`。此外，如果初始松弛问题不可行，则 `numfeaspoints = []`。
`numnodes`	分支定界算法中的节点数。如果在预处理或初始切割过程中找到了解，则 `numnodes = 0`。如果 `intcon = []`，则 `numnodes = []`。
`constrviolation`	约束违反值，在违反约束时为正值。 `constrviolation = max([0; norm(Aeqx-beq, inf); (lb-x); (x-ub); (Aix-bi)])`
`message`	退出消息。

局限性

通常，解 x(intCon) 中一些应为整数值的分量并不是精确的整数。intlinprog 将处在整数容差 IntegerTolerance 内的所有解值视为整数。
要将所有应为整数的解值舍入为精确的整数，请使用 round 函数。
```
x(intcon) = round(x(intcon));
```
小心
舍入解可能导致解变得不可行。舍入后检查可行性：
max(A*x - b) % See if entries are not too positive, so have small infeasibility max(abs(Aeq*x - beq)) % See if entries are near enough to zero max(x - ub) % Positive entries are violated bounds max(lb - x) % Positive entries are violated bounds
intlinprog 不强制将绝对值超过 2.1e9 的解分量转化为整数值。当您的解包含此种分量时，intlinprog 会发出警告。如果您收到此警告，请检查该解，确认该解中应为整数值的分量是否接近整数。
intlinprog 不允许问题的分量（如 f、A 或 ub 中的系数）的绝对值超过 1e25。如果您尝试对这样的问题运行 intlinprog，intlinprog 会出错。

提示

要指定二元变量，请在 intcon 中将变量设置为整数，并指定其下界为 0，上界为 1。
通过指定稀疏线性约束矩阵 A 和 Aeq 来节省内存。但是，您无法对 b 和 beq 使用稀疏矩阵。
如果包含 x0 参数，intlinprog 将在 'rins' 中和引导潜水启发式方法中使用该值，直到找到更好的整数可行点。因此，当您提供 x0 时，您可以通过将 'Heuristics' 选项设置为 'rins-diving' 或使用 'rins' 的其他设置来获得满意的结果。
如果提供的是整数分量的逻辑索引，即用 1 指示整数的二元向量，请使用 find 将其转换为 intcon 形式。例如，
```
logicalindices = [1,0,0,1,1,0,0];
intcon = find(logicalindices)
```
```
intcon =

     1     4     5
```
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 中推出

全部展开

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

版本历史记录

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

另请参阅

主题

WeChat

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

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

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

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

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

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

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

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

`x0` — 初始点
`[]` （默认） | 实数数组

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

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

`x` — 解
实数向量

`fval` — 目标值
实数标量

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

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

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