Linear Program Solving Algorithm

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):
  • a Simplex Algorithm.
  • a Gaussian Elimination Algorithm.
  • an Interior Point Optimization Algorithm.
  • …
• Counter-Example(s):
  • Non-Linear Programming Algorithm, such as a quadratic programming algorithm.
• 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.
        • 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

---