Различные результаты оптимизации линейной системы с использованием разных решателей в Python - PullRequest
Новая
       15

Различные результаты оптимизации линейной системы с использованием разных решателей в Python

0 голосов
/ 29 марта 2019

У меня есть линейная система, полученная из сети пар, и я хотел бы оптимизировать минимум с помощью решателя в 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 лучше для больших систем?или мне нужно поменять на другой решатель?

1 Ответ

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

Сципи минимизирует вашу цель. 

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 максимизирует цель. 

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.
...