制定涉及多个变量配对的约束

Question

是否可以在 PuLP 中制定利用 LpVariables 配对的约束？

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

Answer 1

这是一个完整的工作示例，可以满足您的需求。它应该产生下面的输出。如您所见，已经选择了 8 个 x，并且遵守至少从类型 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))

制定涉及多个变量配对的约束

Formulate contraints that involve pairings of multiple LpVariables

python

linear-programming

pulp