Python最优化算法学习笔记（Gurobi）

微信公众号：数学建模与人工智能

github地址：https://github.com/QInzhengk/Math-Model-and-Machine-Learning

第一章 最优化算法概述

1.1最优化算法简介

最优化算法,即最优计算方法,也是运筹学。涵盖线性规划、非线性规划、整数规划、组合规划、图论、网络流、决策分析、排队论、可靠性数学理论、仓储库存论、物流论、博弈论、搜索论和模拟等分支。
当前最优化算法的应用领域如下。
(1)市场销售:多应用在广告预算和媒体的选择、竞争性定价、新产品开发、销售计划的编制等方面。如美国杜邦公司在20世纪50年代起就非常重视对广告、产品定价和新产品引入的算法研究。
(2)生产计划:从总体确定生产、储存和劳动力的配合等计划以适应变动的需求计划,主要采用线性规划和仿真方法等。此外,还可用于日程表的编排,以及合理下料、配料、物料管理等方面。
(3)库存管理:存货模型将库存理论与物料管理信息系统相结合,主要应用于多种物料库存量的 管理,确定某些设备的能力或容量,如工厂库存量、仓库容量,新增发电装机容量、计算机的主存储器容量、合理的水库容量等。
(4)运输问题:涉及空运、水运、陆路运输,以及铁路运输、管道运输和厂内运输等,包括班次调度 计划及人员服务时间安排等问题。
(5)财政和会计:涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等,采用的方法包括统计分析、数学规划、决策分析,以及盈亏点分析和价值分析等。
(6)人事管理:主要涉及以下6个方面。
①人员的获得和需求估计。
②人才的开发,即进行教育和培训。
③人员的分配，主要是各种指派问题。
④各类人员的合理利用问题。
⑤人才的评价，主要是测定个人对组织及社会的贡献。
⑥人员的薪资和津贴的确定。
(7)设备维修、更新可靠度及项目选择和评价:如电力系统的可靠度分析、核能电厂的可靠度B风险评估等。
(8)工程的最佳化设计:在土木，水利、信息电子、电机、光学、机械、环境和化工等领域皆有作业研究的应用。
(9)计算机信息系统:可将作业研究的最优化算法应用于计算机的主存储器配置，如等候理论在不同排队规则下对磁盘、磁鼓和光盘工作性能的影响。利用整数规划寻找满足组需求档案的寻找次序，并通过图论、数学规划等方法研究计算机信息系统的自动设计。
(10)城市管理:包括各种紧急服务救难系统的设计和运用.如消防车、救护车、警车等分布点的设立。美国采用等候理论方法来确定纽约市紧急电话站的值班人数,加拿大采用该方法研究城市警车的配置和负责范围，以及事故发生后警车应走的路线等。此外，还涉及城市垃圾的清扫、搬运和处理，以及城市供水和污水处理系统的规划等相关问题。

1.2最优化算法的内容

最优化算法的内容包括:规划论(线性规划、非线性规划、整数规划和动态规划)、库存论、图论、排 队论、可靠性理论、对策论、决策论、搜索论等。

1.2.1规划论

1.2.2库存论

库存论中研究的主要问题可以概括为何时订货（补充存贮）和每次订多少货（补充多少库存）这两个问题。

1.2.3图论

1.2.4排队论

排队论(随机服务系统理论)主要研究各种系统的排队长度、排队的等待时间及所提供的服务等各种参数,以便求得更好的服务,它是研究系统随机聚散现象的理论。
排队论的研究目的是要回答如何改进服务机构或组织所服务的对象，使某种指标达到最优的问题。如一个港口应该有多少个码头、一个工厂应该有多少名维修人员等。
因为排队现象是一个随机现象,因此在研究排队现象时,主要采用将研究随机现象的概率论作为主要工具。此外,还涉及微分和微分方程的相关内容。排队论把它所要研究的对象形象地描述为顾客来到服务台前要求接待。如果服务台已被其他顾客占用,那么就要排队。或者服务台时而空闲、时而忙碌,那就需要通过数学方法求得顾客的等待时间、排队长度等的概率分布。
排队论在日常生活中的应用非常广泛,如水库水量的调节、生产流水线的安排、铁路运输的调度 电网的设计等。

1.2.5 可靠性理论

可靠性理论是研究系统故障，以提高系统可靠性问题的理论。可靠性理论研究的系统一般分为以下两类。
(1)不可修复系统:这种系统的参数是寿命、可靠度等，如导弹等。
(2)可修复系统:这种系统的重要参数是有效度，其值为系统的正常工作时间与正常工作时间加上事故修理时间之比、如一般的机电设备等。

1.2.6对策论

对策论(博弈论)是指研究多个个体或团队之间在特定条件制约下的对局中,利用相关方的策略 而实施对应策略的学科,如田忌赛马,智猪博弈就是典型的博弈论问题。

1.2.7决策论

决策论是研究决策问题的,所谓决策就是根据客观可能性,借助一定的理论、方法和工具,科学地 选择最优方案的过程。决策问题由决策者和决策域构成,而决策域则由决策空间、状态空间和结果函数构成。研究决策理论与方法的科学就是决策科学。
决策所要解决的问题是多种多样的,不同角度有不同的分类方法。按决策者所面临的自然状态的确定与否可分为确定型决策、不确定型决策和风险型决策,按决策所依据的目标个数可分为单目标决策与多目标决策,按决策问题的性质可分为战略决策与策略决策，以及按不同准则划分成的种种决策问题类型。不同类型的决策问题应采用不同的决策方法。
决策的基本步骤如下:
(1)确定问题,提出决策的目标;
(2)发现、探索和拟定各种可行方案;
(3)从多种可行方案中，选出最佳方案;
(4)决策的执行与反馈,以寻求决策的动态最优。
如果对方决策者也是人（一个人或一群人），双方都希望取胜，这类具有竞争性的决策称为对策或博弈型决策。构成对策问题的3个根本要素是：局中人、策略和一局对策的得失。对策问题按局中人数分类可分成两人对策或多人对策，按局中人赢得函数的代数和是否为零可分成零和对策和非零和对策,按解的表达形式可分成纯策略对策和混合策略对策,按问题是否静态形式可分成动态对策和静态对策。

1.2.8搜索论

搜索论主要研究在资源和探测手段受到限制的情况下，如何设计寻找某种目标的最优方案,并加以实施的理论和方法。

第二章 Python编程方法

2.1编程基础：Python语法

2.1.1类与实例

类在大部分编程语言中都是一个很重要的概念，类是面向对象编程的基础。使用函数可以实现简单功能的复用，而使用类则可以实现复杂的系统代码复用，因此通过类来模拟复杂的仿真系统。
举一个例子.如PPT模板可以是一个类，那么,通过修改PPT模板中的数据和文字得到新的PPT,就是实例，这个修改的过程就是实例化。又如，动物是一个类，小猫就是一个实例。
类由属性和方法两部分组成。如小猫是个类，其属性包括毛色、体重，方法包括抓老鼠。又如学生是个类，某个具体的同学就是实例，学生这个类的属性包括学号、身高、体重等;而学生这个类的方法就是学生能干什么，包括学习、考试等。方法就是这个类能做哪些事情，代码实现就是函数,一个函数经过固定格式的包装后就是类的方法。
注意:类的定义和实例化有固定的格式要求。

# 定义一个类
class cat():
    def __init__(self, color, weight):
        self.color = color
        self.weight = weight

    def catch_mice(self):
        """抓老鼠的方法"""
        print('抓老鼠')

    def eat_mice(self):
        """吃老鼠"""
        print('吃老鼠')


# 类的实例化
my_cat = cat('yello', 10)

# 调用类的方法
my_cat.catch_mice()
# 输出 抓老鼠

my_cat.eat_mice()
# 输出 吃老鼠

# 查看类的属性
print(my_cat.color)
# 输出 yello

print(my_cat.weight)
# 输出 10

所有的类都有一个_init_(self)初始化方法，用来定义类有哪些属性，也可以用来在实例化类时执行某些方法。

2.2Pandas基础

2.2.1Pandas基础数据结构

Pandas提供了Series和DataFrame两种基础数据结构，其中Series表示序列数据，DataFrame表示表格数据，且是由多个Series组成的。

2.2.2分组统计

Pandas的分组统计使用groupby函数，参数as_index=False表示统计后返回DataFrame类型的结果，否则返回Series类型的统计结果。

2.2.3apply函数

对于apply函数，其作用是对目标集合中的每一个元素执行相同的操作。

第三章 Gurobi优化器

3.1Gurobi的数据结构

3.1.1Multidict

Multidict，即复合字典，就是多重字典的意思，multidict函数允许在一个语句中初始化一个或多个字典。

3.1.2Tuplelist

Tuplelist，即元组列表，就是tuple和list的组合，也就是list元素的tuple类型，其设计目的是为了高效的在元组列表中构建子列表。

3.1.3Tupledict

Tupledict是Python的dict的一个子类,通过tupledict可以更加高效地操作Gurobi中的变量子集，也就是说当定义了很多变量,需要对其中一部分变量进行操作时，可以使用tupledict的内置方法来高效轻松地构建线性表达式,如sum和prod。tupledict的键在内部存储格式是tuplelist,因此可以使用tuplelist的select方法选择集合的子集。在实际使用中,通过将元组与每个Gurobi变量关联起来,可以有效地创建包含匹配变量子集的表达式。

3.2 Gurobi的参数和属性

3.2.1参数类型

(1)Termination停止参数，用于控制求解的停止条件。如TimeLimit设定整个求解过程耗时限制; SolutionLimit设定MIP可行解数量; BarlterLimit设定障碍法(Barrier)迭代次数限制;IterationLimit设定单纯形法迭代次数限制，如表3.1所示。
(2)Tolerances容差参数，用于控制结果的精度，在大多数情况下，这个限制是通过数值公差来管理的；如果冲突小于相应的公差，求解器将结果视为满足约束。
(3)Simplex单纯形参数，用于控制单纯形法的应用。如InfUnbdInfo控制是否生成不可行或无界模型的附加信息。
(4)Barrier障碍法参数，用于控制障碍法的操作，障碍法也称罚函数法。如QCPDual控制是否获取二次模型的对偶值。
(5)MIP混合整数规划参数，用于控制混合整数规划算法。如BranchDir用于设定分支割平面搜索方向，默认值是自动选择的。值为-1时将总是首先探索向下分支，而值为1时则始终首先探索向上分支;Heristics设定启发式算法求解所花费的时间所占的比重。
(6)MIP Cuts割平面参数，用于控制割平面的形式。如Cuts用于控制全局割平面法的强度。
(7)Tuning调参参数，用于控制求解器的调参行为。如TuneCriterion可设定调参的准则，TuneTimeLimit可设定调参的时间。
(8)Multiple Solutions多解参数，用于修改MIP的搜索行为，用于尝试为MIP模型寻找多个解。如PoolSolutions决定储存可行解的数量。

3.2.2修改参数

对于Gorubi参数的修改有3种方法:一种是selPeram( paramname, newvalue)方法,其中paramname还有两种方法，一种是参数的字符串，比如”TimeLimit”，一种是完整的类属性，比如”gkb.CRB. param.TimeLimit” ;第三种方法是直接修改类的属性，写法是modelLParame.xx。

3.2.3属性类型

通过属性(Attributes)能够控制模型(变量、约束、目标等对象)的特征, Curobi中的属性共分成8种类型,分别是模型属性、变量属性、线性约束属性、SOS约束属性、二次约束属性、广义约束属性、解的质量属性和多目标属性。
(1)Model Attributes（模型属性),包括ModelSense模型优化方向(最大化或最小化).0bjVal当 的目标值。

3.2.4查看修改属性

查看和修改Gurobi参数属性的方法很简单,用于查看属性的函数是getAttr(attrname,objs),用于修改属性的函数是setAttr(attrname,newvalue）。
注意:并不是所有属性都能进行修改,对于只读属性就只能查看而不能修改。
(1)查看属性。
方法:getAttr(attrname,objs),其中attrname是属性名称,objs(可选）是列表或字典对象用来存储查询的值。
例如,model.getAttr(GRB.Attr.ObjVal）或简写为model.ObjVal。
（2)修改属性。
方法:setAttr(attrname,newvalue),其中attrname是属性名称,newvalue是属性的值。
例如, var.setAttr(GRB.Attr.VType,’C’)或简写为var.Vtype =‘C’。

3.3 Gurobi线性化技巧

添加广义约束有两种方法;一种是model类的方法add_XXX;另一种是model.addConstr方法。约束条件用Gurobi内置函数表示.即用gurobipy.XXX函数来表达广义约束。
注意:当使用第二种方法时.该约束做的是逻辑判断,而不是赋值操作,这样就和model.addConstr方法的输入要求一致了。

3.4 Gurobi 多目标优化

在Gurobi中，可以通过MdelsetobjectiveN函数来建立多目标优化模型，多目标的setObjectiveN函数和单目标的setObjecive函数用法基本一致，不同的是多了目标优先级、目标劣化接受程度多目标的权重等参数。
setobjectiveN(expr, index, priority, weight, abstol, reltol, name)
各参数说明如下。
(1)expr:目标函数表达式，如x+ 2y + 3z。
(2)index:目标函数对应的序号(0,1,2,..),即第几个目标，注意目标函数序号应从0开始。
(3)prority:优先级,为整数，值越大表示目标优先级越高。
(4)weight:权重(浮点数)，在合成型多目标解法中使用该参数，表示不同目标之间的组合权重。
(5)abtol:允许的目标函数值最大的降低量abstol(浮点数)，即当前迭代的值相比最优值的可接受劣化程度。
(6)reltol:abstol的百分数表示，如rlol=0.05则表示可接受劣化程度是5%。
(7)name:目标函数名称。
需要注意的是，在Gurobi的多目标优化中，要求所有的目标函数都是线性的，并且目标函数的优化方向应一致，即全部最大化或全部最小化，因此可以通过乘以-1实现不同的优化方向。
当前Gurobi支持3种多目标模式，分别是Blend（合成型)、Hierarchical(分层型)、两者的混合型。
Blend通过对多个目标赋予不同的权重实现将多目标转化成单目标函数，权重扮演优先级的角色
Herchial有优先级，一般理解是在保证第一个目标值最优的情况下优化第二个目标,或者在优 化第二个目标时要保证第一一个目标的最优值只能允许少量劣化。

3.5callback函数

callback函数的主要作用是为了获取程序运行过程中的一些中间信息，或者在程序运行过程中动态修改程序运行状态，如用户有时在求解过程中需要实现一些功能，包括终止优化、添加约束条件(割平面)、嵌入自己的算法等。

3.5.1回调函数callback定义

回调函数callback的定义的方法如下。
def funeion_name (model, where):
print(‘dosomething where gurobi run’，
其中calback函数有两个固定的参数:model是指定义的gurobi.Model类，where是指回调函数的出发点。
在callback函数使用过程中,需要注意的是where和what，即在什么地方(where)获取哪些信息(what)，如下面的代码,cbGet查询获取优化器的指定信息,即grb.CRB.Callback.MULTIOBJ_OBJCNT当 前解的数量。
if where -=grb.GRB.Callback.MULTIOBJ:# where
print(model.cbGet(grb.GRB.Callback.MULTIOBJ_OBJCNT)) # what
注意:where和what一般是配套使用的,如当where=MIP时,what只能获取MIP的相关信息。

3.5.2callback函数的功能

在Gurobi中除cbGet函数外还有一些常用函数用于获取运行过程中信息或修改运行状态,包 cbGetNodeRel.cbGetSolution ,cbCut ,cbLazy ,cbSetSolution ,cbStopOneMultiObj等。
cbGet(what)这个函数的使用最为频繁,常用于查询求解过程中的一些信息，如目标值、节点数等,使用时应注意what与where的匹配。

第四章 线性规划

4.1线性规划的标准型

在线性规划求解方法中,模型的标准形式如下。
(1)目标函数求最大值。
(2)约束条件为等式约束。
(3)约束条件右边的常数项大于或等于0。
(4)所有变量大于或等于0。
对于非标准形式的模型,约束方程可以通过引人松弛变量使约束不能转化成等式约束。在某一些模型中,如果目标函数是求最小值,则两边乘以-1将求min转成求max;如果遇到约束方程右边常 数项为负数,则将约束方程乘以-1使常数项非负;如果变量x没有约束,则既可以是正数也可以是负数。
将模型转换成标准型后，就可以使用经典的线性规划方法求解了,包括单纯形法、内点法等。
内点法和单纯形法的结果相差可能很大，这是因为内点法的搜索路径是在可行域内部,而不能在可行域的边界上，这也是内点法的局限性。
内点法不仅局限在线性规划上，二次规划等也是可以求解的,因为其本质是利用函数梯度求最优值，这同很多机器学习算法的思路是一致的，真正的难点在于如何保证新的目标函数是否存在一阶导数和二阶导数，以及如何得到一阶导数和二阶导数的信息，有了导数信息，很多工具如Python中SciPy库的optimize包就可以利用函数的一阶导数和二阶导数快速求解函数的最优值。此外，初始迭代点的选择也是很重要的，在线性规划问题中能够保证最后得到的是最优解，而非线性规划问题中，函数是非凸的，因此很难保证最后的解是全局最优解。

4.2列生成法

列生成法是一种用于求解大规模线性优化问题非常高效的算法，本质上，列生成算法就是单纯形法的一种形式，它是用来求解线性规划问题的，所不同的是列生成法改善了大规模优化问题中单纯形法基变换计算效率低的问题，列生成法在整数规划中已经得到了广泛应用。

4.3对偶问题

可以将原问题和对偶问题看成是一个问题的两个视角，如在一定的资源下如何安排生产才能使利润最大，这个问题的另一个角度就是怎样购买这些生产资源使花钱最少。从数学的角度来说，如果原问题不好求解，可以尝试从对偶问题的角度出发求原问题，如在求最小问题中，对偶问题就是寻找原问题目标函数的下界。

4.4拉格朗日乘子法

第五章 整数规划

通常默认变量的取值是大于或等于0的自然数,然而在许多实际问题中，都要求决策变量的取值为正整数，如机器台数、商品数量、工人数量、装载货物的汽车数量等，,这类要求变量为整数的问题称为整数规划(nteger Programming,IP)问题。如果只要求一部分决策变量取整数，则称为混合整数规划(Mix Integer Programming,MIP)。如果决策变量的取值只能是0或1，则称为0-1整数规划(Binary Integer Programming ,BIP)。如果模型是线性模型，则称为整数线性规划(Integer Linear Programming, ILP)。
求解整数规划的常用方法有分支定界法和割平面法，这两种方法的共同特点是，在线性规划的基础上，通过增加附加约束条件，使整数最优解称为线性规划的一个极点(可行域的一个顶点)，于是就可以用单纯形法等方法找到这个最优解，它们的区别在于约束条件的选取规划和方式不同。

第六章 多目标优化

多目标优化(Multiobjective Optimization Problem, MOP)也叫多目标规划，即同时优化多个目标的规划问题。前面讲的都是单目标规划方法,但是在实际生活中，很多决策往往是多目标决策，如购买商品时，既要保证质量，也要价格合适,如果有赠品就更好了。那么，在企业的生产管理中，既希望利润最大化，也希望成本最小化。
在讲Gurobi求解多目标决策时,已经介绍了Curobi求解多目标规划的两种方法:一种是合成型.将多目标转化成单目标决策问题;另一种是分层型,在保证第一目标的情况下，尽量优化第二,第三等目标。
因此,多目标规划一般有两种方法:一种是化多为少,即将多目标转化为比较容易求解的单目标规划方法;另一种是分层序列法,即把目标按其重要性排序,每次都在前一个目标最优解集内求解下一个目标的最优解,直到求出共同的最优解。那么,如何理解目标最优解集呢?在多目标规划中往往有多个最优解同时满足约束条件,不同的解之间不能简单通过大小来比较,这点是同单目标规划的最大区别,多个解组成的集合称为帕累托最优解集,组成的超平面称为帕累托前沿。

第七章 动态规划

动态规划(Dynamic Programming,DP)是运筹学的一个分支，是解决多阶段决策过程最优化的一种方法。它把多变量复杂决策的问题进行分阶段决策,可高效求解多个单变量的决策问题。动态规划在现代企业管理、工农业生产中有着广泛的应用，许多问题用动态规划处理，比用线性规划或非线性规划处理更加有效,如最短路径、设备维修换新、多阶段库存等问题。

7.1 多阶段决策问题

有这样一类问题，它可以从时间或空间t将决策的过程分解为若干个相互联系的阶段.每个阶段都需要做出决策，当前阶段的决策往往会影响到下个阶段的决策,将各阶段的决策构成一个决策序列、称为策略。每个阶段都有若干个决策可供选择,因此就有许多策略可以选择。如何在这些策略中选择一个最优策略，这类问题就是多阶段决策问题。
一个较常见的多阶段决策问题是网络最短路径问题，给定的一个网路，需要从A出发到达D,如何选择路径才能使总路程最短，显然这是个4阶段决策问题。
动态规划的另一个常见例子是背包问题，一个背包最多能放15kg的物品，每个物品的重量和价值都已经知道，那要选择哪些物品才能使背包内的物品总价值最大?背包问题可以看成是一个多阶段规划问题，如果选择物品A,占用的空间将使得其他可供选择的物品减少。虽然简单背包问题可以用整数规划方法求解，但是用动态规划方法求解更为高效。

第八章 图与网络分析

8.1图的基本概念

在算法最优化领域，图与网络分析是一个很重要的组成部分，特别是在交通运输领域中，问题会被建模成一个图优化问题。不仅仅是交通问题可以用图的模型表示，像人物关系图谱、任务流程依赖关系、电力线网、信息网络等都可以用图来表示。

8.2最小生成树

在数学建模中,如果用图的数据结构求解比较麻烦,而用树的数据结构求解比较简单时,就会用到最小生成树,将图转成树来建模。在实际问题中,一个经典的案例就是村庄架设电话线问题，假设6个村庄,网络边的权值标志村庄之间的距离,现在需要架设一条电话线构造成通信网,使每个村庄都能相互通信,且电话线的总长度最小。这同最短路径TSP问题有点相似,不同的是,在最短路径问题中,每个节点只能访问一次,而在村庄电话线问题中,有些节点是可以被访问多次的。

8.3网络最大流问题

研究网络通过的流量也是生产管理中经常遇到的问题,如交通干线车辆最大通行能力.生产流水线产品最大加工能力、供水网络中最大水流量等。这类网络的弧有确定的容量(Capacity) ,虽然常用cij表示从节点i到节点j的弧最大流量,但实际上通过该弧的流量不一定能达到最大流量,因此常用fij表示通过弧的实际流量。
对于网络最大流研究的两个问题:一个是从网络的起点出发到网络终点所能达到的最大流量;另一个问题是,当求解网络最大流量后,分析限制网络流量最大化的关键弧,通过某些方法增加该弧的容量,使网络最大化流量增加更多。

8.4 VRP问题

VRP( Vehicle Routing Problem,车辆路径问题)是TSP问题的扩展，是交通物流领域的研究热点。这里以物流配送场景为例介绍VRP问题。某配送中心对一定区域内的客户(需求点)进行货物配送服务.每个客户的货物配送量小于车辆最大装载量，且每个客户距离配送中心，以及各个客户间的距离是已知的，通常不存在只需要一辆车跑一趟就能满足全部客户的配送需求，否则VRP就退化为TSP问题，一般来说，需要几辆车或一辆车跑多趟才能满足全部客户的配送需求。此时需要解决的问题有以下两点。
(1)哪些客户的货物应该分配到同一辆车上。
(2)每辆车对客户服务的次序是什么。
VRP问题是运筹优化中一类普遍又重要的问题,Google开源的运筹优化求解器Ortools针对这类问题有专门的调用接口,前面提到的VRP问题就是车辆容量限制的CVRP问题,如果是时间窗约束,如寄快递会指定快递员上门取件的时间段,这就是时间窗口约束的VRP问题,即VRPTW。在配货场景中,因仓库装卸能力有限,只能同时对两辆车进行装卸,那么其他车就需要等待前面的车装卸完成。相似的场景还有飞机场的飞机调度问题,由于飞机场的机位是有限的,如何安排飞机的起降时间和顺序就显得尤为重要,这类问题是资源约束的VRP问题,即VRRC。这些类常见问题Ortools提供了现成的解决方案。

第九章 智能优化算法

常见的智能优化算法有遗传算法、粒子群算法、模拟退火算法、禁忌搜索算法、蚁群算法、差分进化算法等。