使用python中的不同求解器优化线性系统的不同结果

问题描述 投票:0回答:1

我有一个从成对网络派生的线性系统,我想在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_solvelpsolve55,但结果与scipy.optimize.linprog()中的LpSolveR产生的结果不同!

这是使用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_solvelp_maker对大型系统更好吗?或者我是否需要换另一个求解器?

python optimization scipy linear-programming lpsolve
1个回答
0
投票

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.
© www.soinside.com 2019 - 2024. All rights reserved.