Solving Assignment Problem with conditional minimum group sizes using CVXPY

Question

I'm using cvxpy within python to solve a particular type of assignment problem. I'd like to assign M people to N groups in a way that minimizes cost, with the following constraints on groups:

1. Groups cannot have more than J members
2. If a group is populated, it has to have at least K members, otherwise a group can have zero members.

Of cousre, K <= J. I can solve the problem ignoring #2 above. In the below example, M = 6, N = 3 and J = 3. Ideally, I'd like to set K = 2. I generate preferences such that everyone prefers group 1 (column 1 in the cost function), most people then prefer group 2, but one person prefers group 3 to group 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)

The solution/assignment is :

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

That is, I have one group with max size 3, another group with size 2, and a group with size 1. In my ideal setup, a group of 1 (group 3) is too small, and that person would have to be assigned to group 2. Note, if I simply put a minimum group size of 2, I instead get three groups of 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)

The solution is now:

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

I tried the following workaround, but the third constraint below is rejected by cvxpy because the problem is no longer DCP. I think the issue is that I am multiplying a variable by another variable in the constraint. I can't figure out another way to have the total number of people in a group either be greater than 2 or exactly zero:

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)

I now get the following error: DCPError: Problem does not follow DCP rules.

Is there a way to incorporate this nonstandard constraint? Also, if I can use the above constraints, I can solve my problem, but I can solve my problem even more easily if you can tell me how to incorporate a constraint like the following:

1. Group sizes must either be multiples of zero, J, or K.

Carine

Answer 1

After searching around, I found the solution to my own problem. The following solves the problem:

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)

Now, I get the following solution:

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

To explain:

1. The two bind variables are binary variables denoting whether constraints 2 and 3 are binding
2. When bind_2 = 0, Constraint 2 holds no matter what, since the second term on the right hand side is non-negative. When bind_2 = 1, the constraint can only be satisfied if the second term on the right hand side is greater than or equal to 2.
3. When bind_3 = 0, Constraint 3 holds no matter what, since the term on the right is bounded by 3, according to Constraint 1. When bind_3 = 1, the constraint can only be satisfied if the term on the right is zero (the term is non-negative).
4. The fourth constraint limits only one of the two bind variables to equal 1. So, each group total can either be larger than 2 or exactly zero.

Thus far, I cannot extend to the case where the group sizes need to be multiple so of zero, J, or K. The reason is that I can't use the mod function with cvxpy.

The idea for the solution came from here

Carine