单纯形算法利用多面体的顶点构造一个可能的解，然后沿着多面体的边走到目标函数值更高的另一个顶点，直至到达最优解为止。虽然这个算法在实际上很有效率，在小心处理可能出现的“循环”的情况下，可以保证找到最优解，但它的最坏情况可以很坏：可以构筑一个线性规划问题，单纯形算法需要问题大小的指数倍的运行时间才能将之解出。事实上，有一段时期内人们曾不能确定线性规划问题是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。尽管在理论上对它所知甚少，在实际应用中它却表现出色。
单形法沿着边界由一个顶点移动到“相邻”的顶点，内点算法每一步的移动考量较周详，“跨过可行解集合的内部”去逼近最佳解。当今的观点是：对于线性规划的日常应用问题而言，如果算法的实现良好，基于单纯形法和内点法的算法之间的效率没有太大差别，只有在超大型线性规划中，顶点几成天文数字，内点法有机会领先单形法。
线性规划的求解程式在各种各样的工业最优化问题里被广泛使用，例如运输网络的流量的最优化问题，其中很多都可以不太困难地被转换成线性规划问题。
线性规划理论中存在几个尚未解决的问题，这些开放问题的答案将会是数学运算中的根本突破，并且很可能是我们解决大规模线性规划问题的主要进展。
LP存在强多项式时间算法吗？
LP存在多项式时间算法以得到一个严格互补解吗"list-dot list-dot-paddingleft">
LP在实数（单位成本）模型下存在多项式时间算法吗"para" label-module="para">
这些问题已经由斯蒂芬·斯梅尔在二十一世纪十八个尚未解决的最伟大的问题中应用。用斯梅尔的话来说，“第三个问题是线性规划理论中最主要的尚未解决的问题”。然而，对于线性规划问题存在弱多项式时间算法，比如椭球算法和内点算法，尚未发现限制在约束条件个数和变量个数的强多项式时间算法，此算法的发展将会带来理论上重大意义，或者是解决大规模线性规划上的实际收益。
要求所有的未知量都为整数的线性规划问题叫做整数规划（integer programming, IP）或整数线性规划（integer linear programming, ILP）问题。相对于即使在最坏情况下也能有效率地解出的线性规划问题，整数规划问题的最坏情况是不确定的，在某些实际情况中（有约束变量的那些）为NP困难问题。
0-1整数规划是整数规划的特殊情况，所有的变量都要是0或1（而非任意整数）。这类问题亦被分类为NP困难问题 。
只要求当中某几个未知数为整数的线性规划问题叫做混合整数规划（mixed integer programming, MIP）问题。这类问题通常亦被分类为NP困难问题。
存在着几类IP和MIP的子问题，它们可以被有效率地解出，最值得注意的一类是具有完全单位模约束矩阵，和约束条件的右边全为整数的一类。
一个解决大型整数线性规划问题的先进算法为delayed column generation。2100433B
