Сравнивая результаты lpSolve с linprog, есть ли проблема в реализации?

Я хотел бы минимизировать систему линейного программирования с линейными ограничениями «равенства».

Система обобщена в следующем коде «Python 3».

>>> obj_func = [1,1,1]
>>> const = [[[1, 0, 0], [0, 1, 0], [0, 0, 1], [1, 1, 1]]]
>>> constraints= np.reshape(const, (-1, 3))
>>> constraints
array([[1, 0, 0],
       [0, 1, 0],
       [0, 0, 1],
       [1, 1, 1]])
>>> rhs = [0.4498162176582741, 0.4498162176582741, 0.10036756468345168, 1.0]

Использование scipy.optimization.linprg:

   >>> res = linprog(obj_func, constraints, rhs, method="interior-point", options={"disp":True})
>>> res
     con: array([], dtype=float64)
     fun: 1.4722956444515663e-09
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([0.44981622, 0.44981622, 0.10036756, 1.        ])
  status: 0
 success: True
       x: array([4.34463075e-10, 4.34463075e-10, 6.03369494e-10])

Та же система, обобщенная в R и свернутая с помощью lpSolve:

> obj.func = c(1,1,1)
> constraints = matrix(c(1,0,0,0,1,0,0,0,1,1,1,1), nrow= 4, byrow = TRUE)
> rhs = c(0.4498162+0i, 0.4498162+0i, 0.1003676+0i, 1.0000000+0i)
> f.dir = c("=","=","=","=")
>
> res = lp("min",obj.func,constraints,f.dir,rhs,compute.sens=FALSE)
> res
Success: the objective function is 1

Как подробно описано выше, результаты не близки друг к другу, хотя это одна и та же система, поэтому я проделал ту же работу для других систем, но результаты также далеки.

Мой вопрос: я знаю, что не обязательно, чтобы каждый LP имел уникальное решение, но я думаю, что они должны давать близкие значения! В моем случае я пытался минимизировать многие системы, используя оба решателя, но результаты слишком далеки. Например,

First system: linprog gave 1.4722956444515663e-09 while lpSolve gave 1
Another system: linprog gave 1.65952852061376e-11 while lpSolve gave 0.8996324
Another system: linprog gave 3.05146726445553e-12 while lpSolve gave 0.8175745

python-3.x r scipy linear-programming lpsolve
person Noah16    schedule 19.03.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы решаете разные модели.

res = linprog(obj_func, constraints, rhs, method="interior-point", options={"disp":True})

означает

res = linprog(obj_func, A_ub=constraints, b_ub=rhs, method="interior-point", options={"disp":True})

действует в ограничениях:

x0 <= 0.4498162176582741
...

вместо

x0 == 0.4498162176582741

Итак, linprog использует только неравенства, в то время как lpsolve использует только равенства (без моей проверки, делает ли f.dir = c("=","=","=","=") то, что я думаю, но результат показывает это более или менее).

Линпрог-результат:

x: array([4.34463075e-10, 4.34463075e-10, 6.03369494e-10])

является типичным выводом нулевого вектора метода внутренней точки (только аппроксимирует интегральные решения)! В отличие от коммерческих решателей, таких как Gurobi, переходного шага нет.

Будьте внимательны при чтении документов. (которые содержат эту информацию).

person sascha    schedule 19.03.2019