梁颖宗

个人信息Personal Information

教授

硕士生导师

教师拼音名称：Liang Yingzong

入职时间：2018-12-27

所在单位：材料与能源学院

联系方式：yliang@gdut.edu.cn

在职信息：在职

主要任职：Professor

其他任职：Professor

毕业院校：The Hong Kong University of Technology

学科：工程热物理

同专业硕导

教师博客

当前位置：中文主页 >> 教师博客

线性规划

点击次数：

线性规划（LP），也称为线性优化，是一种在数学模型中实现最佳结果（例如最大利润或最低成本）的方法，其要求由线性关系表示。线性规划是数学规划（也称为数学优化）的特例。

更正式地说，线性规划是一种优化线性目标函数的技术，受线性等式和线性不等式约束。它的可行区域是凸多面体，它是定义为有限多个半空间的交集的集合，每个半空间由线性不等式定义。其目标函数是在该多面体上定义的实值仿射（线性）函数。线性规划算法在多胞形中找到该函数具有最大（或最小）值的点（如果存在这样的点）。

线性规划是可以用标准形式表示的问题

${\begin{对齐}&{\text{求一个向量}}&&\mathbf {x} \\&{\text{最大化}}&&\mathbf {c} ^{\mathsf {T}} \mathbf {x} \\&{\text{服从}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{和}}&&\mathbf {x} \geq \mathbf { 0} .\end{对齐}}$

这里的组件 $\mathbf {x}$ 是要确定的变量， $\mathbf {c}$ 和 $\mathbf {b}$ 给定向量，并且 $A$ 是给定矩阵. 其值要最大化的函数 ( $\mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x}$ 在这种情况下）称为目标函数。限制条件 $A\mathbf {x} \leq \mathbf {b}$ 和 $\mathbf {x} \geq \mathbf {0}$ 指定要优化目标函数的凸多面体。

线性规划可以应用于各个研究领域。它广泛应用于数学，并在较小程度上应用于商业、经济学和一些工程问题。使用线性规划模型的行业包括交通、能源、电信和制造。事实证明，它对于规划、路由、调度、分配和设计中的各种类型问题建模非常有用。

具有两个变量和六个不等式的简单线性程序的图示。可行解集用黄色表示，并形成一个多边形，即二维多面体。线性成本函数的最佳值是红线与多边形相交的位置。红线是成本函数的水平集，箭头表示我们优化的方向。具有三个变量的问题的封闭可行区域是凸多面体。给出目标函数固定值的表面是平面（未示出）。线性规划问题是找到多面体上具有最高可能值的平面上的点。

历史[编辑]

列昂尼德·康托罗维奇约翰·冯·诺依曼

解决线性不等式系统的问题至少可以追溯到傅里叶，他于 1827 年发表了一种解决线性不等式的方法，^[1] ，傅里叶-莫茨金消除法就是以他的名字命名的。

1939 年，苏联数学家和经济学家 Leonid Kantorovich给出了与一般线性规划问题等价的线性规划公式，并提出了解决该问题的方法。^[2]这是他在第二次世界大战期间开发的一种计划支出和回报的方法，以减少军队的成本并增加敌人的损失。^{[需要引用]}康托罗维奇的工作最初在苏联被忽视。^[3]大约与康托罗维奇同时期，荷兰裔美国经济学家TC Koopmans将经典经济问题表述为线性规划。康托罗维奇和库普曼斯后来分享了 1975 年诺贝尔经济学奖。^[1] 1941年，弗兰克·劳伦·希区柯克还将交通问题表述为线性规划，并给出了与后来的单纯形法非常相似的解决方案。^[2]希区柯克于1957年去世，诺贝尔奖不追授。

从 1946 年到 1947 年，George B. Dantzig独立开发了通用线性规划公式，用于解决美国空军的规划问题。^[4] 1947年，Dantzig还发明了单纯形法，首次有效地解决了大多数情况下的线性规划问题。^[4]当丹齐格安排与约翰·冯·诺依曼会面讨论他的单纯形方法时，诺依曼意识到他一直在博弈论中研究的问题是等价的，立即猜想了对偶理论。^[4] Dantzig 在 1948 年 1 月 5 日未发表的报告《线性不等式定理》中提供了正式的证明。^[3] Dantzig 的工作于 1951 年向公众公开。战后几年，许多行业将其应用于各自的领域。每日计划。

Dantzig 最初的例子是找到 70 个人到 70 个工作岗位的最佳分配。测试所有排列以选择最佳分配所需的计算能力是巨大的；可能的配置数量超过了可观测宇宙中的粒子数量。然而，通过将问题视为线性规划并应用单纯形算法，只需片刻即可找到最佳解决方案。线性规划背后的理论大大减少了必须检查的可能解决方案的数量。

Leonid Khachiyan于 1979 年首次证明线性规划问题可以在多项式时间内求解，^[5]但该领域更大的理论和实践突破出现在 1984 年，当时Narendra Karmarkar引入了一种新的内点方法来求解线性规划问题。^[6]

用途[编辑]

由于多种原因，线性规划是广泛使用的优化领域。运筹学中的许多实际问题都可以表示为线性规划问题。^[3]线性规划的某些特殊情况，例如网络流问题和多商品流问题，被认为足够重要，需要对专门算法进行大量研究。许多其他类型优化问题的算法通过将线性规划问题作为子问题来解决。从历史上看，线性规划的思想启发了优化理论的许多核心概念，例如对偶性、 分解以及凸性及其概括的重要性。同样，线性规划在微观经济学的早期形成中被大量使用，目前也被用于公司管理，例如计划、生产、运输和技术。尽管现代管理问题日新月异，但大多数企业都希望以有限的资源实现利润最大化、成本最小化。Google 还使用线性规划来稳定 YouTube 视频。^[7]

标准形式[编辑]

标准形式是描述线性规划问题的常用且最直观的形式。它由以下三部分组成：

要最大化的线性（或仿射）函数

例如 $f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}$

问题约束如下形式

例如
- ${\begin{矩阵}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}& \leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{矩阵}}$

非负变量

例如
- ${\begin{矩阵}x_{1}\geq 0\\x_{2}\geq 0\end{矩阵}}$

问题通常用矩阵形式表示，则变为：

$\max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}$

其他形式，例如最小化问题、替代形式约束问题以及涉及负变量的问题始终可以重写为标准形式的等效问题。

示例[编辑]

农民示例的图形解决方案 - 在违反条件的阴影区域之后，距离原点最远的虚线的未阴影区域的顶点给出了最佳组合（它位于农药和土地线上意味着农药和土地限制收入）

假设一个农民有一块农田，比如说L km ²，要种植小麦或大麦或两者的某种组合。农民的肥料数量有限，F千克，农药数量有限，P千克。每平方公里小麦需要F ₁公斤化肥和P ₁公斤农药，而每平方公里大麦则需要F _{2 公斤}化肥和P ₂公斤农药。设S ₁为每平方公里小麦的销售价格，S ₂为大麦的销售价格。如果我们分别用x ₁和x ₂表示种植小麦和大麦的土地面积，那么通过选择x ₁和x ₂的最佳值可以使利润最大化。该问题可以用以下标准形式的线性规划问题来表示：

最大化： $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		（最大化收入（小麦总销量加上大麦总销量）——收入是“目标函数”）
须遵守：	$x_{1}+x_{2}\leq L$	（总面积限制）
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	（肥料限制）
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	（农药限量）
	$x_{1}\geq 0,x_{2}\geq 0$	（不能种植负区域）。

以矩阵形式表示为：

最大化 ${\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$
受 ${\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\ end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix} }\geq {\begin{bmatrix}0\\0\end{bmatrix}}。$

增强形式（松弛形式）[编辑]

线性规划问题可以转换为增广形式，以便应用单纯形算法的常见形式。这种形式引入了非负松弛变量，用约束中的等式代替不等式。然后可以将问题写成以下块矩阵形式：

最大化 $z$ :
${\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix }z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}$
$\mathbf {x} \geq 0,\mathbf {s} \geq 0$

在哪里 $\mathbf {s}$ 是新引入的松弛变量， $\mathbf {x}$ 是决策变量，并且 $z$ 是要最大化的变量。

示例[编辑]

上面的例子被转换成下面的增强形式：

最大化： $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		（目标函数）
受：	$x_{1}+x_{2}+x_{3}=L$	（增强约束）
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F$	（增强约束）
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P$	（增强约束）
	$x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.$

在哪里 $x_{3},x_{4},x_{5}$ 是（非负）松弛变量，在本例中代表未使用的面积、未使用的化肥量和未使用的农药量。

以矩阵形式表示为：

最大化 $z$ :
[1-�1-�20000111000�1�20100磷1磷2001][��1�2�3�4�5]=[0��磷],[�1�2�3�4�5]≥0。
${\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\结束{bmatrix}}{\开始{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={ \begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{ 4}\\x_{5}\end{bmatrix}}\geq 0.$

二元性[编辑]

主条目：对偶线性规划

每个线性规划问题（称为原始问题）都可以转换为对偶问题，它提供了原始问题最优值的上限。以矩阵形式，我们可以将原问题表示为：

最大化c ^Tx ，且满足A x ≤ b、x ≥ 0；
- 与相应的对称对偶问题，
在A ^Ty ≥ c , y ≥ 0 的条件下最小化 b ^Ty。

另一种原始公式是：

在A x ≤ b的情况下最大化c ^Tx；
- 以及相应的不对称对偶问题，
最小化 b ^Ty ，且满足A ^Ty = c , y ≥ 0。

对偶理论有两个基本思想。其一是（对于对称对偶）对偶线性程序的对偶是原始线性程序。此外，线性规划的每个可行解都给出了其对偶目标函数最优值的界限。弱对偶定理指出，对偶在任何可行解处的目标函数值总是大于或等于原始在任何可行解处的目标函数值。强对偶定理指出，如果原数有一个最优解x ^*，那么对偶也有一个最优解y ^*，并且c ^Tx ^* = b ^Ty ^*。

线性规划也可以是无界的或不可行的。对偶理论告诉我们，如果原数是无界的，那么根据弱对偶定理，对偶是不可行的。同样，如果对偶是无界的，那么原数必定是不可行的。然而，对偶和原始都有可能都不可行。有关详细信息和更多示例，请参阅双线性程序。

变体[编辑]

覆盖/包装二元性[编辑]

覆盖/包装问题对
覆盖问题包装问题最小设定覆盖范围最大套装包装最小边缘覆盖最大匹配最小顶点覆盖最大独立集箱盖箱式包装多边形覆盖长方形包装
v t e

覆盖LP是以下形式的线性规划：

最小化： b ^Ty，
满足：A ^Ty ≥ c，y ≥ 0，

使得矩阵A以及向量b和c都是非负的。

覆盖 LP 的对偶是打包 LP，其形式为线性规划：

最大化：c ^Tx，
满足：A x ≤ b，x ≥ 0，

使得矩阵A以及向量b和c都是非负的。

例子[编辑]

覆盖和打包 LP 通常作为组合问题的线性规划松弛而出现，并且在近似算法的研究中很重要。^[8]例如，集合打包问题、独立集合问题和匹配问题的LP松弛都是打包LP。集合覆盖问题、顶点覆盖问题和支配集问题的LP松弛也覆盖LP。

查找图形的分数着色是覆盖 LP 的另一个示例。在这种情况下，图的每个顶点都有一个约束，并且图的每个独立组都有一个变量。

互补松弛[编辑]

当使用互补松弛定理仅知道原数的最优解时，可以获得对偶的最优解。该定理指出：

假设x = ( x ₁ , x ₂ , ... , x _n ) 是原始可行的，并且y = ( y ₁ , y ₂ , ... , y _m ) 是对偶可行的。令( w ₁ , w ₂ , ..., w _m ) 表示相应的原始松弛变量，令( z ₁ , z ₂ , ... , z _n ) 表示相应的对偶松弛变量。那么x和y对于各自的问题来说是最优的当且仅当

x _j z _j = 0，对于j = 1, 2, ... , n，并且
w _i y _i = 0，对于i = 1, 2, ... , m。

因此，如果原数的第 i个松弛变量不为零，则对偶数的第 i个变量等于 0。同样，如果对偶的第 j个松弛变量不为零，则原数的第 j个变量等于 0。

这种最优性的必要条件传达了一个相当简单的经济原理。在标准形式中（最大化时），如果受约束的原始资源存在松弛（即存在“剩余”），则该资源的额外数量必定没有价值。同样，如果双重（影子）价格非负约束要求存在松弛，即价格不为零，则必定存在稀缺供应（没有“剩余”）。

理论[编辑]

最优解的存在性[编辑]

在几何上，线性约束定义了可行区域，它是凸多面体。线性函数是凸函数，这意味着每个局部最小值都是全局最小值；类似地，线性函数是凹函数，这意味着每个局部最大值都是全局最大值。

由于两个原因，不一定存在最佳解决方案。首先，如果约束条件不一致，则不存在可行解：例如，约束条件x≥2 和x≤1 不能同时满足；在这种情况下，我们说 LP 是不可行的。其次，当多胞形在目标函数的梯度方向上无界时（其中目标函数的梯度是目标函数系数的向量），则无法获得最优值，因为总是可以这样做优于目标函数的任何有限值。

多面体的最佳顶点（和射线）[编辑]

否则，如果存在可行解并且约束集有界，则通过凸函数的极大值原理（或者，通过凹函数的极小值原理），始终在约束集的边界上获得最佳值，因为线性函数既有凸函数又有凹函数。然而，有些问题有不同的最优解；例如，寻找线性不等式系统的可行解的问题是一个线性规划问题，其中目标函数是零函数（即处处取零值的常数函数）。对于目标函数为零的可行性问题，如果有两个不同的解，则解的每个凸组合都是一个解。

多面体的顶点也称为基本可行解。选择这个名称的原因如下。令d表示变量的数量。那么线性不等式的基本定理意味着（对于可行问题）对于 LP 可行区域的每个顶点x ^*，存在一组来自 LP 的d个（或更少）不等式约束，这样，当我们将这些d约束视为等式的唯一解是x ^*。因此，我们可以通过查看所有约束集（离散集）的某些子集来研究这些顶点，而不是 LP 解的连续体。这一原理是求解线性规划的单纯形算法的基础。

算法[编辑]

另请参阅：数值分析主题列表 § 线性规划

在线性规划问题中，一系列线性约束产生这些变量的可能值的凸可行区域。在二变量情况下，该区域的形状是凸简单多边形。

基础交换算法[编辑]

Dantzig 单纯形算法[编辑]

单纯形算法是由 George Dantzig在 1947 年开发的，它通过在多胞形的顶点构造可行解，然后沿着多胞形边缘上的路径行走到目标函数值不减的顶点来解决线性规划问题，直到肯定达到了最佳状态。在许多实际问题中，都会发生“停顿”：在目标函数没有增加的情况下进行了许多枢轴。^[9]^[10]在罕见的实际问题中，单纯形算法的常用版本实际上可能会“循环”。^[10]为了避免循环，研究人员制定了新的旋转规则。^[11]

在实践中，单纯形算法非常有效，如果采取某些防止循环的预防措施，可以保证找到全局最优值。单纯形算法已被证明可以有效地解决“随机”问题，即以立方数的步骤，^[12]，这与其在实际问题上的行为相似。^[9]^[13]

然而，单纯形算法在最坏情况下的表现很差：Klee 和 Minty 构建了一系列线性规划问题，对于这些问题，单纯形方法需要执行的步骤数与问题大小呈指数关系。^[9]^[14]^[15]事实上，有一段时间我们不知道线性规划问题是否可以在多项式时间内求解，即复杂度等级为 P。

十字交叉算法[编辑]

与 Dantzig 的单纯形算法类似，十字交叉算法是一种在基之间旋转的基交换算法。然而，十字交叉算法不需要保持可行性，而是可以从可行的基础转向不可行的基础。十字交叉算法不具有线性规划的多项式时间复杂度。在最坏的情况下，两种算法都会访问D维（扰动）立方体（克利-明蒂立方体）的所有^二维角。^[11]^[16]

内点[编辑]

与通过遍历多面体集合上的顶点之间的边来找到最优解的单纯形算法相比，内点方法在可行区域的内部移动。

椭圆体算法，遵循 Khachiyan [编辑]

这是有史以来第一个用于线性规划的最坏情况多项式时间算法。为了解决具有n 个变量并且可以用L 个输入位进行编码的问题，该算法运行在 $O(n^{6}L)$ 时间。^[5] Leonid Khachiyan在 1979 年通过引入椭球体方法解决了这个长期存在的复杂性问题。收敛分析有（实数）前身，特别是Naum Z. Shor开发的迭代方法以及Arkadi Nemirovski 和 D. Yudin 开发的近似算法。

Karmarkar 投影算法[编辑]

主条目：Karmarkar 算法

Khachiyan 的算法对于建立线性规划的多项式时间可解性具有里程碑式的重要性。该算法并不是计算上的突破，因为单纯形法对于除特殊构造的线性程序族之外的所有线性程序都更有效。

然而，Khachiyan 的算法激发了线性规划的新研究方向。1984年，N. Karmarkar提出了线性规划的投影方法。Karmarkar 的算法^[6]改进了 Khachiyan 的^[5]最坏情况多项式界（给出 $O(n^{3.5}L)$ ）。Karmarkar 声称他的算法在实际的线性规划中比单纯形法快得多，这一说法引起了人们对内点方法的极大兴趣。^[17]自从Karmarkar的发现以来，许多内点方法被提出并分析。

Vaidya 的 87 算法[编辑]

1987年，Vaidya提出了一种运行在 $O(n^{3})$ 时间。^[18]

Vaidya 的 89 算法[编辑]

1989 年，Vaidya 开发了一种运行在 $O(n^{2.5})$ 时间。^[19]从形式上来说，该算法采用 $O((n+d)^{1.5}nL)$ 最坏情况下的算术运算，其中 $d$ 是约束的数量， $n$ 是变量的数量，并且 $L$ 是位数。

输入稀疏时间算法[编辑]

2015 年，Lee 和 Sidford 表明，它可以通过 ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ 时间，^[20]其中 $nnz(A)$ 表示非零元素的个数，仍然取 $O(n^{2.5}L)$ 在最坏的情况下。

当前矩阵乘法时间算法[编辑]

2019 年，Cohen、Lee 和 Song 将运行时间改进为 ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ 时间， $欧米伽$ 是矩阵乘法的指数， $\α$ 是矩阵乘法的对偶指数。^[21] $\α$ 被（粗略地）定义为可以乘以一个的最大数字 $n\次n$ 矩阵由一个 $n\times n^{\alpha }$ 矩阵中 $O(n^{2})$ 时间。在李、宋和张的后续工作中，他们通过不同的方法重现了相同的结果。^[22]这两种算法仍然存在 ${\tilde {O}}(n^{2+1/6}L)$ 什么时候 $\omega =2$ 和 $α=1$ 。结果由于江、宋、韦恩斯坦和张的提高 ${\tilde {O}}(n^{2+1/6}L)$ 到 ${\tilde {O}}(n^{2+1/18}L)$ 。^[23]

内点法和单纯形算法的比较[编辑]

目前的观点是，对于线性规划的常规应用，基于单纯形的方法和内点方法的良好实现的效率是相似的。然而，对于特定类型的 LP 问题，一种类型的求解器可能比另一种更好（有时好得多），并且内点方法与基于单纯形的方法生成的解的结构在支持下显着不同。后者的活动变量集通常较小。^[24]

未解决的问题和最近的工作[编辑]

计算机科学中未解决的问题：

线性规划是否承认强多项式时间算法？

（更多计算机科学中未解决的问题）

线性规划理论中有几个悬而未决的问题，这些问题的解决将代表数学上的根本性突破，并可能代表我们解决大规模线性规划的能力的重大进步。

LP 是否承认强多项式时间算法？
LP 是否承认强多项式时间算法来找到严格互补的解决方案？
LP 是否承认实数（单位成本）计算模型中的多项式时间算法？

这组密切相关的问题被Stephen Smale列为21 世纪18 个最大的未解决问题之一。用斯梅尔的话说，该问题的第三个版本“是线性规划理论中未解决的主要问题”。虽然存在求解弱多项式时间线性规划的算法，例如椭球体方法和内点技术，但尚未发现能够在约束数量和变量数量方面实现强多项式时间性能的算法。此类算法的开发将具有巨大的理论意义，并且也许还能在解决大型线性规划方面带来实际收益。

尽管赫希猜想最近在更高维度上被证明是错误的，但它仍然留下了以下问题。

是否存在导致多项式时间单纯形变体的主元规则？
所有多面图都具有多项式有界直径吗？

这些问题涉及性能分析和类似单纯形方法的开发。尽管单纯形算法具有指数时间的理论性能，但其在实践中的巨大效率表明，可能存在以多项式甚至强多项式时间运行的单纯形变体。了解是否存在任何此类变体将具有重大的实践和理论意义，特别是作为确定LP是否可以在强多项式时间内求解的方法。

单纯形算法及其变体属于边缘跟踪算法家族，之所以如此命名，是因为它们通过沿着多面体的边缘从一个顶点移动到另一个顶点来解决线性规划问题。这意味着它们的理论性能受到 LP 多胞形上任意两个顶点之间的最大边数的限制。因此，我们有兴趣了解多面图的最大图论直径。已证明所有多胞形都具有次指数直径。最近对赫希猜想的反驳是证明多面体是否具有超多项式直径的第一步。如果存在任何这样的多面体，则任何边缘跟随变体都不能在多项式时间内运行。关于多胞体直径的问题具有独立的数学意义。

单纯形枢轴方法保留了原始（或对偶）可行性。另一方面，十字枢轴方法不保留（原始或对偶）可行性——它们可能以任何顺序访问原始可行、对偶可行或原始和对偶不可行基。自 20 世纪 70 年代以来，人们就开始研究这种类型的枢轴方法。^[25] 本质上，这些方法试图在线性规划问题下找到排列多胞体上的最短主元路径。与多面体图相比，已知排列多面体图具有较小的直径，这允许强多项式时间十字主元算法的可能性，而无需解决有关一般多面体直径的问题。^[11]

整数未知数[编辑]

如果所有未知变量都要求为整数，则该问题称为整数规划（IP）或整数线性规划（ILP）问题。与在最坏情况下可以有效解决的线性规划相比，整数规划问题在许多实际情况（具有有界变量的情况）中都是NP 困难的。0-1 整数规划或二进制整数规划(BIP) 是整数规划的特殊情况，其中变量需要为 0 或 1（而不是任意整数）。这个问题也被归类为 NP 困难问题，事实上，决策版本是卡普的 21 个 NP 完全问题之一。

如果仅要求部分未知变量为整数，则该问题称为混合整数（线性）规划（MIP 或 MILP）问题。这些通常也是 NP 难的，因为它们比 ILP 程序更通用。

然而，IP 和 MIP 问题的一些重要子类是可以有效解决的，最显着的是约束矩阵完全幺模并且约束的右侧是整数的问题，或者更一般地说，系统具有总对偶完整性的问题（TDI）属性。

求解整数线性规划的高级算法包括：

剖切面法
分支定界
分支和剪切
分店及价格
如果问题有一些额外的结构，则可以应用延迟列生成。

Padberg和 Beasley 讨论了此类整数规划算法。

积分线性规划[编辑]

更多信息：整体多面体

如果实变量的线性规划具有至少一个完整的最优解，即仅由整数值组成，则称该线性规划是完整的。同样，多面体 $P=\{x\mid Ax\geq 0\}$ 如果对于所有有界可行目标函数c，线性规划被称为积分 $\{\max cx\mid x\in P\}$ 有一个最优的 $x^{*}$ 具有整数坐标。正如 Edmonds 和 Giles 在 1977 年观察到的那样，我们可以等效地说，多面体 $磷$ 如果对于每个有界可行积分目标函数c ，线性规划的最优值是积分 $\{\max cx\mid x\in P\}$ 是一个整数。

积分线性程序在组合优化的多面体方面至关重要，因为它们提供了问题的另一种表征。具体来说，对于任何问题，解的凸包都是积分多面体；如果这个多面体有一个很好/紧凑的描述，那么我们可以在任何线性目标下有效地找到最佳可行解。相反，如果我们可以证明线性规划松弛是积分的，那么它就是可行（积分）解的凸包的所需描述。

整个文献中的术语并不一致，因此应小心区分以下两个概念，

在上一节中描述的整数线性程序中，变量被强制约束为整数，并且这个问题通常是 NP 困难的，
在本节描述的积分线性规划中，变量不限于整数，而是已经以某种方式证明了连续问题总是具有积分最优值（假设c是整数），并且可以有效地找到该最优值，因为所有多项式大小的线性程序都可以在多项式时间内求解。

证明多面体是积分的一种常见方法是证明它是完全幺模的。其他通用方法还有整数分解性质和全对偶完整性方法。其他特定的众所周知的积分 LP 包括匹配多面体、晶格多面体、子模流多面体以及两个广义多拟阵/ g-多拟阵的交集- 例如参见 Schrijver 2003。

求解器和脚本（编程）语言[编辑]

许可许可：

姓名	执照	简要信息
壁虎	麻省理工学院许可证	用于解决大规模 LP、QP、QCQP、NLP和MIP优化的开源库
格洛普	阿帕奇v2	Google 的开源线性规划求解器
JuMP.jl	MPL许可证	开源建模语言，带有用于大规模 LP、QP、QCQP、SDP、SOCP、NLP和MIP优化的求解器
皮莫	BSD	用于大规模线性、混合整数和非线性优化的开源建模语言
SCIP	阿帕奇v2	一个通用约束整数规划求解器，重点是 MIP。与 Zimpl 建模语言兼容。
算术	阿帕奇v2	一套开源的优化算法，用于在 Java 中解决 LP、 QP、SOCP、SDP、SQP

Copyleft（互惠）许可证：

姓名	执照	简要信息
ALGLIB	通用公共许可证 2+	来自 ALGLIB 项目的 LP 求解器（C++、C#、Python）
食火鸡约束求解器	LGPL	增量约束求解工具包，可有效求解线性等式和不等式系统
中电	CPL	COIN-OR 的 LP 求解器
糖蛋白	通用公共许可证	GNU 线性编程套件，一个 LP/MILP 求解器，具有本机 C API和许多 (15) 个用于其他语言的第三方包装器。流网络的专家支持。捆绑类似AMPL的 GNU MathProg建模语言和翻译器。
lp_solve	LGPL v2.1	LP 和MIP求解器支持MPS 格式及其自己的“lp”格式，以及通过其“外部语言接口”(XLI) 的自定义格式。^[26]^[27]模型格式之间的转换也是可能的。^[28]
乔卡	通用公共许可证	用于增量求解具有各种目标函数的线性方程组的库
R-项目	通用公共许可证	用于统计计算和图形的编程语言和软件环境

MINTO（混合整数优化器，一种使用分支定界算法的整数规划求解器）具有公开可用的源代码^[29]，但不是开源的。

专有许可证：

姓名	简要信息
人工智能管理系统	一种建模语言，允许对线性、混合整数和非线性优化模型进行建模。它还提供了约束编程工具。还可以实现启发式或精确方法形式的算法，例如分支和剪切或列生成。该工具调用适当的求解器（例如 CPLEX 或类似的）来解决手头的优化问题。学术许可证是免费的。
ALGLIB	Copyleft 许可库的商业版本。C++、C#、Python。
AMPL	一种用于大规模线性、混合整数和非线性优化的流行建模语言，提供免费的学生限制版本（500 个变量和 500 个约束）。
分析公司	通用建模语言和交互式开发环境。其影响图使用户能够将问题表述为带有决策变量、目标和约束节点的图表。Analytica Optimizer Edition 包括线性、混合整数和非线性求解器，并选择求解器来匹配问题。它还接受其他引擎作为插件，包括XPRESS、 Gurobi 、Artelys Kninto和MOSEK。
AP监控器	MATLAB 和 Python 的 API。通过 MATLAB、Python 或 Web 界面解决示例线性规划 (LP) 问题。
CPLEX	流行的求解器，具有适用于多种编程语言的 API，还具有建模语言，并可与 AIMMS、AMPL、GAMS、MPL、OpenOpt、OPL Development Studio 和TOMLAB配合使用。免费供学术使用。
Excel求解器函数	适应电子表格的非线性求解器，其中函数评估基于重新计算的单元格。基本版本可作为 Excel 的标准插件使用。
MP堡
GAMS
古罗比优化器
IMSL 数值库	C/C++、Fortran、Java 和 C#/.NET 中提供的数学和统计算法集合。IMSL 库中的优化例程包括无约束、线性和非线性约束最小化以及线性编程算法。
林多	具有 API 的求解器，可用于大规模优化线性、整数、二次、二次曲线和一般非线性程序，并具有随机编程扩展。它提供了一个全局优化过程，用于为具有连续和离散变量的一般非线性程序找到有保证的全局最优解。它还具有统计采样 API，可将蒙特卡罗模拟集成到优化框架中。它具有代数建模语言 ( LINGO ) 并允许在电子表格中建模 ( What'sBest )。
枫	用于符号和数值计算的通用编程语言。
MATLAB	一种用于数值计算的通用且面向矩阵的编程语言。MATLAB 中的线性规划除了基本 MATLAB 产品外还需要Optimization Toolbox ；可用的例程包括 INTLINPROG 和 LINPROG
数学CAD	所见即所得的数学编辑器。它具有解决线性和非线性优化问题的功能。
数学	一种通用数学编程语言，包括符号和数值功能。
莫塞克	用于大规模优化的求解器，具有多种语言（C++、java、.net、Matlab 和 python）的 API。
NAG 数值库	由数值算法组为多种编程语言（C、C++、Fortran、Visual Basic、Java 和 C#）和软件包（MATLAB、Excel、R、LabVIEW）开发的数学和统计例程集合。NAG 库的优化章节包括用于稀疏和非稀疏线性约束矩阵的线性规划问题的例程，以及用于优化具有非线性、有界或无约束的二次、非线性、线性或非线性函数的平方和的例程。NAG 库具有用于局部和全局优化以及连续或整数问题的例程。
优化J	一种基于 Java 的优化建模语言，提供免费版本。^[30]^[31]
SAS /或	一套用于线性、整数、非线性、无导数、网络、组合和约束优化的求解器；代数建模语言OPTMODEL ；以及针对特定问题/市场的各种垂直解决方案，所有这些都与SAS 系统完全集成。
速压	适用于大规模线性规划、二次规划、一般非线性和混合整数规划的求解器。拥有适用于多种编程语言的 API，还有建模语言 Mosel，并可与 AMPL、GAMS配合使用。免费供学术使用。
可视化模拟	用于动态系统仿真的可视化框图语言。

上一条：对偶性