A polynomial projection algorithm for linear feasibility problems
A polynomial projection algorithm for linear feasibility problems
复制标题
DOI：
10.1007/s10107-014-0823-8
复制
发表时间：
2015-11-01
影响因子：
2.7
通讯作者：
Chubanov, Sergei
中科院分区：
文献类型：
--
作者：
Chubanov, Sergei
我们提出了一种用于线性可行性问题的多项式算法。该算法用线性方程和非负约束的形式表示线性问题。然后，它使用一个程序，该过程要么找到针对各自均匀系统的解决方案，要么提供基于算法重新统一系统的信息，以使其在单位立方体中的可行解决方案更接近所有载体的向量。在对该过程的多项式调用中，算法证明原始系统是不可行的，或者在可行集合的相对内部找到了解决方案。
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.