Целочисленное линейное программирование с помощью CVXPY в python3 - PullRequest
Новая
       18

Целочисленное линейное программирование с помощью CVXPY в python3

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

Я пытаюсь решить задачу целочисленного линейного программирования с использованием CVXPY, но я борюсь с некоторым синтаксисом и не могу найти способ применения моей переменной, который мне интересно решить, чтобы ограничение принимало значения либо 0, либо 1. Я думал, что установка его на логическое значение было решением для объекта Variable, но по какой-то причине я не получаю то, что хочу

Я установил библиотеку cvxpy и попытался запустить ее, используя небольшой пример для ее решения. Вход для моей проблемы - это двоичная матрица размера M (I, J), которая имеет только значения (0 или 1), также переменная, для которой я хочу найти, является логическим (или снова двоичным вектором) вектором P размера J,

целевая функция состоит в том, чтобы минимизировать сумму значений моего вектора переменной размера J (т. Е. Минимизировать число 1с внутри этого вектора)

так, чтобы сумма каждой строки моей матрицы M умноженная на мою переменную Vector P была больше или равна 1 т.е. суммирование (по j) Mij * Pj> = 1, для всех i.

с целью минимизации суммы вектора P.

Я написал следующий код, чтобы сделать это, однако я изо всех сил пытаюсь найти, что я сделал в этом неправильно. 

import numpy as np
import cvxpy as cp

M = np.array([[1,0,0,0], [1,0,0,0], [0,1,1,0], [1,0,0,0], [0,0,1,1], [0,0,1,0]])

variable= cp.Variable(M.shape[1], value = 1, boolean=True)

one_vec = np.ones(M.shape[1])

obj = cp.Minimize(sum(np.dot(variable, one_vec)))

constraints = []

for i in range(len(M)):
    constraints.append(np.sum(np.dot(M[i], variable)) >= 1)

problem = cp.Problem(obj, constraints=constraints)

problem.solve()

так что в качестве ответа на этот простой пример, данный матрицей M в моем коде, ответ должен быть таким, чтобы значение вектора переменной было [1, 0, 1, 0], так как вектор умножается [1, 0, 1, 0] с матрицей

[[1, 0, 0, 0]

[1, 0, 0, 0]

[0, 1, 1, 0]

[1, 0, 0, 0]

[0, 0, 1, 1]

[0, 0, 1, 0] ]

даст значение по крайней мере 1 для каждой строки.

Но если я запускаю этот код, который я написал, в качестве ответа я получаю значение с плавающей точкой, следовательно, я делаю что-то не так, что не могу понять. Я не знаю, как сформулировать этот вопрос программно, я думаю, чтобы решатель решил его. Любая помощь будет принята с благодарностью. Спасибо.

1 Ответ

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

UPDATE! Я думаю, я понял это

Я изменил код так: 

import numpy as np
import cvxpy as cp

M = np.array([[1,0,0,1], [1,0,0,1], [0,1,1,1], [1,0,0,1], [0,0,1,1], [0,0,1,1]])

selection = cp.Variable(M.shape[1], boolean = True)
ones_vec = np.ones(M.shape[1])

constraints = []
for i in range(len(M)):
    constraints.append(M[i] * selection >= 1)

total_genomes = ones_vec * selection

problem = cp.Problem(cp.Minimize(total_genomes), constraints)

problem.solve()

и теперь работает. Я использовал оператор * вместо продукта numpy dot, cvxpy перегружен этим оператором, который, я думаю, выполняет умножение вектора.

...