홈>2020-02-26 08:34

python - Google OR 도구를 사용하여 이진 제약 조건 설정

저는 OR 도구를 사용하고 있습니다. 특히 예약 용도를보고 있습니다. Google의 주요 예 ( https://github.com/google/or-tools/blob/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)])

pythonor-tools

답변 # 1

Laurent의 답변을 자세히 설명하려면 :

길이가 4 인 목록에서 길이가 2 인 시퀀스를 피하려면

[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()]

답변 # 2
Not ()은 부울 변수의 부정입니다.

https://en.wikipedia.org/wiki/Boolean_satisfiability_problem을 참조하십시오.

주된 아이디어는 주어진 패턴을 금지하고 싶다면 :

v0 = 거짓, v1 = 참, v2 = 참, v3 = 거짓

이것은 위치 1에서 시작하는 길이 2의 시퀀스입니다. v0이 true이거나 v1이 false이거나 v2가 false이거나 v3이 true임을 지정하는 BoolOr을 추가합니다.

이러한 조건 중 하나라도 해당되면이 특정 패턴이 존재하지 않습니다.

이것은
와이즈 비즈
.

BoolOr([v0, v1.Not(), v2.Not(), v3])

Python2.net

python - Google OR 도구를 사용하여 이진 제약 조건 설정

관련 자료