A new polynomial relaxation-type algorithm for linear programming with applications in combinatorial and convex optimization

• Applicant: Privatdozent Dr. Sergei Chubanov
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 214066775

• Final Report Year: 2016

Final Report Abstract

In this project I have developed two polynomial algorithms for linear programming and for some more general classes of convex problems. These algorithms can be used to solve linear feasibility problems or to accomplish some special tasks such as tightening the search space in the context of branch-and-bound algorithms. One of the algorithms developed in the project is a new and more efficient version of an algorithm I have previously developed. The theoretical running time was improved by a factor of the square of the number of variables compared to the previous algorithm. The work on the project has also led to new complexity results in linear programming. For instance, one of the proposed algorithms is able to solve a fairly general class of linear optimization problems in strongly polynomial time, i.e., in polynomial time which only depends on the number of variables and constraints and is not sensitive to the sizes of the numbers representing the problem. This substantially extends the class of linear problems known to be solvable in strongly polynomial time. In particular, one of the well-known results on strongly polynomial solvability of a class of the stochastic Markov Decision Problem is a subset of this result. One of the methods developed in this project leads to new polynomial algorithms for a class of combinatorial problems. Also, this method is a fully polynomial-time approximation scheme for linear optimization problems over polyhedra of blocking type given by a separation oracle. The proposed algorithms can have a much wider range of application than only finitedimensional linear problems; both methods have a clear perspective in linear programming in infinite-dimensional spaces, e.g., they are applicable to flow over time problems.

Publications

• A strongly polynomial algorithm for linear systems having a binary solution. Mathematical Programming 134: 533-570, 2012
  Chubanov, S
  
• A strongly polynomial algorithm for linear optimization problems having 0-1 optimal solutions. Optimization Online 1 (4194), 2014
  Chubanov, S
  
• A polynomial projection algorithm for linear feasibility problems. Mathematical Programming 153: 687-713, 2015
  Chubanov, S