Linear programing problem in standard form
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.
- revised simplex
- dual simplex
- branch and bound
- Gomory cut
- Dantzig Wolfe Decomposition
- 0-1 knapsack problem
- minimum cost flow problem
- transportation problem
- LU update
- Sudoku as 0-1 linear programming
numpy, scipy.
- Bertsekas D. P. "Network Optimization: Continuous and Discrete Models".
- Luenberger D. G., Ye Yinyu. "Linear and Nonlinear Programming".
- 刘红英, 夏勇等. "数学规划基础".
- H.D. Mittelmann, Decision Tree for Optimization Software, http://plato.asu.edu/guide.html (2018).
- Coin-OR https://www.coin-or.org/
- cvxopt http://cvxopt.org/
- MIPLIB http://miplib.zib.de/
- MiniZinc http://www.minizinc.org/
- NEOS https://neos-server.org/neos/
- SCIP http://scip.zib.de/
- LEMON https://lemon.cs.elte.hu/trac/lemon