Lower bounds for binary quadratic minimization problems using nonconvex separable underestimators

点击翻译按钮获取中文摘要

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.