Как ограничить количество нулей в программировании с ограничениями

Для заданных n и m я перебираю все n по m частичных циркулянтных матриц с записями, которые либо 0 или 1. Я хочу найти, существует ли матрица, в которой нет двух подмножеств столбцов с одинаковой суммой. Здесь, когда мы добавляем столбцы, мы просто делаем это поэлементно. В моем текущем коде используется программирование с ограничениями через или инструменты. Вот мой код.

from scipy.linalg import circulant
import numpy as np
import itertools
from ortools.constraint_solver import pywrapcp as cs

n = 4
m = 6

def isdetecting(matrix):
    solver = cs.Solver("scip")
    X = np.array([solver.IntVar(values) for i in range(matrix.shape[1])])
    X1 = X.tolist()
    for row in matrix:
        x = X[row].tolist()
        solver.Add(solver.Sum(x) == 0)
    db = solver.Phase(X1, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_CENTER_VALUE)
    solver.NewSearch(db)
    count = 0
#Find just one non-zero solution if there is one
    while (solver.NextSolution() and count < 2):
        solution = [x.Value() for x in X1]
        count += 1
    solver.EndSearch()
    if (count == 1):
        return True

values = [-1,0,1]
nosols = 0
for row in itertools.product([0,1],repeat = m):
    M = np.array(circulant(row)[0:n], dtype=bool)
    if isdetecting(M):
        nosols += 1
        print M.astype(int)

Строка values = [-1,0,1] допускает любое количество нулей в решениях. Как вместо этого указать точное количество нулей, разрешенных в решении?


python math constraint-programming integer-programming
person eleanora    schedule 10.03.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

В or-tools/Python есть глобальный решатель ограничений.Count(), который можно использовать. Пример:

 the_count = 1 # number of 0's allowed
 solver.Add(solver.Count(X1, 0,the_count))

Где «the_count» — это количество нулей, которое можно разрешить в (плоском) массиве «X1». the_count может быть либо константой, либо переменной решения (так что вы можете ограничить это значение дополнительными ограничениями или просто позволить доменам выполнять работу по ограничению количества, например, домен 1..4 ограничивает количество от 1 до 4 вхождений ).

«X1» — это массив переменных решения, которые проверяются. Второй параметр, «0», — это значение для подсчета в X.

Пример использования Solver.Count(): http://hakank.org/or-tools/young_tableaux.py .

Существует также обобщение Solver.Count(), а именно Solver.Distribute (он же Global Cardinality Count, GCC), где вы можете подсчитывать/ограничивать более одного значения одновременно. См. мою модель последовательности де Брейна для примера ее использования: http://hakank.org/or-tools/debruijn_binary.py .

person hakank    schedule 10.03.2014