优化三大要素： 决策变量、约束条件、和目标函数
根据3个要素的不同，优化问题划分为多种不同的类型，其中就包含线性规划LP和混合整数规划MIP。

线性规划LP基础： https://www.gurobi.com/resource/linear-programming-basics/

线性规划（Linear programming,简称LP）：研究线性约束条件下线性目标函数的极值问题的数学理论和方法

1. 线性：数学里，一般说的线性，是说的线性映射，满足
   ①可加性：f（x+y）=f（x）+f（y）
   ②齐次性：f（ax）=af（x）
2. 线性关系：两个变量之间存在一次函数关系
3. 约束优化问题：给定约束条件和目标函数，计算约束条件下目标函数的最大（最小）值。
4. 目标函数和约束条件都是线性函数的情况，称为线性优化问题，即目标函数是线性的，所有约束也是线性的。

经典LP问题：资源分配生产问题、

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
来源：知乎

混合 整数规划 基础-整理自Gurobi 文章目录 整数规划 模型分类MILPMIQP和MIQCP分支定界算法总述Fathomed and Incumbent NodesBest Bound and GapMIP 算法的改进技术PresolveCutting PlanesHuristicsParallelism 整数规划 模型分类 混合 整数线性规划 Objective: minimize cT x Constraints: A x = b (linear constraints) l ≤ x ≤ u (bo 混合 整数规划 问题是运筹优化中经常遇到的一类问题。在这类问题中自变量的类型可能是整数也可能不是整数。相比于连续优化， 混合 整数规划 很多时候会更难求解。在学术界 混合 整数规划 一直是一个活跃的研究领域。... 规划中的变量（部分或全部）限制为整数时，称为 整数规划 。若在线性规划模型中， 变量限制为整数，则称为整数线性规划。目前所流行的求解 整数规划 的方法，往往只适 用于整数线性规划。目前还没有一种方法能有效地求解一切 整数规划 。 混合 整数规划 (MIP) 是 NP-hard 问题中的一类，它的目标是在线性约束下将线性目标最小化，同时使部分或全部变量均为整数值，在容量规划、资源分配与装箱等等现实场景中得到了广泛应用。该方向的大量研究与工程投入都集中在了开发实用求解器上，比如 SCIP、CPLEX、Gurobi 和 Xpress。这些求解器都是使用复杂的启发式算法来指导求解 MIP 的搜索过程。一个求解器在特定应用上的表现主要是取决于该求解器的启发式算法与该应用的匹配程度。 如果你刚刚入门线性规划，对于线性规划的基本原理、概念、术语，以及 Gurobi 内部的核心算法不了解的话，请花费 10分钟时间，阅读以下二个科普文章。如果对于英文不熟练的话，可以采用谷歌浏览器，然后选择翻译为中文。 LP 基础：https://www.gurobi.com/resource/linear-programming-basics/ MIP 基础： https://www.gurobi.com/resource/mip-basics/ 一.优化基础 优化中非常重要的3个要素，分别是：决策变量、 混合 整数规划 (MIP) 是 NP-hard 问题中的一类，它的目标是在线性约束下将线性目标最小化，同时使部分或全部变量均为整数值，在容量规划、资源分配与装箱等等现实场景中得到了广泛应用。 该方向的大量研究与工程投入都集中在了开发实用求解器上，比如 SCIP、CPLEX、Gurobi 和 Xpress。这些求解器都是使用复杂的启发式算法来指导求解 MIP 的搜索过程。一个求解器在特定应用上的表现主要是取决于该求解器的启发式算法与该应用的匹配程度。 在这篇工作中，作者团队展示了机器学习可用于从 MIP 实 混合 整数线性规划(MILP) 线性规划模型(Linear Programming, LP)：LP的定义比较简单，它指的就是目标函数是线性的，所有约束也是线性的，最后，决策变量可以取任何的实数。如果在线性规划问题中有部分决策变量要求必须是整数， 那么这时的规划问题就转变成 混合 整数线性规划问题了。也就是说优化问题不止有条件约束，还有整数约束。 min x1+x2 “数学问题描述” x1-2x2>=6 “条件约束” x1 in integer“整数约束”,x2>=0 “条件约束” 一、 算法背景 Benders分解算法是 J.F.Benders 在1962年首先提出的，是解决某些大规模优化问题的一种求解方法。Benders 分解不是同时考虑大规模问题的所有决策变量和约束，而是将问题划分为多个较小的问题。 由于优化问题的计算难度随着变量和约束的数量而显着增加，因此迭代地解决这些小问题可能比解决单个大问题更有效。本文，我们只探讨最基础的 Benders 分解算法，只考虑将 混合 整数规划 问题分解为线性规划和 整数规划 两个子问题。 更深入的探讨及原理分享，后期会在本人公众号内逐一展示，欢迎关注 0-1型 整数规划 是 整数规划 中的特殊情形，它的变量x仅取值0或1，称其为0-1变量或二进制变量。在实际问题中，如果引入0-1变量，就可以把有各个情况需要分别讨论的数学规划问题统一在一个问题中讨论了。求解方法可分为：1分支定界法，2割平面法，2隐枚举法，4匈牙利法，5蒙特卡罗法。数学规划中的变量（部分或全部）限制为整数时，称为 整数规划 ，前者为完全 整数规划 ，后者为 混合 整数规划 。 整数规划 由于限制变量为整数而增加了难度，但又由于整数解是有限个，为枚举法提供了方便。