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 算法）来解决。到目前为止，我们开发了一种新的生成树问题。二次组合优化问题的精确解的方法，特别适用于当潜在的线性问题易于处理或至少可以很好地近似时。对于给定的二次目标函数不做任何假设，特别是它不应该是凸的或稀疏的。我们方法的想法是通过可分离的二次函数低估目标函数（在最小化问题的情况下）。通过给定变量的二元性，后者等价于线性目标函数。由此产生的线性优化问题的最优值产生原始二次问题的下界。通过将此方法嵌入到分支定界方案中，我们获得了原始问题的精确算法。这种方法的一个重要优点是所产生的线性问题可以通过任意算法来解决，特别是可以使用组合算法。线性优化问题的求解器在我们的方法中被视为黑匣子。在项目的后续过程中，我们将重点关注这些方法在运行时间方面的改进。我们将为计算最佳低估量所需的半定程序开发一个特定问题的求解器。此外，我们将研究如何针对特定组合问题放宽可分离性要求以获得更严格的界限的问题。我们项目的最终目标是一种算法方法，一方面，只需添加相应的黑盒即可直接应用于各种二次组合优化问题。另一方面，在计算低估量时利用特定组合问题的结构，我们的目标是更快地解决特定问题。