整数规划 [编辑]
要求所有的未知量都为整数的线性规划问题叫做整数规划 (integer programming, IP) 或整数线性规划 (integer linear programming, ILP) 问题。 相对于即使在最坏情况下也能有效率地解出的线性规划问题，整数规划问题的最坏情况是不确定的，在某些实际情况中（有约束变量的那些）为NP困难问题。
0-1 整数规划是整数规划的特殊情况，所有的变量都要是0或1（而非任意整数）。这类问题亦被分类为NP困难问题。
只要求当中某几个未知数为整数的线性规划问题叫做混合整数规划 (mixed integer programming, MIP) 问题。这类问题通常亦被分类为NP困难问题。
存在着几类 IP 和 MIP 的子问题，它们可以被有效率地解出，最值得注意的一类是具有完全单位模约束矩阵，和约束条件的右边全为整数的一类。
一个解决大型整数线性规划问题的先进算法为 delayed column generation。
参见 [编辑]
- 单纯形法，一种用于线性规划问题求解的常用方法
- Leonid Kantorovich was one of
founders of linear programming - 影子价格
- MPS file format
- LP example, Job Shop problem
参考 [编辑]
- Alexander Schrijver: "Theory of Linear and Integer Programming". John Wiley and Sons. 1998.
- Thomas H. Cormen, Charles
E. Leiserson, Ronald L. Rivest, and Clifford
Stein. Introduction to Algorithms,
Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter
29: Linear Programming, pp.770–821. - Michael R.
Garey and David S. Johnson. Computers
and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. 1979. ISBN
0716710455. A6:
MP1: INTEGER PROGRAMMING, pg.245.
外部链接 [编辑]
- Guidance on Formulating LP problems
- 0-1 Integer Programming Benchmarks with Hidden
Optimum Solutions - COIN-OR- Open Source Library for linear programming
- Cplex - Commercial library for linear programming
- Xpress-MP - Optimization software free to students
- MOSEK - Optimization software for LP, QP, MIP, SOCP and more
- A Tutorial on Integer Programming
- The linear programming FAQ
求解软件包
- AIMMS — include linear programming in industry solutions
(free trial license available); - COIN-OR — COmputational INfrastructure for Operations Research, open-source library
- Cplex — Commercial library for linear programming
- HOPDM — Higher Order Primal Dual Method
- LINDO — LP, IP, Global solver/modeling language
- LiPS — Free easy-to-use program intended for solving linear,
integer and goal programming problems. - lp_solve
- MOSEK — Optimization software for LP, QP, MIP, SOCP and more
- Premium Solver — Spreadsheet add-in
- What's Best! — Spreadsheet add-in
- Xpress-MP — Optimization software free to students
- GIPALS — Linear programming environment and dynamic link library (DLL)
- DecisionPro Linear Programming
Optimization Software - QSopt Optimization software for LP (free for research purposes).
- Microarray Data Classification Server (MDCS) based on linear programming
- Linear programming and linear goal programming A freeware program
for MS-DOS - Simplex Method Tool A quick-loading
web page