Сформулируйте ограничения, которые включают спаривания нескольких LpVariables - PullRequest
Новая
       54

Сформулируйте ограничения, которые включают спаривания нескольких LpVariables

0 голосов
/ 18 декабря 2018

Можно ли сформулировать ограничения, которые используют пары LpVariables в PuLP?

В частности, скажем, что у меня есть LpVariables x1, x2, ... x100 (все двоичныекатегория), каждый из которых представляет объект.Все эти объекты имеют атрибут type, который является 1, 2, 3 или 4, а также атрибут group, который также является 1, 2, 3 или 4.

Как бы я создал следующее ограничение (я не уверен, как бы я это сделал в PuLP):

Две переменные в решениидолжен быть в том же group (может быть любым group), и должен иметь тип 1, а также должен иметь тип 2.

Само решение - это каждая переменная,8 из которых имеют значение True (указывает, что они являются частью решения), а остальные имеют значение False (указывает, что они не являются частью решения), выбранные множеством других ограничений.

Итак, ограничение, которое я хочу добавить в булеву логику для решения: 

(type 1 object in group 1 AND type 2 object in group 1) OR
(type 1 object in group 2 AND type 2 object in group 2) OR
(type 1 object in group 3 AND type 2 object in group 3) OR
(type 1 object in group 4 AND type 2 object in group 4)

Кроме того, есть ли способ абстрагировать это ограничение до n групп в целлюлозе?

1 Ответ

0 голосов
/ 21 декабря 2018

Вот полный рабочий пример, который делает то, что вы хотите.Он должен произвести вывод ниже.Как вы можете видеть, 8 из х были выбраны, и соблюдается правило, по крайней мере, одно из типа 1 (тип 0 в моем примере) и типа 2 (тип 1 в моем примере), как и требование, что прихотя бы в одной группе есть две выбранные переменные.

Хитрость в этом заключается в том, как описано в ответе, данном на этот вопрос 

x_picked: [3, 9, 22, 49, 64, 77, 84, 93]
group_picked: [3, 0, 1, 3, 3, 0, 3, 3]
type_picked: [0, 3, 3, 3, 3, 0, 1, 2]
n_in_group_soln: [2. 1. 1. 4.]
two_or_more_in_group_soln: [1. 0. 0. 1.]

Самостоятельный пример выполнениячто ты хочешь (Python3): 

from pulp import *
import numpy as np

n = 100
M = 100
n_grps = 4
n_typs = 4

# Binary varaibles; 1 means include in solution, 0 means don't include
x = LpVariable.dicts("x_%s", range(n), cat='Binary')

# Assign types and groups
np.random.seed(0)

# All of these objects have a type attribute, which is either 1, 2, 3, or 4 (use zero-indexes)
type_of_x = np.random.randint(0, n_typs, n)

# as well as a group attribute, which is also 1, 2, 3, or 4. (use zero-indexes)
group_of_x = np.random.randint(0, n_grps, n)

# Also randomly assign a cost to including each solution (obj. to minimise this)
cost_of_x = np.random.random(n)

# Initialise problem and set objective:
prob = pulp.LpProblem('Minimize', pulp.LpMaximize)
prob += lpSum([x[i]*cost_of_x[i] for i in range(n)])

# CONSTRAINTS
# Two variables in the solution must be in the same group (could be any group)
n_in_group = LpVariable.dicts("n_in_group_%s", range(n_grps), cat='Integer')
two_or_more_in_group = LpVariable.dicts("two_or_more_in_group_%s", range(n_grps), cat='Binary')

for i in range(n_grps):
    prob += n_in_group[i] == lpSum([x[j] for j in range(n) if type_of_x[j] == i])
    prob += two_or_more_in_group[i] >= (n_in_group[i] - 1)/M
    prob += two_or_more_in_group[i] <= (1 - (2 - n_in_group[i])/M)

# Need at least one for the two_or_more_in_group vars to be true:
prob += lpSum([two_or_more_in_group[i] for i in range(n_grps)]) >= 1

# and one must of type 1 (note zero index)
prob += lpSum([x[j] for j in range(n) if group_of_x[j] == 0]) >= 1

# and one must be of type 2 (note zerod index)
prob += lpSum([x[j] for j in range(n) if group_of_x[j] == 0]) >= 1

# Finally require that 8 are picked:
prob += lpSum([x[j] for j in range(n)]) == 8

# Solve and display outputs
prob.solve()
x_soln = np.array([x[i].varValue for i in range(n)])
n_in_group_soln = np.array([n_in_group[i].varValue for i in range(n_grps)])
two_or_more_in_group_soln = np.array([two_or_more_in_group[i].varValue for i in range(n_grps)])

x_picked = [i for i in range(n) if x_soln[i] > 0.5]
group_picked = [group_of_x[i] for i in x_picked]
type_picked = [type_of_x[i] for i in x_picked]

print("x_picked: " + str(x_picked))
print("group_picked: " + str(group_picked))
print("type_picked: " + str(type_picked))
print("n_in_group_soln: " + str(n_in_group_soln))
print("two_or_more_in_group_soln: " + str(two_or_more_in_group_soln))
...