Linear Program Solving Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Text replacement - ". ----" to ". ----") |
m (Text replacement - "]] *** " to "]]. *** ") |
||
Line 37: | Line 37: | ||
**** [[Dantzig–Wolfe decomposition]] | **** [[Dantzig–Wolfe decomposition]] | ||
**** [[Theory of two-level planning]] | **** [[Theory of two-level planning]] | ||
**** [[Variable splitting]] | **** [[Variable splitting]]. | ||
*** [[Basic solution (linear programming)]] — solution at vertex of feasible region | *** [[Basic solution (linear programming)]] — solution at vertex of feasible region | ||
*** [[Fourier–Motzkin elimination]] | *** [[Fourier–Motzkin elimination]]. | ||
*** [[Hilbert basis (linear programming)]] — set of integer vectors in a convex cone which generate all integer vectors in the cone | *** [[Hilbert basis (linear programming)]] — set of integer vectors in a convex cone which generate all integer vectors in the cone | ||
*** [[LP-type problem]] | *** [[LP-type problem]]. | ||
*** [[Linear inequality]] | *** [[Linear inequality]]. | ||
*** [[Vertex enumeration problem]] — list all vertices of the feasible set | *** [[Vertex enumeration problem]] — list all vertices of the feasible set | ||
Revision as of 00:44, 24 July 2023
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