构造包含多变量配对的约束

Question

有没有可能在PuLP中利用LpVariables的配对来制定约束？你知道吗

更具体地说，假设我有LpVariablesx1，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组？你知道吗

Answer 1

下面是一个完整的工作示例，可以满足您的需要。它应该产生下面的输出。如您所见，选择了8个x，并且遵守了至少从类型1（在我的示例中为类型0）和类型2（在我的示例中为类型1）中选择一个的规则，以及至少一个组中有两个选择的变量的要求。你知道吗

解决这个问题的诀窍如this question的答案所述

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))