Linear Programming

Introduction

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.

Artificial Variable

One can add artificial variables to convert inequaltiy to equality.

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

Basic Solution

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.

Two Phrase Method

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.

Algorithm

simplex.py

1. revised simplex
2. dual simplex

decomposition.py

1. Dantzig Wolfe Decomposition

bnb

branch_cut.py

1. branch and bound
2. Gomory cut

LU

pf_update.py

1. product form update

ft_update.py

1. FT-like update

dense.py

1. LU factorization for dense matrices

Graph

dynamic.py

1. 0-1 knapsack problem

network_simplex.py

1. minimum cost flow problem

transport.py

1. transportation problem

Modeling

sudoku.py

1. Sudoku as 0-1 linear programming

Dependency

numpy, scipy.

Reference

Books

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.

Papers

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

Further

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