linprog(method=’highs’)#

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)

线性规划:使用 HiGHS 求解器之一,在满足线性等式和不等式约束的条件下最小化线性目标函数。

线性规划解决以下形式的问题:

\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

其中 \(x\) 是决策变量向量;\(c\)\(b_{ub}\)\(b_{eq}\)\(l\)\(u\) 是向量;\(A_{ub}\)\(A_{eq}\) 是矩阵。

或者,即

最小化

c @ x

使得

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

请注意,除非使用 bounds 指定,否则默认情况下 lb = 0ub = None

参数:
c一维数组

要最小化的线性目标函数的系数。

A_ub二维数组,可选

不等式约束矩阵。 A_ub 的每一行指定了 x 上的线性不等式约束的系数。

b_ub一维数组,可选

不等式约束向量。 每个元素表示 A_ub @ x 对应值的上限。

A_eq二维数组,可选

等式约束矩阵。 A_eq 的每一行指定了 x 上的线性等式约束的系数。

b_eq一维数组,可选

等式约束向量。 A_eq @ x 的每个元素必须等于 b_eq 的相应元素。

bounds序列,可选

x 中的每个元素提供 (min, max) 对的序列,定义该决策变量的最小值和最大值。 使用 None 表示没有界限。 默认情况下,界限为 (0, None)(所有决策变量均为非负)。 如果提供单个元组 (min, max),则 minmax 将作为所有决策变量的界限。

method字符串

这是针对 'highs' 方法的文档,该方法在 ‘highs-ds’‘highs-ipm’ 之间自动选择。 也可用的方法包括 ‘interior-point’(默认)、‘revised simplex’‘simplex’(遗留)。

integrality一维数组或整数,可选

指示每个决策变量的整数约束类型。

0 : 连续变量;无整数约束。

1 : 整数变量;决策变量必须是 bounds 内的整数。

2 : 半连续变量;决策变量必须在 bounds 范围内或取值为 0

3 : 半整数变量;决策变量必须是 bounds 内的整数或取值为 0

默认情况下,所有变量都是连续的。

对于混合整数约束,请提供一个形状为 c.shape 的数组。为了从较短的输入推断每个决策变量的约束,该参数将使用 np.broadcast_to 广播到 c.shape

此参数目前仅由 'highs' 方法使用,否则将被忽略。

返回:
resOptimizeResult 对象

一个 scipy.optimize.OptimizeResult 对象,包含以下字段:

x一维数组

使目标函数最小化并满足约束的决策变量值。

fun浮点数

目标函数 c @ x 的最优值。

slack一维数组

松弛变量(名义上为正)的值,即 b_ub - A_ub @ x

con一维数组

等式约束的(名义上为零)残差,即 b_eq - A_eq @ x

success布尔值

当算法成功找到最优解时为 True

status整数

表示算法退出状态的整数。

0 : 优化成功终止。

1 : 达到迭代或时间限制。

2 : 问题似乎不可行。

3 : 问题似乎无界。

4 : HiGHS 求解器遇到问题。

message字符串

算法退出状态的字符串描述。

nit整数

执行的总迭代次数。 对于 HiGHS 单纯形法,这包括所有阶段的迭代。 对于 HiGHS 内点法,这不包括交叉迭代。

crossover_nit整数

HiGHS 内点法在交叉例程中执行的原始/对偶推送次数。 对于 HiGHS 单纯形法,此值为 0

ineqlinOptimizeResult 对象

与不等式约束 b_ub 对应的解和敏感性信息。 一个包含以下字段的字典:

residualnp.ndarray

松弛变量(名义上为正)的值,即 b_ub - A_ub @ x。 此量通常也称为“松弛量”。

marginalsnp.ndarray

目标函数相对于不等式约束右侧 b_ub 的敏感性(偏导数)。

eqlinOptimizeResult 对象

与等式约束 b_eq 对应的解和敏感性信息。 一个包含以下字段的字典:

residualnp.ndarray

等式约束的(名义上为零)残差,即 b_eq - A_eq @ x

marginalsnp.ndarray

目标函数相对于等式约束右侧 b_eq 的敏感性(偏导数)。

lower, upperOptimizeResult 对象

与决策变量的下限和上限 bounds 对应的解和敏感性信息。

residualnp.ndarray

数量 x - lb(下限)或 ub - x(上限)的(名义上为正)值。

marginalsnp.ndarray

目标函数相对于下限和上限 bounds 的敏感性(偏导数)。

另请参阅

有关其余参数的文档,请参阅 scipy.optimize.linprog

选项:
——-
maxiter整数

在任一阶段执行的最大迭代次数。 对于 ‘highs-ipm’,这不包括交叉迭代次数。 默认值为平台上 int 的最大可能值。

disp布尔值(默认:False

如果要在优化过程中将优化状态指示器打印到控制台,请设置为 True

presolve布尔值(默认:True

预求解尝试在将问题发送到主求解器之前识别微不足道的不可行性、识别微不足道的无界性并简化问题。 通常建议保留默认设置 True;如果要禁用预求解,请设置为 False

time_limit浮点数

解决问题允许的最大时间(秒); 默认值为平台上 double 的最大可能值。

dual_feasibility_tolerance双精度浮点数(默认:1e-07)

针对 ‘highs-ds’ 的对偶可行性容差。 ‘highs-ipm’ 的可行性容差使用此值和 primal_feasibility_tolerance 中的较小值。

primal_feasibility_tolerance双精度浮点数(默认:1e-07)

针对 ‘highs-ds’ 的原始可行性容差。 ‘highs-ipm’ 的可行性容差使用此值和 dual_feasibility_tolerance 中的较小值。

ipm_optimality_tolerance双精度浮点数(默认:1e-08

针对 ‘highs-ipm’ 的最优性容差。 允许的最小值为 1e-12。

simplex_dual_edge_weight_strategy字符串(默认:None)

单纯形对偶边权策略。 默认值 None 会自动选择以下选项之一。

'dantzig' 使用 Dantzig 选择最小负约化成本的原始策略。

'devex' 使用 [15] 中描述的策略。

steepest 使用 [16] 中描述的精确最陡边策略。

'steepest-devex' 从精确最陡边策略开始,直到计算成本过高或不精确时,切换到 devex 方法。

目前,None 总是选择 'steepest-devex',但随着新选项的出现,这可能会改变。

mip_rel_gap双精度浮点数(默认:None)

MIP 求解器的终止准则:当原始目标值与对偶目标界限之间的差距(按原始目标值缩放)小于或等于 mip_rel_gap 时,求解器将终止。

unknown_options字典

此特定求解器未使用的可选参数。 如果 unknown_options 非空,将发出警告,列出所有未使用的选项。

注释

方法 ‘highs-ds’ 是 C++ 高性能对偶修正单纯形实现 (HSOL) [13][14] 的封装。 方法 ‘highs-ipm’ 是 C++ 内点法 实现 [13] 的封装;它具有交叉例程,因此与单纯形求解器一样准确。 方法 ‘highs’ 会在这两者之间自动选择。 对于涉及 linprog 的新代码,我们建议明确选择这三个方法值中的一个,而不是 ‘interior-point’(默认)、‘revised simplex’‘simplex’(遗留)。

结果字段 ineqlineqlinlowerupper 都包含 marginals,即目标函数相对于每个约束右侧的偏导数。 这些偏导数也称为“拉格朗日乘子”、“对偶值”和“影子价格”。 marginals 的符号约定与许多非线性求解器产生的拉格朗日乘子相反。

参考文献

[13] (1,2)

Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. “HiGHS - high performance software for linear optimization.” https://highs.dev/

[14]

Huangfu, Q. and Hall, J. A. J. “Parallelizing the dual revised simplex method.” Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

[15]

Harris, Paula MJ. “Pivot selection methods of the Devex LP code.” Mathematical programming 5.1 (1973): 1-28.

[16]

Goldfarb, Donald, and John Ker Reid. “A practicable steepest-edge simplex algorithm.” Mathematical Programming 12.1 (1977): 361-371.