Linear Programming Revisited

初次接触线性规划好像还是初中的时候。那时还不知道原来LP是一个这么NB的东西，可以用来解生活中如此多的问题。
在运筹学、优化、算法中都能见到它的身影。关于它，我重新认识到了几点东西：

1.LP有多项式的算法。因此，如果一个问题被形式化为一个多项式规模的LP，则它可以用椭圆法或内点法在多项式时间内解决。
并且可以使用一些LP的软件包（CPLEX,glpk等）高校地解决问题。

2.LP不是灵丹妙药。算法导论说：为一个特别问题设计的一个有效的算法，
譬如用于单源最短路问题的Dijkstra算法，或者最大流的push-relabel方法，经常在理论和实践中都比LP更有效。

3.线性规划的真正力量在于其求解新问题的能力。真实世界中，充满了LP可解的各种问题。LP同时也对各种我们没有已知有效算法的问题特别有用。

4.我的命题与暂时的理解（证明）
命题：如果一个问题能formalize成多项式个限制的LP，则它必然不是NPC问题。（不知道这个是不是证明NP=P的一个途径之一……）

后来查阅资料得知，现在解决LP的多项式方法，包括椭圆法和内点法，都是weakly polynomial time的，即算法执行时间依赖输入的值的大小，如k=input value，复杂度是O(nk)。当k的值是指数级，O(nk)是指数级的。以上论断不正确。

另外，平时解的很多问题，是整数规划（包括0-1规划）或者混合规划，它们都是NP-hard的，而普通的线性规划却有有效的多项式解法（即上述所提的椭圆法，内点法。