A polynomial projection algorithm for linear feasibility problems

DOI10.1007/s10107-014-0823-8zbMath1327.90102OpenAlexW2040392433MaRDI QIDQ747780

Sergei Chubanov

Publication date: 19 October 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-014-0823-8

zbMATH Keywords

linear programmingpolynomial algorithmsystems of linear inequalities

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items (21)

Implementation of a projection and rescaling algorithm for second-order conic feasibility problems ⋮ Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems ⋮ A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ Rescaled Coordinate Descent Methods for Linear Programming ⋮ Solving conic systems via projection and rescaling ⋮ A new extension of Chubanov's method to symmetric cones ⋮ Rescaling Algorithms for Linear Conic Feasibility ⋮ Computational Complexity of Atomic Chemical Reaction Networks ⋮ An extension of Chubanov's algorithm to symmetric cones ⋮ An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming ⋮ An improved version of Chubanov's method for solving a homogeneous feasibility problem ⋮ A note on submodular function minimization by Chubanov's LP algorithm ⋮ A Polynomial-Time Descent Method for Separable Convex Optimization Problems with Linear Constraints ⋮ A Data-Independent Distance to Infeasibility for Linear Conic Systems ⋮ A polynomial algorithm for convex quadratic optimization subject to linear inequalities ⋮ Enhanced basic procedures for the projection and rescaling algorithm ⋮ Method of Alternating Contractions and Its Applications to Some Convex Optimization Problems ⋮ Computational performance of a projection and rescaling algorithm ⋮ Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems ⋮ Generation of interior points and polyhedral representations of cones in \(\mathbb R^N\) cut by \(M\) planes sharing a common point

Uses Software

• LIPSOL

Cites Work

• Unnamed Item
• A strongly polynomial algorithm for linear systems having a binary solution
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• The many facets of linear programming
• Updating the Inverse of a Matrix
• The Relaxation Method for Solving Systems of Linear Inequalities
• On the non-polynomiality of the relaxation method for systems of linear inequalities
• On the Implementation of a Primal-Dual Interior Point Method
• Systems of distinct representatives and linear algebra
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities

This page was built for publication: A polynomial projection algorithm for linear feasibility problems