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

Question

我有一个问题，我有 4 个变量 x1, x2, x3 and 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-约束 (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，如您在问题中提到的，但默认情况下它们只是 non-negative。那么，对于 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零。

最后，请注意这个问题很强烈under-constrained：我们可以通过更改objective来选择一个完全不同的解决方案。这是我们要求 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]

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

Constrained optimization in python where one variable depends on another variable

python

linear-programming

constraint-programming