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

Question

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

群组成员不能超过 J
如果一个组被填充，它必须至少有 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)

solution/assignment 是：

[[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.

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

组大小必须是零、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.]]

说明：

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

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

解决方案的想法来自here

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

Solving Assignment Problem with conditional minimum group sizes using CVXPY

mathematical-optimization

linear-programming

integer-programming

cvxpy