Gurobi 基础语法之 tupledict 和 tuplelist

Python中的字典：dict

        我们先来介绍一下Python语法中的 dict 类型, 字典中可以通过任意键值来对数据进行映射，任何无法修改的python对象都可以当作键值来使用，这些无法修改的Python对象包括：整数(比如：1)，浮点数(比如：1.1)，字符串(比如："uyt")，元组。

        下面分别用整数和元组作为键值创建 dict 类型的变量

用整数作为键值创建 dict 类型的变量

int_dict = {1: 'one', 2: 'two', 3: 'three'}
print(int_dict)  # {1: 'one', 2: 'two', 3: 'three'}
print(int_dict[1])  # one

用元组作为键值创建 dict 类型的变量（此tuple_dict 非后面讲的 tupledict）

tuple_dict = {('a', 1): 'a_one', ('b', 2): 'b_two', ('c', 3): 'c_three'}
print(tuple_dict)  # {('a', 1): 'a_one', ('b', 2): 'b_two', ('c', 3): 'c_three'}
print(tuple_dict[('b', 2)])  # b_two

值得注意的是：

通过元组访问字典时可以省略圆括号，因此以下语句同样也是同样有效的：

print(tuple_dict['b', 2])  # b_two

        无论是python中的dict, 还是C++中的unordered_map，都是在用键值就能找到value，从功能上来讲，就可以把他们之中的键值当作一个下标来理解

        既然都有了dict，为什么Gurobi之中还创建了很多诸如multidict,  tupledict这样的东西？

Gurobi中的multidict

        首先，multidict 只是一个函数，往这个函数中传入一个 dict 字典，其中的每个键值对由键和一个列表构成，那么经过multidict处理之后将会很方便的得到多个字典，下面举个例子来说明将一个dict 分解成多个新的字典的过程，

keys, dict1, dict2 = gp.multidict( {
'key1': [1, 2],
'key2': [1, 3],
'key3': [1, 4] } )

这就将{ key1': [1, 2], key2': [1, 3], key3': [1, 4] } 这个字典分成了三个部分：

keys: 作为一个gurobi中专有的 tuplelist 类型的变量，实际上是['key1', 'key2', 'key3']

dict1: 作为一个gurobi中专有的 tupledict 类型的变量，实际上是{'key1': 1, 'key2': 1, 'key3': 1}

dict2: 作为一个gurobi中专有的 tupledict 类型的变量，实际上是{'key1': 2, 'key2': 3, 'key3': 4}

 那么multidict这个函数的作用就显而易见了：

在建模过程中，有可能遇到如下场景：有多个决策变量，每个决策变量都有上下界，那么这些决策变量可以用multidict快速的将一个决策变量和上下界都建立字典关系，比如对于上面的dict1 和 dict2来说，key1的上下界是1, 2，key2的上下界是1, 3，key3的上下界是1, 4

Gurobi 中的 tupledict 和 tuplelist

tupledict

        tupledict 是Python中 dict 的一个子类，tupledict 这个子类提供的新方法是 sum 和 prod  

tupledict 的定义：在gurobi中，用一个  tuple 作为字典中的key，如果字典中有多个键值对，则 这些 key（即元组）的长度都必须相同

tupledict 提供了 sum 和 prod 方法，可以方便地创建线性表达式，这些表达式可以直接用于构建模型的约束和目标函数。

Gurobi 中对 tupledict 对象调用 sum 方法

之所以 Gurobi 中要单独设计一个 sum 方法，这是因为 sum 方法有如下优点：

1. 支持部分求和与筛选：向gurobi 中的 sum 方法传入筛选参数，这些参数就将作为筛选元组的特定条件

2. 性能优化：Gurobi 中的 sum 方法进行了性能优化，使其在处理大规模数据时效率更高

        tupledict 中的 sum 方法的使用示例

m = Model()
x = m.addVars(2, 3) 
expr1 = x.sum()  # 创建一个包含所有变量的和的线性表达式
expr2 = x.sum(1, '*') 
expr3 = x.sum('*', 1)n = Model()
y = n.addVars(10, 10) 
expr4 = y.sum(range(1, 6), 1)

代码运行结果

对上面这段代码的解释：首先 x 调用 gurobi 中的 addVars 这个方法，能够获得一个 tupledict类型的对象，这个对象实际上是一个以两个下标组成的元组作为 tuplelist 的key，此时相当于创建了一个2行3列的变量矩阵，变量的下标从(1,1)到(2,3)

上图表明了x 这个变量矩阵的的是按照 tuplelist 的存储结构进行存储的，调用sum方法就是把这个变量矩阵中的每一个变量都相加，也就是说，创建了一个包含所有变量的和的线性表达式。具体来说，它将所有变量x11, x12, x13, x21, x22, x23相加。用数学公式表示为：

expr1 = x11 ​+ x12 ​+ x13 ​+ x21 ​+ x22​ + x23​

对于expr2 = x.sum(1, '*')   创建了一个包含第一行所有变量的和的线性表达式。具体来说，它将第一行的变量x11, x12, x13相加。用数学公式表示为： expr2 = x11​ + x12 ​+ x13​    

而expr3将第一列的变量x11, x21相加。用数学公式表示为：expr3 = x11 + x21

对于expr4来说，其获得了y这个变量矩阵的第一列的前 5 个变量线性表达式。用数学公式表示为：expr4 = y11 + y21 + y31 + y41 + y51

gurobi中对tupledict对象调用 prod 方法

下面用几个例子来说明这个方法：

例1：tupledict可以和dict类型的变量通过 prod 方法进行相乘

m = gp.Model()
x = m.addVars(2, 2)
coef = { (0, 0) : 0.3, (0, 1) : 0.5, (1, 0) : 0.1, (1, 1) : 0.7 }
# coef = { (0, 0) : 0.3, (0, 1) : 0.5, (1, 0) : 0.1} # 得到 0.3x11 + 0.5x12 + 0.1x21
# coef = { (1, 1) : 0.3, (1, 2) : 0.5, (2, 1) : 0.1} # 得到 0.3x22
expr = x.prod(coef)
print(expr)

        值得注意的是，在coef中只有与(0, 0)，(0, 1)，(1, 0)，(1, 1) 这四个元组匹配的键值对才会参与prod，prod之后的结果只有coef的第一个键值对

练习：阿山想要知道应该怎么学习什么技能才能成为一个运筹优化算法的专家，现在已知有三种技能是成为专家的必学技能，分别是python以及gurobi的编程技能，调研建模对象相关背景的能力，算法性能的测试技能，现在阿山要分配合理的时间，在尽可能短的时间内获得更高的技术水平，请你编写一段程序表达这个问题的目标函数

提示：既然 dict 都可以和 tupledict 使用 prod，那么tupledict 是否可以和 tupledict 相乘？

~

~

~

skill, time = multidict({'coding' : 4,'business' : 4,'test' : 1
})m = gp.Model()
x = m.addVars(skill, name = 'x')
expr = x.prod(time)
m.setObjective(expr, GRB.MINIMIZE)

注意：这里添加变量和 相乘都可以用其他的方法替代，具体可以看我的另外一篇博客

tuplelist

        tuplelist 是 Python中 list 的子类，tuplelist提供了一个新的方法：select

tuplelist 的定义：在gurobi中，用一个  tuple 作为列表中的元素，如果列表中有多个元素，则这些 元素（即元组）的长度都必须相同

tuplelist 提供了 select 方法，可以高效的筛选出符合条件的元组

tuplelist 中的 select 方法

        tuplelist 中的 select 方法的优点是快速查找，这一点将配合 Gurobi 中的其他方法发挥更大的作用，具体在后面进行讨论

        tuplelist 中的 select 方法的使用示例

        tuplelist 提供了select方法，select 方法为查找元素提供了一中条件筛选的方式，由于列表中的元组长度一致，所以可以理解成一个矩阵，那么select方法就可以通过指定对应位置处的元素取值，以下面这个例子为例：

Cities= [('A','B','C','D'), ('A','C','D','E'), ('B','C','B','C'),('B','D','B','C'),('C','A','B','C')]
Routes = tuplelist(Cities)
print(Routes.select('A','*'))
print(Routes.select('*','C', 'B'))

 将会打印出，select 方法的返回值会自动打印 搜索到的符合条件的元组有哪些，而且说明每个元组包含的元素个数，其返回值的类型是 tuplelist

        select 方法的进一步说明

        select 方法可以高效地筛选符合特定条件的元组(或称下标)，其底层的实现不是通过顺序遍历的方式进行查找的，在一群元素中查找某个特定元素的方案有很多，下面列举出几种方案，至于Gurobi 是否采用了这些方案，不在本文的研究范围之内。

        首先是合理的数据结构，合理的数据结构可以有效的加快查找的过程，这些数据结构包括但不限于哈希表，红黑树，

        其次是合理的算法，select 方法还可能采用了优化的筛选算法。当调用 select 方法时，Gurobi 会根据筛选条件直接定位到可能包含符合条件元组的区域，而不是对整个 tuplelist 进行遍历。

        select 的高效查找特性带来的优势

        在本文的前面介绍了multidict 函数，这个函数本质就是将一个key: [val1, val2]的键值对进行拆分，分别形成 tuplelist，tupledict1, tupledict2，在这样的场景中，如果要找到满足某个特定条件的key，可以 通过第一个 tuplelist 对象执行 select 方法，这样就可以快速的获得这个特定条件的 key 对应的 val

        代码示例：

categories, minNutrition, maxNutrition = multidict({'calories': [1800, GRB.INFINITY],'protein': [91, GRB.INFINITY],'fat': [0, GRB.INFINITY],'sodium': [0, GRB.INFINITY]})print(type(categories.select('fat')))
print(minNutrition[categories.select('protein')[0]])