使用Google或Tools设置二进制约束

Question

我一直在使用or-tools，尤其是查看其调度用途。我觉得我现在已经在图书馆上掌握了，尽管Google的主要示例有一个方面(https://github.com/google/google/or-tools/blob/master/master/examples/python/shift_scheduling_sat.py(麻烦理解。我遇到问题的功能是：add_soft_sequence_constraint()和相关：negated_bounded_span(相关代码在下面(。

这些旨在限制一个人可以连续工作的班次数量，尽管我无法弄清楚这是如何实现的。

我的问题是：使用.not((到底是什么结果？我很难在上面找到任何文档或为其进行清晰的测试。为什么 negated_bounded_space()(完全取决于.not((的函数(？最后，在两种情况下，在add_soft_sequence_constraint中，它如何知道您工作一个长序列(即，连续6个偏移(之间的差异，这将不允许使用，而2个较短的序列(4个偏移，一个休息，然后是3个班次(被允许，但与长序列相同(或更多(？

任何帮助都会很棒，并且非常感谢，我希望能够使用和调整代码，但是在正确理解它之前，我会感到不舒服。

def negated_bounded_span(works, start, length):
    sequence = []
    # Left border (start of works, or works[start - 1])
    if start > 0:
        sequence.append(works[start - 1])
    for i in range(length):
        sequence.append(works[start + i].Not())
    # Right border (end of works or works[start + length])
    if start + length < len(works):
        sequence.append(works[start + length])
    return sequence
def add_soft_sequence_constraint(model, works, hard_min, soft_min, min_cost,
                                 soft_max, hard_max, max_cost, prefix):
    # Forbid sequences that are too short.
    for length in range(1, hard_min):
        for start in range(len(works) - length - 1):
            model.AddBoolOr(negated_bounded_span(works, start, length))

    # Just forbid any sequence of true variables with length hard_max + 1
    for start in range(len(works) - hard_max - 1):
        model.AddBoolOr(
            [works[i].Not() for i in range(start, start + hard_max + 1)])

Answer 1

not((是布尔变量的否定。

请参阅https://en.wikipedia.org/wiki/boolean_satissibaly_problem。

主要思想是，如果您要禁止给定模式：

v0 = false，v1 = true，v2 = true，v3 = false

这是从位置1开始的长度2的序列，您添加一个布洛尔指定V0为true，或者V1为false，或者V2是false，或V3为true。

如果这些条件中的任何一个是正确的，则不存在此特定模式。

这是写为

的

boolor([[V0，v1.not((，v2.not((，v3](

。

Answer 2

详细说明laurent的答案：

如果要避免长度列表中的长度2序列4：

• [1,1,0,0]-> BoolOr[v0.Not(),v1.Not(),v2]
• [0,1,1,0]-> BoolOr[v0, v1.Not(), v2.Not(), v3]
• [0,0,1,1]-> BoolOr[v1, v2.Not(), v3.Not()]

我还开了一个github https://github.com/google/or-tools/issues/1399，作为行

for start in range(len(works) - length - 1):

可能是错误的。

长度为4和硬最小值的小示例3：

from ortools.sat.python import cp_model

def negated_bounded_span(works, start, length):
    sequence = []
    # Left border (start of works, or works[start - 1])
    if start > 0:
        sequence.append(works[start - 1])
    for i in range(length):
        sequence.append(works[start + i].Not())
    # Right border (end of works or works[start + length])
    if start + length < len(works):
        sequence.append(works[start + length])
    return sequence

if __name__ == '__main__':
    model = cp_model.CpModel()
    works = [model.NewBoolVar(f'{i}') for i in range(4)]
    for length in range(1, 3):
        print(f'Length {length}')
        for start in range(len(works) - length + 1):
            print(negated_bounded_span(works, start, length))

按照以下方式返回某些东西：

Length 1
[0.Not(), 1(0..1)]
[0(0..1), 1.Not(), 2(0..1)]
[1(0..1), 2.Not(), 3(0..1)]
[2(0..1), 3.Not()]
Length 2
[0.Not(), 1.Not(), 2(0..1)]
[0(0..1), 1.Not(), 2.Not(), 3(0..1)]
[1(0..1), 2.Not(), 3.Not()]