A polynomial projection algorithm for linear feasibility problems.

*(English)*Zbl 1327.90102Summary: We propose a polynomial algorithm for linear feasibility problems. The algorithm represents a linear problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure which either finds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the homogeneous system so that its feasible solutions in the unit cube get closer to the vector of all ones. In a polynomial number of calls to the procedure the algorithm either proves that the original system is infeasible or finds a solution in the relative interior of the feasible set.

##### MSC:

90C05 | Linear programming |

##### Software:

LIPSOL
PDF
BibTeX
XML
Cite

\textit{S. Chubanov}, Math. Program. 153, No. 2 (A), 687--713 (2015; Zbl 1327.90102)

Full Text:
DOI

##### References:

[1] | Agmon, Sh.: The relaxation method for linear inequalities. Can. J. Math. 6, 382-392 (1954) · Zbl 0055.35001 |

[2] | Chubanov, S, A strongly polynomial algorithm for linear systems having a binary solution, Math. Program., 134, 533-570, (2012) · Zbl 1268.90029 |

[3] | Dantzig, G.: An \(ε \)-precise feasible solution to a linear program with a convexity constraint in \(1/ε ^2\) iterations independent of problem size. Tech. rep. SOL 92-5 (1992) · Zbl 0654.90050 |

[4] | Edmonds, J, Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Stand., 71 B, 241-245, (1967) · Zbl 0178.03002 |

[5] | Goffin, JL, The relaxation method for solving systems of linear inequalities, Math. Oper. Res., 5, 388-414, (1980) · Zbl 0442.90051 |

[6] | Goffin, JL, On the non-polynomiality of the relaxation method for systems of linear inequalities, Math. Program., 22, 93-103, (1982) · Zbl 0473.90051 |

[7] | Hager, WW, Updating the inverse of a matrix, SIAM Rev., 31, 221-239, (1989) · Zbl 0671.65018 |

[8] | Karmarkar, N, A new polynomial-time algorithm for linear programming, Combinatorica, 4, 353-395, (1984) · Zbl 0557.90065 |

[9] | Khachiyan, L.G.: A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR 244 (English translation: Soviet Math. Dokl. 20, 191-194) (1979) · Zbl 0414.90086 |

[10] | Mehrotra, S, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047 |

[11] | Motzkin, Th., Schoenberg, I.J.: The relaxation method for linear inequalities. Can. J. Math. 6, 393-404 (1954) · Zbl 0055.35002 |

[12] | Renegar, J, A polynomial-time algorithm, based on newton’s method, for linear programming, Math. Program., 40, 59-93, (1988) · Zbl 0654.90050 |

[13] | Roos, C.: Speeding up Chubanov’s method for solving a homogeneous inequality system. Optimization Online, Report 2013-100, TU Delft, NL, September (2013) · Zbl 1268.90029 |

[14] | Stiemke, E, Über positive Lösungen homogener linearer gleichungen, Math. Ann., 76, 340-342, (1915) · JFM 45.0168.04 |

[15] | Todd, M, The many facets of linear programming, Math. Program., 91, 417-436, (2002) · Zbl 1030.90051 |

[16] | Zhang, Y.: Solving Large-Scale Linear Programs by Interior-point Methods Under the MATLAB Environment. Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD (1995) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.