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

The topic of the current project is "A new polynomial algorithm for linear programming with applications in combinatorial and convex optimization ". The already achieved results: E1) A new polynomial algorithm for linear programming. Besides an optimal solution, the algorithm finds a polyhedral description of the optimal face in time O(n^4L), where L is the instance size and n is the number of variables. This running time is at least as good as the running time obtained by a direct application of traditional methods. E2) A strongly polynomial algorithm for linear optimization problems with 0-1 optimal solutions. This is the first strongly polynomial algorithm for this class of problems. The algorithm finds an optimal solution and an optimality criterion for 0-1 solutions. A direct application of traditional methods to this task would lead to a much slower algorithm. E3) A polynomial algorithm for quadratic convex optimization with linear constraints. (Polynomial in the sense of the instance size and log(1/e), where e is an approximation error.) E4) A polynomial algorithm for systems Ax = b, Cx >= d, having 0-1 solutions. Here, C is a 0-1 matrix, and Cx >= d is given by a polynomial separation oracle. (E.g., we can use this algorithm to find a lower bound on the optimal value of the traveling-salesman problem which is at least as good as the subtour bound.) The developed methods are based on my new projection algorithms. They have the following perspectives of application: Linear optimization problems with exponentially many variables and constraints and quasi-convex optimization problems. Such problems arise often in the context of NP-hard problems. The continuation of the project will be dedicated to the following topics: R1) New algorithms for convex and quasi-convex optimization. The method of E2 can be modified so as to be applicable to problems with quasi-convex objective functions and linear constraints. R2) Linear optimization problems with exponentially many variables. The algorithms mentioned in E2 and E3 will be an appropriate basis for a new algorithm for such problems. R3) Anti-stalling pivot rules for the simplex method on the basis of the projection methods. Traditional pivot rules can lead to stalling, especially in combinatorial applications. On the basis of the new projection methods we can develop variants of the simplex method that are free of this effect. R4) Numerical experiments. Their purpose is to develop effective implementations that can in particular be used in branch-and-bound algorithms. The technique used in the strongly polynomial algorithm mentioned in E2 allows us to obtain better bounds than those obtained by solving linear or convex relaxations to optimality. Moreover, the method is able to derive structural properties of optimal solutions.

• DFG Programme: Research Grants