The dual face algorithm for linear programming (LP) was proposed by the author in 2014. Using QR factorization, it proceeds from dual face to dual face, until reaching an optimal dual face along with dual and primal optimal solutions, unless detecting infeasibility of the problem. On the other hand, a variant of the algorithm using LU factorization was presented, but it is for specialized LP problems only. To break the barriers, this paper proposes a new dual face algorithm using LU factorization for standard LP problems. Surprisingly enough, it turns out that this algorithm and the face algorithm \cite{pan20} just proposed are a pigeon pair. Like the latter, the former also has salient features of its own, and is even more attractive.
Citation
Southeast University, Nanjing 210096
Article
View A New Dual Face Algorithm Using LU Factorization for Linear Programming