我有一个从成对网络派生的线性系统,我想在python中使用求解器优化最小值。通过以下数据总结了从小型网络派生的该系统的示例
obj_func
{('1', '2'): [1, 1, 1],
('2', '3'): [1, 1, 1, 2, 1, 0],
('2', '4'): [1, 1, 1, 2, 0, 1],
('3', '4'): [0, 1, 1, 1]}
rhs
{('1', '2'): [0.3333487586477922, 0.3333487586477922, 0.3333024827044157, 1.0],
('2', '3'): [0.5, 0.5, 0.3333487586477922, 0.3333487586477922, 0.3333024827044157],
('2', '4'): [0.49996529223940045, 0.5000347077605996, 0.3333487586477922, 0.3333487586477922, 0.3333024827044157],
('3', '4'): [0.49996529223940045, 0.5000347077605996, 0.5, 0.5]}
constraints
defaultdict(<class 'list'>,
{('1', '2'): [[[1, 0, 0], [0, 1, 0], [0, 0, 1], [1, 1, 1]]],
('2', '3'): [[[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]]],
('2', '4'): [[[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]]],
('3', '4'): [[[1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 0], [0, 1, 0, 1]]]})
以前,我在lpSolve中使用R
进行了优化,但出于编程原因,我改为python3
并且使用了Scipy.optimize.linprog()。现在我使用来自lp_solve的lpsolve55
,但结果与scipy.optimize.linprog()
中的LpSolve
和R
产生的结果不同!
这是使用scipy.optimize.linprog()
的代码
from scipy.optimize import linprog
min_for_pairs = []
for pair in list(network.edges()):
A = np.reshape(constraints[pair], (-1, len(obj_func[pair])))
res = linprog(obj_func[pair], A_eq=A, b_eq=rhs[pair], method='interior-point', options={'presolve': True})
min_for_pairs.append(res.fun)
min_for_pairs
[1.0, 0.6666975173156104, 0.666651241372254, 0.5000347083535648]
这个使用lp_solve
:
from lpsolve55 import *
from lp_maker import *
from lp_solve import *
min_for_pairs = []
for pair in list(network.edges()):
A = np.reshape(constraints[pair], (-1, len(obj_func[pair])))
sense_equality = [0] * len(A)
lp = lp_maker(obj_func[pair], A , rhs[pair], sense_equality)
solvestat = lpsolve('solve', lp)
obj = lpsolve('get_objective', lp)
min_for_pairs.append(obj)
min_for_pairs
[1.0, 1.3333487586477921, 1.3333487586477921, 1.0]
我想知道 :
1)我的代码有什么问题,以便得到不同的结果?这是正常的,因为lp_solve
找不到最佳?
2)我从scipy(到lpsolve55)改变了,因为在大型网络上工作时速度太慢了。例如,我使用scipy
来获得一个目标函数的最小值,该函数来自一个小于16000对的小型网络,耗时超过6小时!一般来说,lp_solve
和lp_maker
对大型系统更好吗?或者我是否需要换另一个求解器?
scipy is minimizing你的目标。
Whereas the top level linprog module expects a problem of form:
Minimize:
c @ x
Subject to:
A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub
where lb = 0 and ub = None unless set in bounds.
但lp_maker maximizes的目标。
lp_maker.py
This script is analog to the lp_solve script and also uses the API to create a higher-level function called lp_maker. This function accepts as arguments some matrices and options to create an lp model. Note that this scripts only creates a model and returns a handle. Type help(lp_maker) or just lp_maker() to see its usage:
LP_MAKER Makes mixed integer linear programming problems.
SYNOPSIS: lp_handle = lp_maker(f,a,b,e,vlb,vub,xint,scalemode,setminim)
make the MILP problem
max v = f'*x
a*x <> b
vlb <= x <= vub
x(int) are integer
ARGUMENTS: The first four arguments are required:
f: n vector of coefficients for a linear objective function.
a: m by n matrix representing linear constraints.
b: m vector of right sides for the inequality constraints.
e: m vector that determines the sense of the inequalities:
e(i) < 0 ==> Less Than
e(i) = 0 ==> Equals
e(i) > 0 ==> Greater Than
vlb: n vector of non-negative lower bounds. If empty or omitted,
then the lower bounds are set to zero.
vub: n vector of upper bounds. May be omitted or empty.
xint: vector of integer variables. May be omitted or empty.
scalemode: Autoscale flag. Off when 0 or omitted.
setminim: Set maximum lp when this flag equals 0 or omitted.
OUTPUT: lp_handle is an integer handle to the lp created.