Можно ли в CVXPY задать ограничение функцией?

Моя задача - найти минимальное остовное дерево графа. Проверить, что граф все еще связен можно, высчитав любое алгебраическое дополнение для матрицы Кирхгофа, построенной на моем графе с учетом всех вершин и тех ребер, которые я выбрала.

Я использую библиотеку CVXPY и она распознает мою задачу как MIP. Вот так я прописываю решение:

# вектор весов:
W = vector_of_weights(list_of_edges)

# искомый вектор x (набор ребер в остовном дереве)
x = cvxpy.Variable(len(edges), boolean=True)

# ограничение
constraint = kirhgof_matrix_al_complement(list_of_edges, list_of_vertexes, x) >= 2

# функционал
functional = W * x

# постановка задачи
problem = cvxpy.Problem(cvxpy.Minimize(functional), [constraint])

# решение
problem.solve(solver=cvxpy.GLPK_MI)
print(x.value)

Как видите, я задаю вектор весов функцией vector_of_weights() и CVXPY нормально с таким работает (он корректно считает решение при задании другого ограничения)

Проблемы начинаются, когда я задаю ограничение constraint = kirhgof_matrix_al_complement(list_of_edges, list_of_vertexes, x) >= 2

Вот что представляет из себя функция kirhgof_matrix_al_complement():

def kirhgof_matrix_al_complement(list_of_edges, list_of_vertexes, x):
    # ребра в иксе:
    current_edges = list_of_edges[np.array(list(map(bool, x)))]
    # матрица инцидентности:
    I = np.zeros((len(list_of_vertexes), len(current_edges)))
    for i in range(len(list_of_vertexes)):
        for j in range(len(current_edges)):
            if list_of_vertexes[i] == current_edges[j].sv:
                I[i][j] = 1
            elif list_of_vertexes[i] == current_edges[j].ev:
                I[i][j] = -1
    # матрица кирхгофа:
    K = I.dot(I.transpose())
    # алгебраическое дополнение элемента [0][0]
    K = np.delete(K, (0), axis=0)
    K = np.delete(K, (0), axis=1)
    al_complement = np.linalg.det(K)
    print(al_complement)
    return int(al_complement)

Программа не выдает ошибки, но в качестве оптимального решения я всегда получаю нули. Мой вопрос в том, ошиблась ли где-то я или же CVXPY просто не умеет работать с заданием ограничения в такой форме, в какой его задала я.

P.S. Я пробовала вызывать kirhgof_matrix_al_complement(), передав в нее икс из нулей и в ответ получила ноль, то есть ограничение не соблюдается.

0 ответов

Другие вопросы по тегам