如何在 MIP 求解器中表达 2 个二进制变量不同

Question

我有一个分配问题，我想将多个球分配给不同的容器。每个球都有一定的尺寸——小、中、大。我想添加一个约束，即具有 2 种不同颜色的球应该位于不同的容器中。

我正在使用 google-OR-tools 线性求解器。显然，我无法在建模构造中表达

!=

约束。

我能够像下面这样开始：

from ortools.linear_solver import pywraplp
import itertools

s = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

balls_size = ["s", "m", "s", "m", "l", "s", "m"]
balls_id_size = {i: j for i, j in zip(range(len(balls_size)), balls_size)}

bins = ["a", "b", "c"]

dv = {(i, j): s.BoolVar("") for i, j in itertools.product(balls_id_size, bins)}

我希望所有垃圾箱所容纳的球的尺寸都应该是同质的

Answer 1

请查看下面的代码清单。我添加了注释，以便代码不言自明。本质上，该方法是对每个箱子计算小、中、大尺寸球的数量 - 例如考虑 bin

a

，如果

sum_dv_["a", "s"] >= 1

（bin a 中的小球数量），则指示变量

bin_dv_["a", "s"] == 1

。然后，因为我们只能在垃圾箱里放一种尺寸的球，所以：

bin_dv_["a", "s"] + bin_dv_["a", "m"] + bin_dv_["a", "l"] <= 1

。这是对所有垃圾箱完成的。

from ortools.linear_solver import pywraplp
import itertools

s = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

balls_size = ["s", "m", "s", "m", "l", "s", "m"]
balls_id_size = {i: j for i, j in zip(range(len(balls_size)), balls_size)}

bins = ["a", "b", "c"]

dv = {(i, j): s.BoolVar("") for i, j in itertools.product(balls_id_size, bins)}

# each ball should be assigned to 1 bin
for i in balls_id_size:
    s.Add(sum(dv[i, bn] for bn in bins) == 1)

# placeholder decision variable to store number of small/medium/large sized
# balls in each bin
sum_size_bin = {
    (i, j): s.IntVar(0, 10, "") for i, j in itertools.product(bins, ["s", "m", "l"])
}
# boolean flag. will be turned = 1 if corresponding sum >= 1
# i.e. if number of small balls in bin 'b' is 2 (say), then the corresponding boolean flag = 1
# sum_size_bin[b, "s"] >= 1 ==> bool_size_bin[b, "s"] = 1
# above constraint will be stated later
bool_size_bin = {
    (i, j): s.BoolVar("") for i, j in itertools.product(bins, ["s", "m", "l"])
}

s_balls = [i for i, j in balls_id_size.items() if j == "s"]
m_balls = [i for i, j in balls_id_size.items() if j == "m"]
l_balls = [i for i, j in balls_id_size.items() if j == "l"]

for b in bins:
    # number of small sized balls in bin 'b'
    s.Add(
        sum_size_bin[b, "s"]
        == sum([j for i, j in dv.items() if (i[0] in s_balls) and (i[1] == b)])
    )
    # 100 is big_M
    # if number of small sized balls in bin 'b' is >= 1 then the corresponding boolean flag == 1
    s.Add(sum_size_bin[b, "s"] - 100 * bool_size_bin[b, "s"] <= 0)

    # number of medium sized balls in bin 'b'
    s.Add(
        sum_size_bin[b, "m"]
        == sum([j for i, j in dv.items() if (i[0] in m_balls) and (i[1] == b)])
    )
    # 100 is big_M
    # if number of medium sized balls in bin 'b' is >= 1 then the corresponding boolean flag == 1
    s.Add(sum_size_bin[b, "m"] - 100 * bool_size_bin[b, "m"] <= 0)

    # number of large sized balls in bin 'b'
    s.Add(
        sum_size_bin[b, "l"]
        == sum([j for i, j in dv.items() if (i[0] in l_balls) and (i[1] == b)])
    )
    # 100 is big_M
    # if number of large sized balls in bin 'b' is >= 1 then the corresponding boolean flag == 1
    s.Add(sum_size_bin[b, "l"] - 100 * bool_size_bin[b, "l"] <= 0)

    # in each bin we can have balls of only 1 size
    s.Add(bool_size_bin[b, "s"] + bool_size_bin[b, "m"] + bool_size_bin[b, "l"] <= 1)

s.Solve()

# investigate the solution
for b in bins:
    item_binMapping = [i for i in dv if ((i[1] == b) and (dv[i].SolutionValue() > 0.1))]
    item_size = [
        j for i, j in balls_id_size.items() if i in [j[0] for j in item_binMapping]
    ]
    print(list(zip(item_binMapping, item_size)))

以上结果为：

# (item_id, bin, size)
[((1, 'a'), 'm'), ((3, 'a'), 'm'), ((6, 'a'), 'm')]
[((0, 'b'), 's'), ((2, 'b'), 's'), ((5, 'b'), 's')]
[((4, 'c'), 'l')]

所有箱子的球数都是相同的。

我们可以添加对称破缺约束 - 因为现在 bin a 或 bin b 都可以全部为中型或全部为小型。这可能因求解器而异，或者也可能在不同的运行中。我们可以强制，bin a 应该始终有小球，以便所有运行都会产生相同的输出。