Linear programming problem in standard form is

min  c * x
s.t. A * x = b,
     x >= 0.

And the dual problem is

max r * b
s.t. r * A <= c

In the integer programming, the variables must be integers.

One can add artificial variables to convert inequaltiy to equality.

e.g. A * x <= b iff A * x + s = b, s >= 0.

Let A = [B D] where B is a basis for column space, if xb = b / B and xb >= 0, then the basic solution xb is feasible. And the basic solution is actually x = [xb 0].

Let r = cb \ B, where c = [cb cd], if r * D <= cd then xb is dual feasible.

If xb is both primal and dual feasible, then it is optimum.

Solve the artificial problem for a basic solution

min  1 * s
s.t. A * x + s = b,
     x, s >= 0

If the optimum value is zero, then the problem is feasible.

1. revised simplex
2. dual simplex

1. Dantzig Wolfe Decomposition

1. branch and bound
2. Gomory cut

1. product form update

1. FT-like update

1. LU factorization for dense matrices

1. 0-1 knapsack problem

1. minimum cost flow problem

1. transportation problem

1. Sudoku as 0-1 linear programming

numpy, scipy.

1. Bertsekas D. P. "Network Optimization: Continuous and Discrete Models". 1998.
2. Duff I. S., Erisman A. M., Reid J. K. "Direct Methods for Sparse Matrices". 2017.
3. Luenberger D. G., Ye Yinyu. "Linear and Nonlinear Programming". 2008.
4. Pan Pingqi. "Linear Programming Computation". 2014. (中文版于2012年出版)
5. 刘红英, 夏勇等. "数学规划基础". 2012.

1. Huangfu Q , Hall J A J . Novel update techniques for the revised simplex method[J]. Computational Optimization & Applications, 2015, 60(3):587-608.

1. H.D. Mittelmann, Decision Tree for Optimization Software, http://plato.asu.edu/guide.html.
2. Coin-OR https://www.coin-or.org/
3. cvxopt http://cvxopt.org/
4. MIPLIB http://miplib.zib.de/
5. MiniZinc http://www.minizinc.org/
6. NEOS https://neos-server.org/neos/
7. SCIP http://scip.zib.de/
8. LEMON https://lemon.cs.elte.hu/trac/lemon