在当今信息时代，优化问题已经渗透到各个领域，从供应链管理到人工智能，从交通规划到金融分析。在这个广泛应用的背后，有一种强大的数学工具正在默默发挥着关键作用 - Gurobi。Gurobi是一款高性能数学规划求解器，专注于线性规划、整数规划、二次规划和混合整数二次规划等优化问题。它是由Gurobi Optimization公司开发的，拥有超过30年的研究和开发经验。
Gurobi 不仅仅是一个求解器，它是一个全面的优化工具包，提供了丰富的API，可用于多种编程语言，包括Python、C++、Java和.NET。这使得它非常适合将优化引入各种应用中。
虽然用基础的 Python数据结构也能实现 Gurobi的建模,但在建模过程中,经常要对带不同下标的数据进行组合,如果使用 Python 内置的数据结构,则效率会比较低,为了提高建模效率,Gurobi封装了更高级的 Python 数据结构,即 Mutidict,Tuplelist Tupledict。在对复杂或大规模问题建模时,它们可以大大提高模型求解的效率。
一、 Multidict
Multidict,即复合字典,就是多重字典的意思,multidict 函数允许在一个语句中初始化一个或多个字典,如现在有多个学生的语文、数学、英语成绩,如果每门成绩都用一个字典来存储,那么3门课的成绩就需要3个字典,在编写代码时就需要重复录人学生的姓名,如果使用 multidict 函数则只需要输人一遍学生的姓名,其后面跟学生的成绩,就可以一次性定义多个需要的字典,并且这些字典的键都是相同的,如代码所示。
import gurobipy as grb
# mutidict 用法
student, chinese, math, english = grb.multidict({
'student1': [1, 2, 3],
'student2': [2, 3, 4],
'student3': [3, 4, 5],
'student4': [4, 5, 6]
})
print(student) # 字典的键
# 输出
# ['student1', 'student2', 'student3', 'student4']
print(chinese) # 语文成绩的字典
# 输出
# {'student1': 1, 'student2': 2, 'student3': 3, 'student4': 4}
print(math) # 数学成绩的字典
# 输出
# {'student1': 2, 'student2': 3, 'student3': 4, 'student4': 5}
print(english) # 英语成绩的字典
# 输出
# {'student1': 3, 'student2': 4, 'student3': 5, 'student4': 6}
二、Tuplelist
Tuplelist,即元组列表,就是tuple和list的组合,也就是 list元素的tuple类型,其设计目的是为了高效地在元组列表中构建子列表,如可以使用tuplelist 对象的 seleet 方法进行检索,如与特定字段中的一个或多个指定值匹配的所有元组,这个操作有点像SOL里面的 seleet-where 操作。如代码所示。
import gurobipy as grb
# 创建tuplelist对象
tl = grb.tuplelist([(1, 2), (1, 3), (2, 3), (2, 5)])
# 取出第一个值是1的元素
print(tl.select(1, '*'))
# 输出
# <gurobi.tuplelist (2 tuples, 2 values each):
# ( 1 , 2 )
# ( 1 , 3 )
# 取出第二个值是3的元素
print(tl.select('*', 3))
# 输出
# <gurobi.tuplelist (2 tuples, 2 values each):
# ( 1 , 3 )
# ( 2 , 3 )
Tuplelist 继承自list,所以向tuplelist 中添加新元素和普通list 添加元素一样,有append、pop 等方法,同样用迭代的方式遍历元素,如代码所示。
# 添加一个元素
tl.append((3, 5))
print(tl.select(3, '*'))
# 输出 <gurobi.tuplelist (1 tuples, 2 values each):
# ( 3 , 5 )
# 使用迭代的方式实现select功能
print(tl.select(1, '*'))
# 输出 <gurobi.tuplelist (2 tuples, 2 values each):
# ( 1 , 2 )
# ( 1 , 3 )
# 对应的迭代语法是这样的
print([(x, y) for x, y in tl if x == 1])
从上面的代码可以看出,其实 tuplelist在内部存储上和普通的list是一样的只是 Gurobi 在继承list类的基础上添加了select 方法。因此,可以把 tuplelist看作是list 对象,可以使用选代、添加或删除元素等方法。
三、Tupledict
Tupledict 是 Python 的 dict 的一个子类,通过 tupledict 可以更加高效地操作 Gurobi中的变量子集也就是说当定义了很多变量,需要对其中一部分变量进行操作时,可以使用 tupledict 的内置方法来高效轻松地构建线性表达式,如 sum 和 prod。tupledict 的键在内部存储格式是 tuplelist,因此可以使用tu-plelist的 select 方法选择集合的子集。在实际使用中,通过将元组与每个 Gurobi变量关联起来,可以有效地创建包含匹配变量子集的表达式
如创建一个3x 3 的矩阵,里面的每个元素表示线性表达式的变量,取其中一部分变量的操作就显得很方便了。对如下矩阵进行代码演示,其方法如代码所示。
import gurobipy as grb
model = grb.Model()
# 定义变量的下标
tl = [(1, 1), (1, 2), (1, 3),
(2, 1), (2, 2), (2, 3),
(3, 1), (3, 2), (3, 3)]
vars = model.addVars(tl, name="d")
# 基于元素下标的操作
print(sum(vars.select(1, '*')))
# 输出
# <gurobi.LinExpr: d[1,1] + d[1,2] + d[1,3]>
相当于对第1行求和,即x11 +x12 +x13 。另一种效果相同但写法更快捷的代码如下。
vars.sum(1，'*')
在上面的例子中讨论的情况是变量的系数都是1时,如果变量系数不是 1,就不能用sum 方法,而需要用prod 方法来构建线性表达式prod方法用于变量和系数相乘后的累加。首先创建一个系数矩阵,用tupledict 存储,键与vars 是一样的,这样就可以快速匹配系数和对应的变量,然后采用prod方法用选定的变量和系数来构建线性表达式,如代码 所示。
import gurobipy as grb
# import math
# 创建一个系数矩阵，用tuplelist格式存储
c1 = [(1, 1), (1, 2), (1, 3)]
coeff = grb.tupledict(c1)
coeff[(1, 1)] = 1
coeff[(1, 2)] = 0.3
coeff[(1, 3)] = 0.4
print(vars.prod(coeff, 1, '*'))
# 输出
# <gurobi.LinExpr: d[1,1] + 0.3 d[1,2] + 0.4 d[1,3]>
如果不是选择部分变量而是选择全部变量,prod 函数实现的功能就是具有相同下标的变量相乘后加和。在下面的例子中,用迭代表达式与 prod方法实现的功能是一样的。
obj= grb.quicksum(cost[i,j]* x[i,j] for i,j in arcs)
obj= m x.prod(cost)
由于tupledict是 dict 的子类,因此可以使用标准的 dict方法来修改 tupledict,如上面的代码中，直接对tupledict的某个键进行赋值操作。
Gurobi变量一般都是tupledict 类型,用tupledict 定义变量的好处是可以快速选择部分变量，创建各种各样的约束因为tupledict有sum函数和select函数,如代码的演示。
# tupledict类型的变量快速创建约束条件
import gurobipy as grb
m = grb.Model()
x = m.addVars(3, 4, vtype=grb.GRB.BINARY, name="x")
m.addConstrs((x.sum(i, '*') <= 1 for i in range(3)), name="con")
m.update()
m.write("tupledict_vars.lp")
# 将会创建如下的约束：
# con[0]: x[0, 0] + x[0, 1] + x[0, 2] + x[0, 3] <= 1
# con[1]: x[1, 0] + x[1, 1] + x[1, 2] + x[1, 3] <= 1
# con[2]: x[2, 0] + x[2, 1] + x[2, 2] + x[2, 3] <= 1
四、应用范例
下面通过一个网络流的例子来讲解 Multidiet,Tuplelist,Tupledict在优化建模问题中的应用，这个例子可以在 Gurobi安装目录下的example中找到。
在这个网络流的例子中,有两个城市(底特律和丹佛)生产了两种商品(铅笔和钢笔),必须装运到3个城市(波士顿、纽约和西雅图)的仓库,以满足给定的需求。网络中每一条弧都有其总容量和成本,如代码所示。
import gurobipy as grb
# 两种商品
commodities = ['Pencils', 'Pens']
# 2个产地+3个目的地
nodes = ['Detroit', 'Denver', 'Boston', 'New York', 'Seattle']
# 网络中每条弧的容量，使用multidict一次性创建多个字典
arcs, capacity = grb.multidict({
('Detroit', 'Boston'): 100,
('Detroit', 'New York'): 80,
('Detroit', 'Seattle'): 120,
('Denver', 'Boston'): 120,
('Denver', 'New York'): 120,
('Denver', 'Seattle'): 120})
# 商品在不同弧上的运输成本，是tupledict形式，可以用select，sum等加快变量选取
cost = {
('Pencils', 'Detroit', 'Boston'): 10,
('Pencils', 'Detroit', 'New York'): 20,
('Pencils', 'Detroit', 'Seattle'): 60,
('Pencils', 'Denver', 'Boston'): 40,
('Pencils', 'Denver', 'New York'): 40,
('Pencils', 'Denver', 'Seattle'): 30,
('Pens', 'Detroit', 'Boston'): 20,
('Pens', 'Detroit', 'New York'): 20,
('Pens', 'Detroit', 'Seattle'): 80,
('Pens', 'Denver', 'Boston'): 60,
('Pens', 'Denver', 'New York'): 70,
('Pens', 'Denver', 'Seattle'): 30}
# 商品在不同节点的流入流出，即需求量
# 正数表示产地，负数表示需求量
# 是tupledict形式，可以用select，sum等加快变量选取
inflow = {
('Pencils', 'Detroit'): 50,
('Pencils', 'Denver'): 60,
('Pencils', 'Boston'): -50,
('Pencils', 'New York'): -50,
('Pencils', 'Seattle'): -10,
('Pens', 'Detroit'): 60,
('Pens', 'Denver'): 40,
('Pens', 'Boston'): -40,
('Pens', 'New York'): -30,
('Pens', 'Seattle'): -30}
# 创建模型
m = grb.Model('netflow')
# 创建变量
# flow是tupledict类型的变量，因此可以使用select方法快速筛选
# 键是 ('Pencils', 'Detroit', 'Boston') 格式，可以使用select方法快速筛选，然后出选出来的变量sum求和
# 值是 cost，表示商品从产地到目的地的需求量
# 值还有系数，就是cost
flow = m.addVars(commodities, arcs, obj=cost, name="flow")
# 添加容量约束，使用到了迭代表达式
# 此处迭代中，i是产地，j是目的地
# capacity[i,j] 表示i->j的弧的容量
# flow.sum('*',i,j) 从i->j的所有不同商品的总量求和
m.addConstrs((flow.sum('*', i, j) <= capacity[i, j] for i, j in arcs), "cap")
# 添加节点的流入=流出的约束
# h表示商品， j表示节点包括产地和目的地
# flow.sum(h,'*',j) 表示商品h经过所有所有中间节点到达j后的总数量
# flow.sum(h,j,'*') 表示商品h从j节点流出去的数量
# inflow[h,j] 表示h在j节点的需求量
# 理解起来就是：
# 商品h在节点j，流入-流出 = 需求
# 流出可以表示产地，也可以表示中转节点
m.addConstrs((flow.sum(h, '*', j) + inflow[h, j] == flow.sum(h, j, '*') for h in commodities for j in nodes), "node")
# 求解模型
m.optimize()
# 打印结果
if m.status == grb.GRB.Status.OPTIMAL:
solution = m.getAttr('x', flow)
for h in commodities:
print('
Optimal flows for %s:' % h)
for i, j in arcs:
if solution[h, i, j] > 0:
print('%s -> %s: %g' % (i, j, solution[h, i, j]))
# 求解结果如下：
# Optimal flows for Pencils:
# Detroit -> Boston: 50
# Denver -> New York: 50
# Denver -> Seattle: 10
#
# Optimal flows for Pens:
# Detroit -> Boston: 30
# Detroit -> New York: 30
# Denver -> Boston: 10
# Denver -> Seattle: 30
在上面的代码中定义了一个运输网络,包括工厂生产的产品,目的地对产品的需求量、网络的最大运输量,以及单位运输成本。这是一个网络流优化的问题，网络流求解的核心是,起始点的输出量和终点的输入量相等,网络中各节点的输入量和输出量相等。
从上面的例子中,就能很好地理解 multidil 如何快速创建多个字典变量,upedict 如何表示模型的变量,tuplelist 作为 diet 的键如何发挥快速选择部分变量的作用，同时看到用集合选代的方式创建约束可以使代码变得简洁,且更容易维护。相信通过这个例子,读者能对Gurobi的基础数据结构有更深入的理解。
上一条：Gurobi 11.0发布，全局精确非线性优化同样出色
下一条：Gurobi-第二章Gurobi常用参数
沪公网安备31011302006932号