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

当前项目的主题是“线性规划的一种新多项式算法及其在组合和凸优化中的应用”。E1）线性规划的一个新的多项式算法。除了最优解之外，该算法还在时间O（n^4L）内找到最优面的多面体描述，其中L是实例大小，n是变量的数量。该运行时间至少与通过直接应用传统方法获得的运行时间一样好。E2）线性优化问题具有0-1最优解的强多项式算法。这是这类问题的第一个强多项式算法。该算法找到一个最优解和0-1解的最优性准则。将传统方法直接应用于该任务将导致慢得多的算法。E3）线性约束二次凸优化的多项式算法。（实例大小和log（1/e）意义上的多项式，其中e是近似误差。E4）系统Ax = B，Cx ≥ d的多项式算法，有0-1个解。这里，C是0-1矩阵，并且Cx >= d由多项式分离预言机给出。(E.g.,我们可以使用该算法来找到关于旅行推销员问题的最优值的下界，该下界至少与子环界一样好）。 开发的方法是基于我的新的投影算法。它们具有以下应用前景：指数多变量和约束的线性优化问题和拟凸优化问题。这类问题通常出现在NP难问题的背景下。该项目的延续将致力于以下主题：R1）凸和准凸优化的新算法。E2的方法可以修改，以便适用于具有准凸目标函数和线性约束的问题。R2）具有指数多变量的线性优化问题。在E2和E3中提到的算法将是一个适当的基础上，一个新的算法，这样的问题。R3）基于投影法的单纯形法的防失速主元规则。传统的主元规则可能导致停顿，特别是在组合应用中。在新的投影方法的基础上，我们可以开发出不受这种影响的单纯形法的变体。R4）数值实验。他们的目的是开发有效的实现，特别是可以用于分支定界算法。在E2中提到的强多项式算法中使用的技术使我们能够获得比通过求解线性或凸松弛最优性所获得的更好的边界。此外，该方法是能够获得最优解的结构特性。

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.