CVXPY генерирует странный результат - PullRequest
Новая
       25

CVXPY генерирует странный результат

0 голосов
/ 30 апреля 2019

Вот простая задача оптимизации: 

import cvxpy as cp
import numpy as np

w = np.array([700, 700, 700, 700, 700, 700, 700, 700, 700, 700])
b = 7000
n = len(w)

# Define and solve the CVXPY problem.
x = cp.Variable(n, boolean=True)
prob = cp.Problem(cp.Minimize(w.T@x), [w.T@x >= b])
prob.solve()

# Print result.
print("\nThe optimal value is", prob.value)
print("A solution x is")
print(np.round(x.value))

Я хочу решить это как ILP и получить результат $ x \ in {0, 1} ^ n $.Довольно легко увидеть, что это просто даст x = [1,1,1,1,1,1,1,1,1,1] как оптимальное x и оптимальное значение как 7000, и это действительно то, что я получаю.Однако, если я добавлю [1800, 1800] так, что w = [700, 700, 700, 700, 700, 700, 700, 700, 700, 700, 1800, 1800], тогда оптимальное значение все равно должно быть приблизительно 7000 (все 700-е), но решатель дает 7100 и включает в себя два 1800-х.

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

...