整数规划是从1958年由R.E.戈莫里提出 割平面法 之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。现今比较成功又流行的方法是分支定界法和割平面法，它们都是在上述框架下形成的。

整数规划又分为：

1、 纯整数规划 ：所有决策变量均要求为整数的整数规划

2、 混合整数规划 ：部分决策变量均要求为整数的整数规划

3、纯0－1整数规划：所有决策变量均要求为0－1的整数规划

4、混合0－1规划：部分决策变量均要求为0－1的整数规划

整数规划与线性规划不同之处只在于增加了整数约束。不考虑整数约束所得到的线性规划称为整数规划的线性松弛模型。

单纯形算法 利用多面体的顶点构造一个可能的解，然后沿着多面体的边走到目标函数值更高的另一个顶点，直至到达最优解为止。虽然这个 算法 在实际上很有效率，在小心处理可能出现的“循环”的情况下，可以保证找到最优解，但它的最坏情况可以很坏：可以构筑一个线性规划问题，单纯形算法需要问题大小的指数倍的运行时间才能将之解出。事实上，有一段时期内人们曾不能确定线性规划问题是 NP完全问题 还是可以在 多项式时间 里解出的问题。

第一个在最坏情况具有多项式时间复杂度的线性规划算法在1979年由前苏联数学家Leonid Khachiyan提出。这个算法建基于 非线性规划 中Naum Shor发明的 椭球法 （ellip-soid method），该法又是Arkadi Nemirovski（2003年冯‧诺伊曼运筹学理论奖得主）和D. Yudin的凸集最优化椭球法的一般化。

理论上，“椭球法”在最恶劣的情况下所需要的计算量要比“单形法”增长的缓慢，有希望用之解决超大型线性规划问题。但在实际应用上，Khachiyan的算法令人失望：一般来说，单纯形算法比它更有效率。它的重要性在于鼓励了对 内点算法 的研究。内点算法是针对单形法的“边界趋近”观念而改采“内部逼近”的路线，相对于只沿着可行域的边沿进行移动的单纯形算法，内点算法能够在可行域内移动。

1984年，贝尔实验室印度裔数学家卡马卡（Narendra Karmarkar）提出了投影尺度法（又名Karmarkar's algorithm）。这是第一个在理论上和实际上都表现良好的算法：它的最坏情况仅为多项式时间，且在实际问题中它比单纯形算法有显著的效率提升。自此之后，很多内点算法被提出来并进行分析。一个常见的内点算法为Mehrotra predictor-corrector method。尽管在理论上对它所知甚少，在实际应用中它却表现出色。

单形法沿着边界由一个顶点移动到“相邻”的顶点，内点算法每一步的移动考量较周详，“跨过可行解集合的内部”去逼近最佳解。当今的观点是：对于线性规划的日常应用问题而言，如果算法的实现良好，基于单纯形法和内点法的算法之间的效率没有太大差别，只有在超大型线性规划中，顶点几成天文数字，内点法有机会领先单形法。

线性规划的求解程式在各种各样的工业最优化问题里被广泛使用，例如运输网络的流量的最优化问题，其中很多都可以不太困难地被转换成线性规划问题。

整数规划 0—1规划

0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何 有界 变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种 非线性规划 问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用 匈牙利方法 就比较方便。