使用 CVXPY 解决具有条件最小组大小的分配问题

Question

我正在使用cvxpy内python来解决特定类型的分配问题。我想以最小化成本的方式将 M 人分配到 N 个组，对组有以下限制：

1. 组的成员不能超过 J 个
2. 如果一个组被填充，它必须至少有 K 个成员，否则一个组可以有零个成员。

当然，K <= J。我可以忽略上面的#2 来解决问题。在下面的例子中，M = 6，N = 3 和 J = 3。理想情况下，我想设置 K = 2。我生成的偏好使得每个人都喜欢第 1 组（成本函数中的第 1 列），然后大多数人更喜欢第 2 组，但一个人更喜欢第 3 组而不是第 2 组：

import numpy as np import cvxpy as cp

preference = np.array([[1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,3,2]])

groupmax = np.array([3,3,3])

selection = cp.Variable(shape=preference.shape,boolean=True)

group_constraint_1 = cp.sum(selection,axis=0) <= groupmax

assignment_constraint = cp.sum(selection,axis=1) == 1

cost = cp.sum(cp.multiply(preference,selection))

constraints = [group_constraint_1,assignment_constraint]

assign_prob = cp.Problem(cp.Minimize(cost),constraints)

assign_prob.solve(solver=cp.GLPK_MI)

print(selection.value)

解决方案/任务是：

[[1. 0. 0.]
 [1. 0. 0.]
 [1. 0. 0.]
 [0. 1. 0.]
 [0. 1. 0.]
 [0. 0. 1.]]

也就是说，我有一个最大大小为 3 的组，另一个大小为 2 的组和一个大小为 1 的组。在我的理想设置中，一组 1（组 3）太小了，必须分配那个人到第 2 组。请注意，如果我只是将最小组大小设置为 2，则会得到三组 2：

import numpy as np import cvxpy as cp

preference = np.array([[1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,3,2]])

groupmax = np.array([3,3,3])

groupmin = np.array([2,2,2])

selection = cp.Variable(shape=preference.shape,boolean=True)

group_constraint_1 = cp.sum(selection,axis=0) <= groupmax

group_constraint_2 = cp.sum(selection,axis=0) => groupmin

assignment_constraint = cp.sum(selection,axis=1) == 1

cost = cp.sum(cp.multiply(preference,selection))

constraints = [group_constraint_1,group_constraint_2,assignment_constraint]

assign_prob = cp.Problem(cp.Minimize(cost),constraints)

assign_prob.solve(solver=cp.GLPK_MI)

print(selection.value)

现在的解决办法是：

[[1. 0. 0.]
 [1. 0. 0.]
 [0. 1. 0.]
 [0. 1. 0.]
 [0. 0. 1.]
 [0. 0. 1.]]

我尝试了以下解决方法，但下面的第三个约束被拒绝，cvxpy因为问题不再是 DCP。我认为问题在于我将一个变量乘以约束中的另一个变量。我想不出另一种方法来使组中的总人数大于 2 或恰好为零：

import numpy as np
import cvxpy as cp

preference = np.array([[1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,3,2]])

groupmax = np.array([3,3,3])

selection = cp.Variable(shape=preference.shape,boolean=True)

switch_1 = cp.Variable(shape=preference.shape[1],boolean=True)

switch_2 = cp.Variable(shape=preference.shape[1],boolean=True)

group_constraint_1 = cp.sum(selection,axis=0) <= groupmax

group_constraint_2 = cp.sum(selection,axis=0) - 2 * switch_1 >= 0

group_constraint_3 = cp.sum(selection,axis=0) * switch_2 == 0

switch_constraint = switch_1 + switch_2 == 1

assignment_constraint = cp.sum(selection,axis=1) == 1

cost = cp.sum(cp.multiply(preference,selection))

constraints = [group_constraint_1,group_constraint_2,group_constraint_3,
               switch_constraint,assignment_constraint]

assign_prob = cp.Problem(cp.Minimize(cost),
                         constraints)

assign_prob.solve(solver=cp.GLPK_MI)

print(selection.value)

我现在收到以下错误： DCPError: Problem does not follow DCP rules.

有没有办法合并这个非标准约束？另外，如果我可以使用上述约束，我可以解决我的问题，但如果您能告诉我如何合并如下约束，我可以更轻松地解决我的问题：

1. 组大小必须是零、J 或 K 的倍数。

Answer 1

四处寻找后，我找到了解决我自己问题的方法。以下解决问题：

import numpy as np
import cvxpy as cp

preference = np.array([[1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,3,2]])

groupmax = np.array([3,3,3])

selection = cp.Variable(shape=preference.shape,boolean=True)

bind_2 = cp.Variable(shape=preference.shape[1],boolean=True)

bind_3 = cp.Variable(shape=preference.shape[1],boolean=True)

group_constraint_1 = cp.sum(selection,axis=0) <= groupmax

group_constraint_2 = (1 - bind_2) * 2 >= 2 - cp.sum(selection,axis=0)

group_constraint_3 = (1 - bind_3) * 4 >= cp.sum(selection,axis=0)

bind_constraint = bind_2 + bind_3 == 1

assignment_constraint = cp.sum(selection,axis=1) == 1

cost = cp.sum(cp.multiply(preference,selection))

constraints = [group_constraint_1,group_constraint_2,group_constraint_3,
               bind_constraint,assignment_constraint]

assign_prob = cp.Problem(cp.Minimize(cost),constraints)

assign_prob.solve(solver=cp.GLPK_MI)

print(selection.value)

现在，我得到以下解决方案：

[[1. 0. 0.]
 [0. 1. 0.]
 [1. 0. 0.]
 [0. 1. 0.]
 [0. 1. 0.]
 [1. 0. 0.]]

解释：

1. 这两个bind变量是二进制变量，表示约束 2 和 3 是否绑定
2. 当 bind_2 = 0 时，约束 2 无论如何都成立，因为右侧的第二项是非负的。当 bind_2 = 1 时，只有右边的第二项大于或等于 2 才能满足约束。
3. 当bind_3 = 0时，约束3无论如何都成立，因为右边的项以3为界，根据约束1。当bind_3 = 1时，只有右边的项为零（项是非负数）。
4. 第四个约束限制两个bind变量中只有一个等于 1。因此，每个组的总数可以大于 2 或恰好为零。

到目前为止，我无法扩展到组大小需要是零、J 或 K 的倍数的情况。原因是我无法将mod函数与 cvxpy 一起使用。

解决方案的想法来自这里