在调用gurobi来求解TSP问题时，常常会用到懒惰约束，但由于API的不同，使用python和matlab这两种方式调用gurobi时会有很大差别。matlab通过yalmip工具包来调用gurobi，python通过gurobipy库来调用gurobi。这篇文章主要介绍这两种方式在求解时各方面的差异。
一、数据初始化
我们的算例文件，如berlin8.tsp、pr76.tsp、a280.tsp等，是以城市节点的二维坐标的形式，给出各城市两两之间的距离，因此，如果想要得到距离矩阵，是要通过计算的（二维欧氏距离）。
matlab使用了两个转化函数，将tsp文件中的关键信息存储到一个结构体中，这个结构体中包含了城市个数、距离矩阵等数据，用于后续计算，这两种数据都是以矩阵的形式参与运算。需要注意的是，这里将距离矩阵的对角线上的数字都设置为了M（即远大于其它距离的值，这里设置为了99999） ，是为了避免“自己到自己”的情况发生。
python可以使用load函数直接读取tsplib95库中包含的所有类型的文件（包括tsp类型的文件），因此获得文件中的关键信息比较方便，不需要自己再编写函数。城市id以列表的形式来参与运算，但城市两两之间的距离以字典的形式参与运算，键为由两个城市id组成的元组，值为两城市间的距离。需要注意的是，由于combinations函数的使用，字典中不包含原距离矩阵中的对角线上的距离，而且原距离矩阵的剩余的距离字典也只需包含“一半”。
二、决策变量
matlab是基于矩阵的，其创建了n*n规模的的0-1决策变量，第i行第j列的决策变量表示求解路径上城市i的下一个城市是否为城市j，是则为1，否则为0。
python在创建决策变量时则更加灵活，tuplelist和tupledict对于运筹规划求解来说，是两种高效的数据结构。python不需要严格遵循矩阵的格式，“自己到自己”是没有意义的，所以python可以不定义表示“自己到自己”的决策变量（ 即“对角线”上的变量），这也从根本上避免了求解结果中出现“自己到自己”的情况。实际上，python创建变量是从不同的视角进行的，每个0-1变量表示“连结”或“相邻”，如果城市i与城市j相邻，则城市j与城市i则必然相邻，所以对应的决策变量必然是“对称”的。（这里需要注意的是，matlab也可以通过1维的方式（即所有决策变量都放在一个向量中）实现决策变量的“裁剪”，即消除对角线上的变量，决策变量的个数由n*n变为n*(n-1)，但这种方式不够直观，易出错，也不便于采用向量化运算。）
三、离开约束和到达约束
由于决策变量的定义方式不同，约束的表现形式也不一样。
每个城市只能被一个城市“访问”，也只能“访问”一个城市，matlab可以用向量化的方式提高效率。
每个城市只能与两个城市“相邻”，tupledict数据类型本身有sum函数，可以实现方便高效的求和运算。
四、目标函数
matlab的目标函数很好理解，距离矩阵与决策变量矩阵点乘再求和。
而python可以在决策变量这里直接设置系数，可以不再显式定义目标函数 。我们通常使用setObjective方法来设置目标，但obj属性提供了设置或修改线性目标项的另一种选择。
五、懒惰约束实现流程
懒惰约束实现流程的差异是两者之间最大的差别，也是最能影响求解时间的因素。
matlab在由于没有callbacks功能，所以在实现懒惰约束时是比较死板的，其基本思路是：不加入破除子圈约束，直接求解，根据得到的最优解的子圈情况来加入相应的破圈约束，并再次求解，循环上述流程，直到得到的最优解没有子圈（通常有CCC、MTZ两种消除子圈的约束方式，这里我们采用了CCC这种方式，因为在实验过程中我们发现实现懒惰约束时这种方式的运行效率要更高一些） 。这样做最大的弊端是，每次都要求出最优解后，才能根据最优解的子圈情况来增加约束，而不是每次迭代就根据新解来加入约束，这样会浪费较多的时间。
python则灵活的多，通过callbacks函数，用户可以灵活指定约束增加的时机。每一次迭代出新解，即可检查子圈情况，如果出现子圈则增加破圈约束，这样能大大节省求解时间。这里的subtourelim函数即为本次使用的callbacks函数，where参数取值为MIPSOL，表示callbakcs函数的触发点是发现新的解时。subtour函数是一个用来找到最短子圈的方法，每当找到这个子圈，加入破除这个子圈的约束。
六、求解时间对比
将beilin8.tsp、berlin52.tsp、pr76.tsp、bier127.tsp、a280.tsp这几个算例进行求解，目标函数都是使路线的总距离最小，求解的时间对比如下：
由上表可知，python的求解效率比matlab要高，当求解规模比较大时，这种差距会更加明显。究其原因，最主要是因为python可以实现callback，大大减少了无用功的投入。此外一些特有的数据结构也显得其更加灵活，虽然matlab也能实现，但会影响其本身的向量化优势的发挥。总体上来说，python对于懒惰求解的应用比matlab更灵活方便，求解效率也更高， 所以更加适合进行懒惰约束相关的运算求解。
七、代码链接
matlab版本代码链接：https://github.com/BDLab206/blog_code/blob/main/matlab_Gurobi_TSP_advanced_Lazy_Constraints
python版本代码链接：https://github.com/BDLab206/blog_code/blob/main/python_Gurobi_TSP_advanced_Lazy_Contraints
作者：段新龙
