# intlinprog
混合整数线性规划 (MILP)
函数库: TyOptimization
# 语法
x,fval,exitflag,output,lambda = intlinprog(f,intcon,A,b)
_ = intlinprog(f,intcon,A,b,Aeq,beq)
_ = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
_ = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)
_ = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,options)
_ = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)
_ = intlinprog(problem)
# 说明
混合整数线性规划求解器。
求以下问题的最小值：
f、x、intcon、b、beq、lb 和 ub 是向量，A 和 Aeq 是矩阵。
提示
intlinprog 仅适用于基于求解器的方法。有关这两种优化方法的讨论，请参见首先选择基于问题或基于求解器的方法。
x,fval,exitflag,output,lambda = intlinprog(f,intcon,A,b) 最小化 f'*x，使得 intcon 中的 x 分量是整数或扩展整数变量，且 A*x ≤ b，其中 fval = f'*x。示例
_ = intlinprog(f,intcon,A,b,Aeq,beq) 求解上述问题，同时还满足等式约束 Aeq*x = beq。如果不存在不等式，请设置 A = [] 和 b = []。
_ = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub) 定义设计变量 x 的一组下界和上界，使解始终在 lb ≤ x ≤ ub 范围内。如果不存在等式，请设置 Aeq = [] 和 beq = []。示例
_ = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0) 使用初始可行点 x0 进行优化。如果不存在边界，请设置 lb = [] 和 ub = []。
_ = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,options) 使用 options 中指定的优化选项执行最小化。如果不存在边界，请设置 lb = [] 和 ub = []。示例
_ = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options) 使用 options 中指定的优化选项执行最小化。使用 optimoptions 可设置这些选项。如果不存在初始点，请设置 x0 = []。
_ = intlinprog(problem) 使用 problem 结构体封装所有求解器输入。您可以使用 mpsread 从 MPS 文件中导入 problem 结构体。您还可以使用 prob2struct 将优化问题转换为 problem 结构体。示例
# 示例
求解具有线性不等式的 MILP
求解问题
编写目标函数向量和由整数变量组成的向量。
using TyOptimization
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.01 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 3 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
x = 2-element Vector{Float64}:
6.5
7.000000000000002
求解具有所有类型的约束的 MILP
求解问题
编写目标函数向量和由整数变量组成的向量。
using TyOptimization
f = [-3,-2,-1]
intcon = [3]
编写线性不等式约束。
A = [1 1 1]
b = [7]
编写线性等式约束。
Aeq = [4 2 1]
beq = [12]
编写边界约束。
lb = zeros(3)
ub = [Inf,Inf,1] # 保证 x[3] 为二元变量
调用 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)
x = 3-element Vector{Float64}:
0.0
6.0
0.0
使用非默认选项求解 MILP
求解问题
而不显示迭代输出。
指定求解器输入。
using TyOptimization
f = [-3,-2,-1]
intcon = [3]
A = [1 1 1]
b = [7]
Aeq = [4 2 1]
beq = [12]
lb = zeros(3)
ub = [Inf,Inf,1]
指定无显示。
options = optimoptions(:intlinprog,Display = "off")
调用 intlinprog。
x, = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,options)
x = 3-element Vector{Float64}:
0.0
6.0
0.0
用基于问题的方法求解 MILP
此示例说明如何使用基于问题的方法设立问题，然后使用基于求解器的方法求解问题。问题是
创建名为 prob 的 OptimizationProblem 对象来表示此问题。要指定二元变量，请创建一个下界为 0、上界为 1 的整数类型优化变量。
using TyOptimization
x = optimvar("x", 2; Lowerbnd=0)
xb = optimvar("xb"; Lowerbnd=0, Upperbnd=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, 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)
sol =
3-element Vector{Float64}:
0.0
6.0
0.0
fval = -12.0
exitflag = 1
output = (iterations = 0, algorithm = "highs", message = "Optimal found.")
# 输入参数
f — 系数向量实数向量
系数向量，指定为实数向量或实数数组。系数向量表示目标函数 f'*x，该表示法表明 f 是列向量。
示例： f = [4,2,-1.7]
intcon — 整数约束组成的向量整数向量 | IntegerConstraint 对象
整数变量索引，指定为正整数的向量或使用 integerConstraint 函数创建的 IntegerConstraint 对象。"legacy" 算法不支持扩展整数变量。intcon 中的值表示决策变量 x 的分量，这些分量为整数值或扩展整数值。intcon 的值在 1 到 length(f) 范围内。
示例： intcon = [1,2,7] 表示 x[1]、x[2] 和 x[7] 仅取整数值。
示例： intcon = integerConstraint(SemiContinuous=[1,2],Integer=[3]) 指定 x[1] 和 x[2] 为半连续型，而 x[3] 为整数型。
A — 线性不等式约束实矩阵
线性不等式约束，指定为实矩阵。A 是 M×N 矩阵，其中 M 是不等式的数目，而 N 是变量的数目（x0 中的元素数）。对于大型问题，将 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]。
b — 线性不等式约束实数向量
线性不等式约束，指定为实数向量。b 是与 A 矩阵相关的包含 M 个元素的向量。对于大型问题，将 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]。
Aeq — 线性等式约束实矩阵
线性等式约束，指定为实矩阵。Aeq 是 Me×N 矩阵，其中 Me 是等式的数目，而 N 是变量的数目（x0 中的元素数）。对于大型问题，将 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]。
beq — 线性等式约束实数向量
线性等式约束，指定为实数向量。beq 是与 Aeq 矩阵相关的包含 Me 个元素的向量。对于大型问题，将 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]。
lb — 下界实数向量
下界，指定为实数向量。如果 x0 中的元素数等于 lb 中的元素数，则 lb 指定
x[i] >= lb[i]（对于全部 i）。
如果 length(lb) < length(x0)，则 lb 指定
x[i] >= lb[i] (1 <= i <= length(lb))。
如果 lb 的元素数少于 x0，求解器将发出警告。
示例： 要指定所有 x 分量为正，请使用 lb = zeros(size(x0))。
ub — 上界实数向量
上界，指定为实数向量。如果 x0 中的元素数等于 ub 中的元素数，则 ub 指定
x[i] <= ub[i]（对于全部 i）。
如果 length(ub) < length(x0)，则 ub 指定
x[i] <= ub[i] (1 <= i <= length(ub))。
如果 ub 的元素数少于 x0，求解器将发出警告。
示例： 要指定 x 的所有分量小于 1，请使用 ub = ones(size(x0))。
x0 — 初始点[] （默认） | 实数向量
初始点，指定为实数向量。当 f 存在时，x0 中的元素数与 f 中的元素数相同。否则，该数字与 A 或 Aeq 的列数相同。
提供 x0 会改变 intlinprog 收敛所需的时间量。很难预测 x0 如何影响求解器。
x0 必须关于所有约束都可行。如果 x0 不可行，求解器会出错。如果您没有可行的 x0，请设置 x0 = []。
示例： x0 = 100 .*rand(size(f))
options — intlinprog 的选项使用 optimoptions 创建的选项
intlinprog 的选项，指定为 optimoptions 的输出。
| 所有算法 | |
| AbsoluteGapTolerance | 非负实数。如果内部计算的目标函数的上界 (U) 和下界 (L) 之间的差小于或等于 AbsoluteGapTolerance，则 intlinprog 停止，默认值 NaN 为占位符，intlinprog 将根据算法类型自动覆盖：
|
| Algorithm | 选择优化算法：
|
| ConstraintTolerance | 非负实数。是从 1e-10 到 1e-3 的实数值，默认值 NaN 为占位符，intlinprog 将根据算法类型自动覆盖：
|
| RelativeGapTolerance | 0 到 1 范围内的实数。如果内部计算的目标函数上界 (U) 和下界 (L) 之间的相对容差 (U-L)/abs(U) 小于或等于 RelativeGapTolerance，则 intlinprog 停止，默认值为 1e-4。 |
| highs 算法 | |
| Display | 显示级别：
|
| MaxNodes | 严格正整数，它是 intlinprog 在分支定界过程中探查的最大节点数，默认值为 10000000。 |
| MaxTime | 非负实数，它是 intlinprog 运行的最长时间（以秒为单位），默认值为 7200。 |
| legacy 算法 | |
| LPMaxIterations | 严格正整数，在分支定界过程中每个节点的单纯形算法迭代的最大次数。默认值 -1 为占位符，intlinprog 内部使用 max(30000, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables)) 覆盖该默认值，其中 numberOfEqualities 表示 Aeq 的行数，numberOfInequalities 表示 A 的行数，numberOfVariables 表示 f 的元素数。 |
示例： options = optimoptions(:intlinprog,Display="final")
problem — 封装输入和选项的结构体 的选项结构体
封装输入和选项的结构体，用下列字段指定。
| 字段名称 | 条目 |
| f | 表示目标 f'*x 的向量（必需） |
| intcon | 表示取整数值的变量的向量，或指定扩展整数约束的 IntegerConstraint 对象（必需） |
| Aineq | 线性不等式约束 Aineq*x ≤ bineq 中的矩阵 |
| bineq | 线性不等式约束 Aineq*x ≤ bineq 中的向量 |
| Aeq | 线性等式约束 Aeq*x = beq 中的矩阵 |
| beq | 线性等式约束 Aeq*x = beq 中的向量 |
| lb | 由下界组成的向量 |
| ub | 由上界组成的向量 |
| x0 | 初始可行点 |
| solver | "intlinprog"（必需） |
| options | 使用 optimoptions 创建的选项（必需） |
您必须在问题结构体中至少指定以下字段。其他字段是可选的：
- f
- intcon
- solver
- options
示例：
f = [1,2,3]
intcon = [2,3]
options = optimoptions("intlinprog")
Aineq = [-3 -2 -1]
bineq = [-20]
lb = [-6.1,-1.2,7.3]
solver = "intlinprog"
problem = (;f,intcon,options,Aineq,bineq,lb,solver)
# 输出参数
x — 解实数向量
解，以向量形式返回，它在所有边界、整数约束和线性约束的限制下最小化 f'*x。
当问题不可行或无界时，x 为 Float64[]。
fval — 目标值实数标量
目标函数值，以解 x 处的标量值 f'*x 形式返回。
当问题不可行或无界时，fval 为 NaN。
exitflag - intlinprog 停止的原因整数
intlinprog 停止的原因，以整数形式返回。
| 退出标志 | |
| 1 | intlinprog 收敛于解 x。 |
| 0 | intlinprog 提前停止超过最大迭代次数或超过最大迭代时间。 |
| -1 | 求解器失去可行性。 |
| -2 | intlinprog 找不到可行点。 |
| -3 | 解无界。 |
| -5 | 原始问题与对偶问题均不可行。 |
output - 有关优化过程的信息结构体
有关优化过程的信息，以包含下列字段的结构体形式返回。
| 优化过程的信息 | |
| iterations | 迭代次数 |
| algorithm | 使用的优化算法 |
| message | 退出消息 |
lambda - 解处的拉格朗日乘数结构体
解处的拉格朗日乘数，以包含下列字段的结构体形式返回。
| 解处的拉格朗日乘数 | |
| ineqlin | 对应于 A 和 b 的线性不等式 |
| eqlin | 对应于 Aeq 和 beq 的线性等式 |
| lower | 对应于 lb 的下界 |
| upper | 对应于 ub 的上界 |
线性约束的拉格朗日乘数满足以下具有 length(f) 个分量的方程：
基于拉格朗日函数:
此符号约定与非线性求解器的符号约定一致。然而，此符号与许多线性规划文献中的符号相反，因此 intlinprog 拉格朗日乘数是关联的“影子价格”的负数。
# 局限性
- 对于 highs 算法，解 x[intcon] 中一些应为整数值的分量并不是精确的整数。intlinprog 将处在整数容差 ConstraintTolerance 内的所有解值视为整数；
要将所有应为整数的解值舍入为精确的整数，请使用 nearest 函数。
x[intcon] = nearest.(x[intcon])提示
舍入解可能导致解变得不可行。舍入后需要检查可行性。
- intlinprog 不允许问题的分量（如 f、b 或 ub 中的系数）的绝对值超过 1e20（对于 "legacy" 算法无此限制），也不允许线性约束矩阵 A 和 Aeq 的任意分量绝对值超过或等于 1e15。
# 提示
要指定二元变量，请在 intcon 中将变量设置为整数，并指定其下界为 0，上界为 1；
如果提供的是整数分量的逻辑索引，即用 1 指示整数的二元向量，请使用 find 将其转换为 intcon 形式。例如，
logicalindices = [1,0,0,1,1,0,0]
intcon = findall(isone,logicalindices)
intcon = 3-element Vector{Int64}:
1
4
5
# 另请参阅
linprog | optimoptions | prob2struct | mpsread | integerConstraint