常见的运筹优化类问题及常用的优化算法

  之前的研究的是有关多目标优化的方向，期间涉及到二次规划问题最优求解，以及kkt条件相关的知识。在研究启发式方法的同时也涉及到与传统优化方法的比较。因此在这里总结一些运筹向常见的问题。如旅行商问题TSP、车辆路径规划VRP、设施选址问题、网络优化、物流调度等。
  然后介绍优化领域内的常用算法如遗传算法、粒子群算法、分支定界法、动态规划法、贪心算法。
  最后介绍谷歌DeepMind用神经网络求解MIP的方法。

1、常见问题介绍

  （1）TSP旅行商问题：一个商人从一点出发，经过所有点后返回原点。它需要满足：除起点和终点外，所有点当且仅当经过一次；起点与终点重合；所有点构成一个连通图。要求：得到这个商人经过所有点的最短路程。
  （2）VRP车辆路径规划问题：对一系列装卸货点进行适当的路径规划，在满足约束条件（客户需求、车辆载重和容积、车型、车辆行驶里程、配送时间窗、配送中心数量等限制）和目标最优化（路程最短、成本最低、使用车辆数最少、配送时间最快等）下，将客户的配送需求从配送中心送达客户点，或从客户点送回配送中心。
  （3）设施选址问题：自20世纪60年代初期以来，在运筹学中一直占据着中心位置。它来自于工厂、仓库、超市、学校、医院、图书馆、火车站、代理服务器、传感器等位置的确定问题。
  （4）网络最优化问题：是一类特殊的组合最优化问题。应用图论理论，通过网络的拓扑结构及其性质，对网络进行研究，并且以计算机算法寻求网络中的最短路、最大流等。
  （5）物流调度：物流调度是指车辆分配情况的掌控及司机及车上货物跟踪。物流调度主要是指在物流过程中,物流公司根据待发货物的重量,去向,规格，加急程度等对所属的车辆和人员进行合理的安排调度。

2、常用算法

  （1）遗传算法：该算法通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时，相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
  （2）粒子群算法：PSO中优化问题的每个解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
  （3）分支定界法：基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
  （4）动态规划法：基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。
  （5）贪心算法：贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯。

3、 DeepMind用神经网络求解MIP

  混合整数规划（MIP）是一类 NP 困难问题，来自 DeepMind、谷歌的一项研究表明，用神经网络与机器学习方法可以解决混合整数规划问题。
  混合整数规划（Mixed Integer Program, MIP）是一类 NP 困难问题，旨在最小化受限于线性约束的线性目标，其中部分或所有变量被约束为整数值。混合整数规划的形式如下：

  MIP 已经在产能规划、资源分配和装箱等一系列问题中得到广泛应用。人们在研究和工程上的大量努力也研发出了 SCIP、CPLEX、Gurobi 和 Xpress 等实用的求解器。这些求解器使用复杂的启发式算法来指导求解 MIP 的搜索过程，并且给定应用上求解器的性能主要依赖于启发式算法适配应用的程度。
  DeepMind、谷歌的研究者展示了机器学习可以用于从 MIP 实例数据集自动构建有效的启发式算法。该研究证明，机器学习可以构建针对给定数据集的启发式算法，其性能显著优于 MIP 求解器中使用的经典算法，特别是具有 SOTA 性能的非商业求解器 SCIP 7.0.1。该研究将机器学习应用于 MIP 求解器的两个关键子任务：（1）输出对满足约束的所有变量的赋值（如果存在此类赋值）（2）证明变量赋值与最优赋值之间的目标值差距边界。
   源代码并未公开，论文可自行在以下地址查看。