[Это связано с минимальной обложкой]
Я хотел бы решить следующую загадку компьютером для небольшого размера n. Рассмотрим все 2 ^ n двоичных векторов длины n. Для каждого из них вы удаляете ровно n/3 бит, оставляя двоичную длину вектора 2n/3 (предположим, n является целым числом, кратным 3). Цель состоит в том, чтобы выбрать биты, которые вы удаляете, чтобы свести к минимуму количество различных двоичных векторов длиной 2n/3, которые остаются в конце.
Например, для n = 3 оптимальным ответом являются 2 разных вектора 11 и 00. При n = 6 это 4, для n = 9 оно равно 6 и для n = 12 оно равно 10.
Ранее я пытался решить эту проблему как минимальную заданную проблему покрытия следующего вида. Все списки содержат только 1s и 0s.
Я говорю, что список A охватывает список B, если вы можете сделать B из A, вставив именно символы x.
Рассмотрим все 2 ^ n списки из 1s и 0s длины n и установите x = n/3. Я хотел бы вычислить минимальный набор списков длины 2n/3, который охватывает их все. Дэвид Эйзенстат предоставил код, который преобразовал эту проблему с минимальным набором обложек в задачу смешанного целочисленного программирования, которая может быть отправлена в CPLEX (или http://scip.zib.de/, которая с открытым исходным кодом).
from collections import defaultdict
from itertools import product, combinations
def all_fill(source, num):
output_len = (len(source) + num)
for where in combinations(range(output_len), len(source)):
poss = ([[0, 1]] * output_len)
for (w, s) in zip(where, source):
poss[w] = [s]
for tup in product(*poss):
(yield tup)
def variable_name(seq):
return ('x' + ''.join((str(s) for s in seq)))
n = 12
shortn = ((2 * n) // 3)
x = (n // 3)
all_seqs = list(product([0, 1], repeat=shortn))
hit_sets = defaultdict(set)
for seq in all_seqs:
for fill in all_fill(seq, x):
hit_sets[fill].add(seq)
print('Minimize')
print(' + '.join((variable_name(seq) for seq in all_seqs)))
print('Subject To')
for (fill, seqs) in hit_sets.items():
print(' + '.join((variable_name(seq) for seq in seqs)), '>=', 1)
print('Binary')
for seq in all_seqs:
print(variable_name(seq))
print('End')
Проблема в том, что если вы установите n = 15, то выведенный экземпляр слишком велик для любого решателя, который я могу найти. Существует ли более эффективный способ решения этой проблемы, поэтому я могу решить n = 15 или даже n = 18?
