整数规划

1，整数规划（Integer Programming,简称IP）:规划问题中一部分变量或者全部变量为整数变量的话，该数学规划问题就属于整数规划问，即自变量存在整数。
2，整数规划的可行域是离散的
3，整数规划问题被看作数学规划里、乃至世界上最难的问题之一，通常退而求其次求解近似解或局部最优解。
4，常见整数规划问题：背包问题、广义指派问题、集合覆盖问题
5，分类（按决策变量分）：
①全部决策变量限制为整数的规划问题，称为纯整数规划
②部分决策变量限制为整数的规划问题，称为混合整数规划，即自变量既包含整数也有连续变量，混合整数规划(mixed integer programming,简称MIP）基础：https://www.gurobi.com/resource/mip-basics/
③决策变量只取0或1的规划问题，称为0-1整数规划

求解
1，求解难度大：虽然连续优化问题的可行解有无数多个，但是通过微积分，这一成熟且强大的工具，往往可以建立出针对连续优化（即可微）问题的最优性条件。整数规划问题中，整数不连续从而不可微分，导致无法使用微积分的工具，难以得到最优性条件，同时由于离散，无法满足凸性。
2，普遍方法：
① 整数规划方法：分支定界法、割平面法、蒙特卡罗法、列生成法，拉格朗日松弛法等
② 0-1整数规划：隐枚举法、（指派问题：匈牙利法）

3，精确算法：分支定界法(Branch and Bound Algorithm, B&B)、枚举法
分支（Branching) 算法是整数规划求解器的核心框架
整数规划精确算法核心的便是分支定界法，以及增加分支定界效率的各种技巧，例如割平面方法（Cutting Planes Method）。

①问题的规模往往非常小；②最后获得的解，必定是最优解

4，近似算法（Approximate Algorithm）:
根据特定问题使用一些技巧（贪婪策略，限制，划分，断切，松弛）
比较考验技术，需要给出算法的近似比，复杂度分析，具有很强的推理能力。同样，这类算法的求解规模还是比较受限制的，其最后获得的解不是最优解。

5.启发式算法（Heuristic Algorithm）:算法设计者根据经验或者观察到的性质设计出来的。TSP问题：LKH算法。
启发式算法大致可以分为四类：取整（Rounding）、下潜（Diving）、子问题（Sub-MIP）和上述三类之外的其他算法。

6，神经网络(Neural Networks)：Google的DeepMind团队2021年官宣了一篇神经网络(Neural Networks)求解MIP论文，文章链接https://arxiv.org/abs/2012.13349及国内评读评DeepMind近期神经网络求解MIP的论文：https://zhuanlan.zhihu.com/p/400603949

作者：王源
链接：https://zhuanlan.zhihu.com/p/406262088
来源：知乎