python - 在Python中使用多进程构建Gurobi表达式

Question

首先，我正在使用 jupyter-notebook、python 版本 3.5 和带有 python 界面的 Gurobi 7.0.2，所有这些都在 Red Hat 上进行。

这是我的问题的背景:我想解决一个二次问题，它有大量的变量。构建目标函数需要 1-2 个小时以上。

我考虑过使用 NumPy GPU 加速，但表达式有点棘手，所以这不是一个解决方案。

因此，我尝试使用多个线程构建目标函数。但是，我收到一个错误，我不知道如何处理它。

我简化了我的代码，因此它更具可读性(错误仍然相同)。

from gurobipy import *
import multiprocessing as mp
import queue
mp.set_start_method('fork')

def function(obj,q):

    print('We enter')
    obj = x*x + x*y + y*y + y*z + z*z + 2*x
    q.put(obj)
    print('We end')

m = Model("qp")
obj = QuadExpr()

x = m.addVar(ub=1.0, name="x")
y = m.addVar(ub=1.0, name="y")
z = m.addVar(ub=1.0, name="z")
q = mp.Queue()
if __name__ == '__main__':
    for k in range (4): 
        p = mp.Process(target=function, args=(obj,q,))
        p.start()
        obj+=q.get()
        p.join()
m.setObjective(obj)

# Add constraint: x + 2 y + 3 z <= 4
m.addConstr(x + 2 * y + 3 * z >= 4, "c0")

# Add constraint: x + y >= 1
m.addConstr(x + y >= 1, "c1")

m.optimize()

for v in m.getVars():
    print('%s %g' % (v.varName, v.x))

print('Obj: %g' % obj.getValue())

输出:

We enter
We end

---------------------------------------------------------------------------
GurobiError                               Traceback (most recent call last)
<ipython-input-31-c71f0667f39b> in <module>()
     17         p = mp.Process(target=function, args=(obj,q,))
     18         p.start()
---> 19         obj+=q.get()
     20         p.join()
     21 m.setObjective(obj)

quadexpr.pxi in gurobipy.QuadExpr.__iadd__ (../../src/python/gurobipy.c:39916)()

quadexpr.pxi in gurobipy.QuadExpr.add (../../src/python/gurobipy.c:35739)()

linexpr.pxi in gurobipy.LinExpr.add (../../src/python/gurobipy.c:29245)()

GurobiError: Unsupported type (<class 'NoneType'>) for LinExpr addition argument

我从这个帖子中猜想https://groups.google.com/forum/#!topic/gurobi/fwLRrWLLJqo ，这与腌制我从队列中输出的 gurobi 表达式有关，但我不太确定。

你知道我该如何解决这个问题吗？有没有其他方法可以从可以在这里工作的过程中“返回”结果？我想避免写入磁盘，因为它很慢(可能是最后一个资源:S)。

提前谢谢您:)。

P.D.我的代码中最慢的部分是这个，我尝试将其拆分为多个进程:

# var is an array of GRB.BINARY
# D=edge_costs
def penalty_function(var,obj,D):
    num_nodes = len(var)
    for i,fil in enumerate(D):
        for j,val in enumerate(fil):
            # -x*D*x
            if val!=0:
                obj+=var[i]*var[j]*val
            # -x(i)x(j)*min(Ds)
            if(j>i):
                for k in range(num_nodes):
                    if(not j==i):
                    minval=min(D[j][k],D[i][k])
                        if (minval!=0 ):
                            obj+=var[i]*var[j]*minval
    return obj

Answer 1

首先，Gurobi Optimizer 不支持多线程模型构建。即使我们这样做了，模型构建也几乎永远不会成为正确编写应用程序的瓶颈。

在本例中，您有很多类似于 x + x + x 的表达式。虽然正确，但效率非常低 - 最好写 3*x。这是对penalty_function的快速重写:

# var is an array of GRB.BINARY
# D=edge_costs
def penalty_function(var,obj,D):
    num_nodes = len(var)
    for i,fil in enumerate(D):
        for j,val in enumerate(fil):
            # -x*D*x
            if val!=0:
                obj+=var[i]*var[j]*val
            # -x(i)x(j)*min(Ds)
            if(j>i):
                minval = sum(min(D[j][k],D[i][k]) for k in range(num_nodes))
                if minval != 0:
                    obj += var[i]*var[j]*minval
    return obj

针对 Erwin Kavelagen 提出的问题，一个快速解决方法是 set PreQLinearize=1 .

编辑:我们可以通过组合两个 var[i]*var[j] 项来使penalty_function稍微更有效:

def penalty_function(var,obj,D):
    num_nodes = len(var)
    for i,fil in enumerate(D):
        for j,val in enumerate(fil):
            # -x(i)x(j)*min(Ds)
            if(j>i):
                val += sum(min(D[j][k],D[i][k]) for k in range(num_nodes))
            # -x*D*x
            if val!=0:
                obj += var[i]*var[j]*val
    return obj