0

我需要一些方法来在 python cvxpy 优化任务约束中将整数变量的总和限制为 1。

我不想要的是强制变量的总和为 1，我只需要一个函数来将 sum(x) 的结果上限为 1，以便在约束中使用它。我要建模的是一个约束，例如：

y[i] >= if sum(x) >= 1 then 1 else 0

y 是一个布尔变量，x需要是整数变量。我似乎无法找到解决这个问题的方法。我试过使用 min 和 cvxpy.minimal 函数

y[i] >= min(sum(x), 1)

和

y[i] >= cvxpy.minimal(sum(x), x[test])

其中 x[test] 每个约束总是 1，但两种方法都不起作用。第一个给出错误，因为不允许严格的不等式，第二个给出一个错误，即约束违反了 DCP。

我发现唯一可以工作的是一个小“黑客”，我将总和乘以 0.001（总和永远不会大于 1000，因此结果总是在 0 和 1 之间）

y[i] >= sum(x) * 0.001

但这不知何故完全破坏了求解器，甚至只有几个约束和变量（500、100）的问题似乎无休止地运行。（30+分钟仍然没有解决方案）这个“hack”的最大变量数量<100，运行时间只有几分钟，这真的是不可接受的

____更新以获得更多说明：

我想要 X 数量的产品 Y 并且我知道卖家 Z 有多少产品 Y 的库存。我还需要考虑每个卖家的运费（固定数量为 1） 这个问题很容易描述如下：

             Product1  Product2  Product3
seller1 has  3         4         5
seller2 has  0         1         10

wanted order 2         1         7

这等同于问题（为简单起见，忽略约束 x1 >= 0）

min 1*x1 + 1*x2 + 1*x3 + 1*x4 + 0.9*x5 + 0.95*x6 + y1 + y2
s.t. 
     x1 <= 3
     x2 <= 4
     x3 <= 5
     x4 <= 0
     x5 <= 1
     x6 <= 10
     x1 + x4 >= 2
     x2 + x5 >= 1
     x3 + x6 >= 7
     y1 >= if x1 + x2 + x3 > 0 then 1 else 0
     y2 >= if x4 + x5 + x6 > 0 then 1 else 0
4

1 回答 1

0

如果性能不佳，请考虑使用更好的 MIP 求解器。CVXPY 支持不同的求解器（有些很好，有些只对玩具问题有用）。

其次，对单个变量（比如说）进行操作可能x[i,j]比对总和（这称为分解）更好。IE

y[i] = 0 => x[i,j] = 0

或者

x[i,j] <= 100*y[i]

当然，我们假设我们最小化y[i]（否则我们需要使用双向暗示）。

因此，在您更新的模型中，我们有：

y1 >= if x1 + x2 + x3 > 0 then 1 else 0

这可以以分解的形式建模为：

x1 <= 100*y1
x2 <= 100*y1
x3 <= 100*y1

或汇总：

x1+x2+x3 <= 100*y1

根据求解器的不同，分解的版本可能效果更好（一些高级求解器可以识别聚合结构）。

从建模的角度来看，我可能会使用y[i]和x[i,j]作为变量。这更合乎逻辑（对我来说）。

于 2019-12-05T01:04:49.093 回答