Linear Program Solving Algorithm
Jump to navigation
Jump to search
A Linear Program Solving Algorithm is a continuous optimization algorithm that can be implemented by a linear programming system (to solve a linear programming task).
- Context:
- It can be a Binary Linear Programming Algorithm.
- It can range from being an Iterative Linear Programming Algorithm to being a ...
- Example(s):
- Counter-Example(s):
- See: Dynamic Programming Algorithm Strategy, Matrix Factorization, Linear Programming Relaxation, Column Generation.
References
2016
- (Wikipedia, 2016) ⇒ http://wikipedia.org/wiki/list_of_numerical_analysis_topics#Linear_programming Retrieved:2016-4-4.
- Linear programming (also treats integer programming) — objective function and constraints are linear
- Algorithms for linear programming:
- Simplex algorithm
- Bland's rule — rule to avoid cycling in the simplex method
- Klee–Minty cube — perturbed (hyper)cube; simplex method has exponential complexity on such a domain
- Criss-cross algorithm — similar to the simplex algorithm
- Big M method — variation of simplex algorithm for problems with both "less than" and "greater than" constraints
- Interior point method
- Column generation
- k-approximation of k-hitting set — algorithm for specific LP problems (to find a weighted hitting set)
- Simplex algorithm
- Linear complementarity problem
- Decompositions:
- Basic solution (linear programming) — solution at vertex of feasible region
- Fourier–Motzkin elimination.
- Hilbert basis (linear programming) — set of integer vectors in a convex cone which generate all integer vectors in the cone
- LP-type problem.
- Linear inequality.
- Vertex enumeration problem — list all vertices of the feasible set
- Algorithms for linear programming:
- Linear programming (also treats integer programming) — objective function and constraints are linear