Main Content

本页翻译不是最新的。点击此处可查看最新英文版本。

intlinprog

混合整数线性规划 (MILP)

说明

混合整数线性规划求解器。

求以下问题的最小值:

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

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 结构体。您还可以使用 prob2structOptimizationProblem 对象创建 problem 结构体。

示例

[x,fval,exitflag,output] = intlinprog(___) 可以与上述任何输入参数结合使用,返回 fval = f'*x、描述退出条件的值 exitflag 以及包含优化过程信息的结构体 output

示例

全部折叠

求解问题

minx8x1+x2subjectto{x2isanintegerx1+2x2-14-4x1-x2-332x1+x220.

编写目标函数向量和由整数变量组成的向量。

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.
x = 2×1

    6.5000
    7.0000

求解问题

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x20x1+x2+x374x1+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)
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.
x = 3×1

         0
    5.5000
    1.0000

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

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

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.61         0              -              -                                          
   14739      0.83         1   2.154000e+03   2.593968e+01                                          
   18258      1.06         2   1.854000e+03   1.180593e+01                                          
   18673      1.08         2   1.854000e+03   1.563342e+00                                          
   18829      1.09         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.43         2   2.154000e+03   2.593968e+01                                          
    5844      0.58         3   1.854000e+03   1.180593e+01                                          
    6204      0.60         3   1.854000e+03   1.455526e+00                                          
    6400      0.62         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 采用更多步骤。

求解问题

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x20x1+x2+x374x1+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
    5.5000
    1.0000

此示例说明如何使用基于问题的方法设立问题,然后使用基于求解器的方法求解问题。问题是

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x20x1+x2+x374x1+2x2+x3=12

创建名为 probOptimizationProblem 对象来表示此问题。要指定二元变量,请创建一个下界为 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.
sol = 3×1

         0
    5.5000
    1.0000

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

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

带更多输出调用 intlinprog 以查看解的详细信息和过程。

目标是求解问题

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x20x1+x2+x374x1+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)
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.
x = 3×1

         0
    5.5000
    1.0000

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

输出结构体显示 numnodes0。这意味着 intlinprog 在分支之前已求出问题的解。这是结果可靠的一个标志。此外,absolutegaprelativegap 字段是 0。这是结果可靠的另一个标志。

输入参数

全部折叠

系数向量,指定为实数向量或实数数组。系数向量表示目标函数 f'*x。该表示法假设 f 是列向量,但您也可以使用行向量或数组。linprog 在内部将 f 转换为列向量 f(:)

如果您指定 f = []intlinprog 会尝试在不试图最小化目标函数的情况下找到可行点。

示例: f = [4;2;-1.7];

数据类型: double

整数约束组成的向量,指定为正整数向量。intcon 中的值指示决策变量 x 中应取整数值的分量。intcon 的值在 1numel(f) 范围内。

intcon 也可以是数组。intlinprog 在内部将数组 intcon 转换为向量 intcon(:)

示例: intcon = [1,2,7] 表示 x(1)x(2)x(7) 仅取整数值。

数据类型: double

线性不等式约束,指定为实矩阵。AM×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];

示例: 要指定 x 的各个分量加起来等于或小于 1,请指定 A = ones(1,N)b = 1

数据类型: double

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

数据类型: double

线性等式约束,指定为实矩阵。AeqMe×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];

示例: 要指定 x 分量之和为 1,请指定 Aeq = ones(1,N)beq = 1

数据类型: double

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

数据类型: double

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

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

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

数据类型: double

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

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

示例: ub = [Inf;4;10] 表示 x(2) ≤ 4x(3) ≤ 10

数据类型: double

初始点,指定为实数数组。当 f 存在时,x0 中的元素数与 f 中的元素数相同。否则,该数字与 AAeq 的列数相同。求解器在内部将数组 x0 转换为向量 x0(:)

提供 x0 会改变 intlinprog 收敛所需的时间量。很难预测 x0 如何影响求解器。有关适合在有 x0 时使用的 Heuristics 的建议,请参阅提示

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

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

数据类型: double

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

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

选项描述默认值
AbsoluteGapTolerance

非负实数。如果内部计算的目标函数的上界 (U) 和下界 (L) 之间的差小于或等于 AbsoluteGapTolerance,则 intlinprog 停止:

U – L <= AbsoluteGapTolerance.

0
BranchRule

选择分支分量的规则:

  • 'maxpscost' - 具有最大伪代价的小数分量。请参阅分支定界

  • 'strongpscost' - 具有最大伪代价且伪代价估计值比在 'maxpscost' 中更准确的小数分量。请参阅分支定界

  • 'reliability' - 具有最大伪代价且伪代价估计值比在 'strongpscost' 中还要准确的小数分量。请参阅分支定界

  • 'mostfractional' - 小数部分最接近 1/2 的分量。

  • 'maxfun' - 目标向量 f 中绝对值最大的分量所对应的小数分量。

'reliability'
ConstraintTolerance1e-91e-3 范围内的实数,这是线性约束仍被视为满足时可具有的最大差异。ConstraintTolerance 不是停止条件。1e-4
CutGeneration

切割生成的级别(请参阅切割生成):

  • 'none' - 无切割。使 CutMaxIterations 不相关。

  • 'basic' - 正常切割生成。

  • 'intermediate' - 使用更多切割类型。

  • 'advanced' - 使用大多数切割类型。

'basic'
CutMaxIterations在进入分支定界阶段之前经历所有切割生成方法的次数,从 150 的整数。通过将 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'
IntegerTolerance1e-61e-3 范围内的实数,这是解 x 的分量仍被视为整数时相比整数可具有的最大偏差。IntegerTolerance 不是停止条件。1e-5
LPMaxIterations严格正整数,在分支定界过程中每个节点的单纯形算法迭代的最大次数。

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

在此表达式中,numberOfEqualities 表示 Aeq 的行数,numberOfInequalities 表示 A 的行数,numberOfVariables 表示 f 的元素数。

LPOptimalityTolerance非负实数,要将一个变量纳入基,该变量的简化后的代价必须超过 LPOptimalityTolerance1e-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|) > ObjectiveImprovementThreshold0
OutputFcn

优化函数在事件中调用的一个或多个函数。指定为 'savemilpsolutions'、函数句柄或函数句柄元胞数组。对于自定义输出函数,传递函数句柄。输出函数可以停止求解器。

  • 'savemilpsolutions' 收集工作区中 xIntSol 矩阵中的整数可行点,其中每列均为一个整数可行点。

有关编写自定义输出函数的信息,请参阅intlinprog Output Function and Plot Function Syntax

[]
PlotFcn

对算法执行过程中的各种进度测量值绘图,可以选择预定义的绘图,也可以自行编写绘图函数。传递 'optimplotmilp'、函数句柄或函数句柄组成的元胞数组。对于自定义绘图函数,传递函数句柄。默认值是“无”([]):

  • 'optimplotmilp' 绘制内部计算的与解对应的目标函数值上界和下界。

有关编写自定义绘图函数的信息,请参阅intlinprog Output Function and Plot Function Syntax

[]
RelativeGapTolerance

01 范围内的实数。如果内部计算的目标函数上界 (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)

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

f表示目标 f'*x 的向量(必需)
intcon表示取整数值的变量的向量(必需)
Aineq线性不等式约束 Aineq*x bineq 中的矩阵

bineq

线性不等式约束 Aineq*x bineq 中的向量

Aeq

线性等式约束 Aeq*x = beq 中的矩阵

beq

线性等式约束 Aeq*x = beq 中的向量
lb由下界组成的向量
ub由上界组成的向量
x0初始可行点
solver'intlinprog'(必需)

options

使用 optimoptions 创建的选项(必需)

您必须在问题结构体中至少指定以下字段。其他字段是可选的:

  • f

  • intcon

  • solver

  • options

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

数据类型: struct

输出参数

全部折叠

解,以向量形式返回,它在所有边界、整数约束和线性约束的限制下最小化 f'*x

当问题不可行或无界时,x[]

目标函数值,以解 x 处的标量值 f'*x 形式返回。

当问题不可行或无界时,fval[]

算法停止条件,以整数形式返回,标识算法停止的原因。下面列出 exitflag 的值以及相应的 intlinprog 停止原因。

3

解关于相对 ConstraintTolerance 容差可行,但关于绝对容差不可行。

2

intlinprog 提前停止。找到整数可行点。

1

intlinprog 收敛于解 x

0

intlinprog 提前停止。找不到整数可行点。

-1

intlinprog 由输出函数或绘图函数停止。

-2

找不到可行点。

-3

根 LP 问题无界。

-9

求解器失去可行性。

退出消息可以提供关于 intlinprog 停止原因的更详细信息,例如超出容差。

退出标志 3-9 与不可行性较大的解相关。此类问题通常源于具有较大条件数的线性约束矩阵,或源于具有较大解分量的问题。要纠正这些问题,请尝试缩放系数矩阵,消除冗余线性约束,或对变量给出更严格的边界。

求解过程摘要,以包含优化过程信息的结构体形式返回。

relativegap

intlinprog 在分支定界算法中计算的目标函数上界 (U) 和下界 (L) 之间的相对百分比差。

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

如果 intcon = [],则 relativegap = []

注意

虽然您将 RelativeGapTolerance 指定为十进制数字,但迭代输出和 output.relativegap 以百分比形报告该间隙,即测量的相对间隙的 100 倍。如果退出消息涉及相对间隙,则该值是测量的相对间隙,而不是百分比。

absolutegap

intlinprog 在分支定界算法中计算的目标函数上界和下界之间的差。

如果 intcon = [],则 absolutegap = []

numfeaspoints

找到的整数可行点的数量。

如果 intcon = [],则 numfeaspoints = []。此外,如果初始松弛问题不可行,则 numfeaspoints = []

numnodes

分支定界算法中的节点数。如果在预处理或初始切割过程中找到了解,则 numnodes = 0

如果 intcon = [],则 numnodes = []

constrviolation

约束违反值,在违反约束时为正值。

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

message

退出消息。

局限性

  • 通常,解 x(intCon) 中一些应为整数值的分量并不是精确的整数。intlinprog 将处在整数容差 IntegerTolerance 内的所有解值视为整数。

    要将所有应为整数的解值舍入为精确的整数,请使用 round 函数。

    x(intcon) = round(x(intcon));

    小心

    舍入解可能导致解变得不可行。舍入后检查可行性:

    max(A*x - b) % See if entries are not too positive, so have small infeasibility
    max(abs(Aeq*x - beq)) % See if entries are near enough to zero
    max(x - ub) % Positive entries are violated bounds
    max(lb - x) % Positive entries are violated bounds
  • intlinprog 不强制将绝对值超过 2.1e9 的解分量转化为整数值。当您的解包含此种分量时,intlinprog 会发出警告。如果您收到此警告,请检查该解,确认该解中应为整数值的分量是否接近整数。

  • intlinprog 不允许问题的分量(如 fAub 中的系数)的绝对值超过 1e25。如果您尝试对这样的问题运行 intlinprogintlinprog 会出错。

提示

  • 要指定二元变量,请在 intcon 中将变量设置为整数,并指定其下界为 0,上界为 1

  • 通过指定稀疏线性约束矩阵 AAeq 来节省内存。但是,您无法对 bbeq 使用稀疏矩阵。

  • 如果包含 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)

    • 更新任何相关选项。使用 optimoptionsintlinprog 创建选项。

    • 按以下方式更改您对 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 中推出

全部展开