Linear Programming Algorithm: Difference between revisions

From GM-RKB
Jump to navigation Jump to search
m (Text replacement - " ⇒ " to " ⇒ ")
(Redirected page to Linear Program Solving Algorithm)
Tag: New redirect
 
Line 1: Line 1:
A [[Linear Programming Algorithm]] is an [[continuous optimization algorithm]] that can be implemented by a [[linear programming system]] (to solve a [[linear programming task]]).
#REDIRECT [[Linear Program Solving Algorithm]]
* <B>Context</U>:</B>
** It can be a [[Binary Linear Programming Algorithm]].
** It can range from being an [[Iterative Linear Programming Algorithm]] to being a ...
* <B>Example(s):</B>
** a [[Simplex Algorithm]].
** a [[Gaussian Elimination Algorithm]].
** an [[Interior Point Optimization Algorithm]].
* <B>Counter-Example(s):</B>
** [[Non-Linear Programming Algorithm]], such as a [[quadratic programming algorithm]].
* <B>See:</B> [[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]]
*****[[Ellipsoid method]]
*****[[Karmarkar's algorithm]]
*****[[Mehrotra predictor–corrector method]]
****[[Column generation]]
****[[k-approximation of k-hitting set]] — algorithm for specific LP problems (to find a weighted hitting set)
***[[Linear complementarity problem]]
***Decompositions:
****[[Benders' decomposition]]
****[[Dantzig–Wolfe decomposition]]
****[[Theory of two-level planning]]
****[[Variable splitting]]
***[[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
 
----
[[Category:Concept]]
__NOTOC__

Latest revision as of 17:07, 31 March 2019