Решение задачи о назначении с условными минимальными размерами групп с использованием CVXPY - PullRequest
Новая
       45

Решение задачи о назначении с условными минимальными размерами групп с использованием CVXPY

0 голосов
/ 17 января 2019

Я использую cvxpy в python для решения определенного типа задачи назначения. Я хотел бы назначить M людей на N групп таким образом, чтобы минимизировать затраты со следующими ограничениями для групп:

  1. В группах не может быть более J участников
  2. Если группа заполнена, она должна содержать не менее K членов, в противном случае группа может иметь ноль членов.

Конечно, J <= K. Я могу решить проблему, игнорируя # 2 выше. В приведенном ниже примере M = 6, N = 3 и J = 3. В идеале я хотел бы установить K = 2. Я генерирую предпочтения так, что все предпочитают группу 1 (столбец 1 в функции стоимости), тогда большинство людей предпочитают группу 2, но один человек предпочитает группу 3 группе 2: </p> 

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.

1 Ответ

0 голосов
/ 17 января 2019

Обыскав вокруг, я нашел решение своей проблемы. Следующее решает проблему: 

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 = 3, ограничение 3 выполняется независимо от того, что, поскольку термин справа ограничен 3, согласно ограничению 1. Когда bind_3 = 1, ограничение может быть выполнено только в том случае, если термин справа равен нулю (термин неотрицательный).
  4. Четвертое ограничение ограничивает только одну из двух bind переменных равным 1. Таким образом, общее количество каждой группы может быть больше 2 или точно равно нулю.

До сих пор я не могу распространиться на случай, когда размеры группы должны быть кратны нулю, J или K. Причина в том, что я не могу использовать функцию mod с cvxpy.

Идея решения пришла от здесь

...