Планирование инструментов Google OR: максимизируйте общее значение последовательностей, которые разделены на сегменты с ограничениями (i) 1 на сегмент;(ii) нет совпадений - PullRequest
Новая
       38

Планирование инструментов Google OR: максимизируйте общее значение последовательностей, которые разделены на сегменты с ограничениями (i) 1 на сегмент;(ii) нет совпадений

0 голосов
/ 02 мая 2019

Я пытаюсь использовать инструменты Python Google OR (версия 6.10.6025) для решения проблемы комбинаторной оптимизации. У меня есть набор n-грамм, которые все получены из 1 длинной последовательности. Некоторые из n-грамм перекрываются, и у каждого есть значение. N-граммы разделены на сегменты, и я хочу выбрать n-граммы, которые максимизируют общее значение с двумя ограничениями: (1) ровно 1 н-грамм выбран из каждого сегмента; (2) ни одно из выбранных n-грамм не перекрывается.

Подход, который я пробовал, включает представление каждого n-грамма как OptionalIntervalVar, чтобы я мог использовать метод AddNoOverlap для добавления ограничения (2). В нем содержатся элементы из графиков работы сотрудников и примеров цеха: https://developers.google.com/optimization/scheduling/employee_scheduling, https://developers.google.com/optimization/scheduling/job_shop.

Ниже приведен мой код для решения игрушечного примера, где есть 2 ведра, каждое из которых содержит 2 нграммы. Без ограничения (2) решение состоит во 2-й нграмме сегмента 0 (значение = 3) и 1-й нграме блока 1 (значение = 2), следовательно, общее значение равно 5. Однако эти нграммы перекрываются, поэтому с ограничением (2) решение состоит во 2-й нграмме сегмента 0 (значение = 3) и 2-й нграмме сегмента 1 (значение = 1), а общее значение равно 4. Этот код находит решение без ограничения (2), но если я раскомментирую строку model.AddNoOverlap(intervals) чтобы добавить ограничение (2), статус решателя становится НЕОБХОДИМЫМ (т. е. нет решения), и я не понимаю, почему. Может кто-нибудь сказать мне, где я иду не так? А может мне нужен другой подход к этой проблеме? Заранее спасибо! 

import collections

from ortools.sat.python import cp_model


# Create the model.
model = cp_model.CpModel()

# Create variables to represent ngrams in model.
buckets = range(2)
ngram_indexes_per_bucket = range(2)

interval_bucket0_ngram0 = model.NewOptionalIntervalVar(0, 1, 1, True, 'interval_bucket0_ngram0')
interval_bucket0_ngram1 = model.NewOptionalIntervalVar(0, 2, 2, True, 'interval_bucket0_ngram1')
interval_bucket1_ngram0 = model.NewOptionalIntervalVar(1, 2, 3, True, 'interval_bucket1_ngram0')
interval_bucket1_ngram1 = model.NewOptionalIntervalVar(2, 1, 3, True, 'interval_bucket1_ngram1')

all_ngrams = {}  # key = (bucket, ngram index); value = interval var and bool var.
ngram = collections.namedtuple('ngram', 'interval is_selected')
all_ngrams[(0, 0)] = ngram(interval=interval_bucket0_ngram0, is_selected=model.NewBoolVar('interval_bucket0_ngram0'))
all_ngrams[(0, 1)] = ngram(interval=interval_bucket0_ngram1, is_selected=model.NewBoolVar('interval_bucket0_ngram1'))
all_ngrams[(1, 0)] = ngram(interval=interval_bucket1_ngram0, is_selected=model.NewBoolVar('interval_bucket1_ngram0'))
all_ngrams[(1, 1)] = ngram(interval=interval_bucket1_ngram1, is_selected=model.NewBoolVar('interval_bucket1_ngram1'))

# Maximize total value: values[bucket][n_gram index].
values = [[1, 3],
          [2, 1]]
model.Maximize(sum(values[bucket][i] * all_ngrams[(bucket, i)].is_selected
                   for bucket in buckets for i in ngram_indexes_per_bucket))

# Constraint (1): select 1 ngram from each bucket.
for bucket in buckets:
    model.Add(sum(all_ngrams[(bucket, i)].is_selected for i in ngram_indexes_per_bucket) == 1)

# Constraint (2): selected ngrams cannot be overlapping.
intervals = [all_ngrams[(0, 0)].interval, all_ngrams[(0, 1)].interval, all_ngrams[(1, 0)].interval,
             all_ngrams[(1, 1)].interval]
#model.AddNoOverlap(intervals)

# Solve.
solver = cp_model.CpSolver()
status = solver.Solve(model)
print(solver.StatusName(status))
print('Optimal value: %i' % solver.ObjectiveValue())

# Write out solution.
for bucket in buckets:
    for i in ngram_indexes_per_bucket:
        print("bucket = {0}; ngram index = {1}".format(bucket, i))
        if solver.Value(all_ngrams[(bucket, i)].is_selected):
            print("Selected!")
        else:
            print("Not selected!")
...