Lower bounds for binary quadratic minimization problems using nonconvex separable underestimators

使用非凸可分离低估量的二元二次最小化问题的下界

基本信息

批准号：
231686800
负责人：
Professor Dr. Christoph Buchheim
金额：
--
依托单位：
Lehrstuhl V, Diskrete Optimierung
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2012
资助国家：
德国
起止时间：
2011-12-31 至 2016-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/231686800?language=en
关键词：
Lower bounds binary quadratic minimization

项目摘要

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.

该项目与经典组合优化问题的二次变体有关。即使对同一可行集合的线性优化是有效的，这些问题通常是NP-固定的。例如，在理论上和实践中很难解决二次跨越树问题，而这个问题的线性对应物可以通过诸如Kruskal的算法等众所周知且非常快的算法来解决。到目前为止，我们开发了一种新的方法，即至少在近似于限制问题的问题上，尤其是Quadratic组合优化问题的确切解决方案。没有关于给定的二次目标函数的假设，尤其是不应该是凸或稀疏的。通过给定变量的二进制，后者等同于线性目标函数。因此，所得线性优化问题的最佳值为原始二次问题产生了下限。通过将这种方法嵌入分支和结合方案中，我们获得了原始问题的精确算法。这种方法的一个重要优点是，可以通过任意算法来解决所得的线性问题，尤其是可以使用组合算法。线性优化问题的求解器被认为是我们方法中的黑匣子。在项目的进一步过程中，我们将重点关注这些方法的改进。我们将为计算最佳低估所需的半决赛程序开发特定问题的求解器。此外，我们将调查一个问题，如何放宽特定组合问题的可分离性要求，以获得更紧密的范围。我们项目的最终目标是一种算法方法，一方面，可以通过添加相应的黑匣子直接应用于宽类二次组合优化问题。另一方面，在计算低估器时利用特定组合问题的结构，我们旨在更快地解决特定问题的解决方案。