python - python 中的约束优化，其中一个变量依赖于另一个变量

Question

我有一个问题，我有 4 个变量 x1、x2、x3 和 x4。我需要在以下条件下查找 x1, x2, x3, x4 的值:

1. 1995 < 2*x1 + 4*x2 + 3*x3 + x4 < 2000
2. x1 >= 1.2*x2
3. x2 >= 1.3*x3
4. x3 >= 1.1*x4
5. x4 > 0.0

我可以使用 python-constraint ( https://labix.org/python-constraint ) 来完成此操作，但在我的系统上解决这个问题需要大约 30 分钟，这太长了。

from constraint import *

problem = Problem()
problem.addVariable("x1", range(100,500))
problem.addVariable("x2", range(100,500))
problem.addVariable("x3", range(100,500))
problem.addVariable("x4", range(100,500))

problem.addConstraint(lambda a, b, c, d: 2*a + 3*b + 4*c + 5*d > 1995, ["x1", "x2", "x3", "x4"])
problem.addConstraint(lambda a, b, c, d: 2*a + 3*b + 4*c + 5*d < 2005, ["x1", "x2", "x3", "x4"])
problem.addConstraint(lambda a, b: a >= 1.2 * b, ["x1", "x2"])
problem.addConstraint(lambda b, c: b >= 1.3 * c, ["x2", "x3"])
problem.addConstraint(lambda c, d: c >= 1.1 * d, ["x3", "x4"])
problem.addConstraint(lambda d: d > 0, ["x4"])

problem.getSolutions()

我还查看了 scipy.optimize.linprog，但我找不到传递条件 2、3 和 4 的方法，因为它依赖于同一问题中另一个变量的值。我可以使用 bounds 参数传递每个单独变量的边界，例如:

x1_bounds = (100, 200)
x2_bounds = (200, 300)

但是如何在边界内传递其他变量的值，例如 x1_bounds >= 1.2*x2？或者还有其他方法可以做到这一点吗？

这可以使用 Excel 中的 GRG 非线性求解器来解决，但我无法在 python 中找到等效的解决方案。

Answer 1

事实上，您的问题是线性的，因此它非常适合线性编程方法。然而，您将其提供给求解器时却没有关于问题线性的任何线索，因此它肯定会发现这很棘手:它几乎必须尝试每种可能性，这将需要很长时间。可以将您的约束重写为 python-constraint 求解器的不同形式(例如，它具有 MaxSumConstraint 约束形式)，这可能会更好，但理想情况下我认为您应该使用专门用于线性问题的求解器。

有一个名为 kiwisolver 的解算器，它可以完成您想要的操作。这是为该库转换的示例:

import kiwisolver

x1 = kiwisolver.Variable('x1')
x2 = kiwisolver.Variable('x2')
x3 = kiwisolver.Variable('x3')
x4 = kiwisolver.Variable('x4')

constraints = [1995 <= 2*x1 + 4*x2 + 3*x3 + x4,
               2*x1 + 4*x2 + 3*x3 + x4 <= 2000,
               x1 >= 1.2*x2,
               x2 >= 1.3*x3,
               x3 >= 1.1*x4,
               x4 >= 0]

solver = kiwisolver.Solver()

for cn in constraints:
    solver.addConstraint(cn)

for x in [x1, x2, x3, x4]:
    print(x.value())

这给出了

254.49152542372883
212.07627118644066
163.13559322033896
148.30508474576254

但是您也可以使用标准线性程序求解器，例如 scipy。您只需将不平等重新组织成正确的形式即可。

你想要:

1. 1995 < 2*x1 + 4*x2 + 3*x3 + x4 < 2000
2. x1 >= 1.2*x2
3. x2 >= 1.3*x3
4. x3 >= 1.1*x4
5. x4 > 0.0

所以我们将其重写为:

 2*x1 +  4*x2 +  3*x3 +  1*x4 < 2000
-2*x1 + -4*x2 + -3*x3 + -1*x4 < -1995
-1*x1 + 1.2*x2 + 0*x3 +  0*x4 < 0
 0*x1 + -1*x2 + 1.3*x3 + 0*x4 < 0
 0*x1 +  0*x2 + -1*x3 + 1.1*x4 < 0

您可以按照问题中提到的方式将 x1 添加到 x4 的范围，但默认情况下它们只是非负数。那么，对于 LP，我们还需要在可能的解决方案的多面体中选择我们想要优化的位置:在这种情况下，我将只选择总和最小的解决方案。所以这给了我们这个:

from scipy.optimize import linprog

output = linprog([1, 1, 1, 1],
                [[ 2,   4,   3,   1],
                 [-2,  -4,  -3,  -1],
                 [-1, 1.2,   0,   0],
                 [0,   -1, 1.3,   0],
                 [0,    0,  -1, 1.1]],
                [2000, -1995, 0, 0, 0])

print(output.x)

这给出

[274.92932862 229.10777385 176.23674912   0.        ]

这是最优LP解。请注意，它已使 x4 = 0:LP 通常不区分 > 和 >=，因此我们有一个解决方案，其中 >x4 为零，而不是大于零的微小 epsilon。

最后，请注意，该问题严重受限:我们可以通过改变目标来选择完全不同的解决方案。这是一个解决方案，我们要求 linprog 最大化 2*x1 + 4*x2 + 3*x3 + x4:

from scipy.optimize import linprog


output = linprog([-2, -4, -3, -1],
                 [[ 2,   4,   3,  1],
                  [-2,  -4,  -3, -1],
                  [-1, 1.2,   0, 0],
                  [0,   -1, 1.3, 0],
                  [0,    0,  -1, 1.1]],
                 [2000, -1995, 0, 0, 0])

print(output.x)

给予

[255.1293488  212.60779066 163.54445436 148.67677669]