Lower bounds for binary quadratic minimization problems using nonconvex separable underestimators

该项目涉及经典组合优化问题的二次变量的求解。这样的问题通常是NP难的，即使在相同的可行集上进行线性优化是可能的。作为一个例子，二次生成树问题在理论上和实践中都很难解决，而这个问题的线性对应问题可以用众所周知的非常快速的算法来求解，如Kruskal算法。到目前为止，我们发展了一种新的方法来求解二次组合优化问题的精确解，特别适用于潜在的线性问题是可处理的或至少可以很好地逼近的情况。对于给定的二次目标函数不作任何假设，特别是不假定它是凸的或稀疏的，我们的方法的思想是用一个可分离的二次函数来低估目标函数(在最小化问题的情况下)。通过给定变量的二值化，后者等价于一个线性目标函数。由此得到的线性优化问题的最优值产生了原始二次问题的下界。通过将该方法嵌入到分支定界格式中，我们得到了原问题的精确算法。这种方法的一个重要优点是，所得到的线性问题可以用任意算法来求解，特别是可以使用组合算法。在我们的方法中，线性优化问题的求解器被视为一个黑箱。在项目的进一步过程中，我们将重点关注这些方法在所产生的运行时间方面的改进。我们将为计算最优低估数所需的半定程序开发一个特定于问题的求解器。此外，我们还将研究如何针对特定的组合问题放宽可分性的要求，以获得更严格的界。我们项目的最终目标是一种算法方法，一方面，只需添加相应的黑盒，就可以直接应用于一大类二次组合优化问题。另一方面，在计算低估因子时，利用特定组合问题的结构，我们的目标是对特定问题进行更快的求解。

The project is concerned with the solution of quadratic variants of classical combinatorial optimization problems. Such problems are generally NP-hard, even if linear optimization over the same feasible set is possible efficiently. As an example, the quadratic spanning tree problem is very hard to solve in theory and in practice, while the linear counterpart of this problem can be solved by well-known and very fast algorithms such as Kruskal's algorithm.So far, we developped a new approach for the exact solution of quadratic combinatorial optimization problems that is applicable in particular when the underlying linear problem is tractable or can at least be approximated well. No assumptions are made concerning the given quadratic objective function, in particular, it is not supposed to be convex or sparse.The idea of our approach is to underestimate the objective function (in case of a minimization problem) by a separable quadratic function. By the binarity of the given variables, the latter is equivalent to a linear objective function. The optimal value of the resulting linear optimization problem thus yields a lower bound for the original quadratic problem. By embedding this approach into a branch-and-bound scheme, we obtain an exact algorithm for the original problem. An important advantage of this approach is that the resulting linear problems can be solved by an arbitrary algorithm, in particular, combinatorial algorithms can be used. The solver for the linear optimization problem is considered a black box in our approach.In the further course of the project, we will focus on the improvement of these methods in terms of the resulting running times. We will develop a problem-specific solver for the semidefinite programs needed to compute optimal underestimators. Moreover, we will investigate the question how the requirement of separability can be relaxed for specific combinatorial problems in order to obtain tighter bounds. The ultimate objective of our project is an algorithmic approach that, on one hand, can be applied directly for a wide class of quadratic combinatorial optimization problems by just adding the corresponding black box. On the other hand, exploiting the structure of specific combinatorial problems when computing underestimators, we aim at even faster solution for particular problems.