课题基金 / 基金详情

Lower bounds for binary quadratic minimization problems using nonconvex separable underestimators

Lower bounds for binary quadratic minimization problems using nonconvex separable underestimators
使用非凸可分离低估量的二元二次最小化问题的下界
批准号:
231686800
负责人:
Professor Dr. Christoph Buchheim
金额:
$0.0万
依托单位国家:
德国
项目类别:
Research Grants
财政年份:
2012
资助国家:
德国
项目状态:
已结题
起止时间:
2011-12-31 至 2016-12-31

项目摘要

项目成果

Professor Dr. Christoph Buchheim的其他基金

相似基金

相关文献

中文摘要
翻译
该项目关注的是经典组合优化问题的二次变量的解决方案。这样的问题通常是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.
期刊论文(3)
专著(0)
科研奖励(0)
会议论文
DOI: 10.1287/ijoc.2017.0789
发表时间: 2018-06-01
期刊: INFORMS JOURNAL ON COMPUTING
影响因子: 2.1
作者: [Buchheim, Christoph, Traversi, Emiliano]
通讯作者: Traversi, Emiliano
DOI: 10.1007/978-3-642-38527-8_22
发表时间: 2013-06
期刊: Mathematical Programming
影响因子: 2.7
作者: [C. Buchheim;Emiliano Traversi]
通讯作者: C. Buchheim;Emiliano Traversi
SDP-based branch-and-bound for non-convex quadratic integer optimization
基于 SDP 的分支定界非凸二次整数优化
DOI: 10.1007/s10898-018-0717-z
发表时间: 2019
期刊: Journal of Global Optimization
影响因子: 1.8
作者: [Buchheim, Christoph, Montenegro, Maribel, Wiegele, Angelika]
通讯作者: Angelika
Strategic planning of seaport hinterland networks with focus on LCL shipment consoldiation in gateways
  • 批准号:
    421917839
  • 项目类别:
    Research Grants (Transfer Project)
  • 资助金额:
    $0.0万
  • 财政年份:
    2019
  • 负责人:
    Professor Dr. Christoph Buchheim
  • 依托单位:
Exact and heuristic algorithms for uncertain and time-dependent hub location problems based on quadratic optimization
  • 批准号:
    201197672
  • 项目类别:
    Research Grants
  • 资助金额:
    $0.0万
  • 财政年份:
    2011
  • 负责人:
    Professor Dr. Christoph Buchheim
  • 依托单位:
Two-stage optimization for planning logistics service networks
  • 批准号:
    504583220
  • 项目类别:
    Research Grants
  • 资助金额:
    $0.0万
  • 财政年份:
    --
  • 负责人:
    Professor Dr. Christoph Buchheim
  • 依托单位:
Convex relaxations of PDE-constrained optimization problems with combinatorial switching constraints
国内基金
海外基金
资本外逃及其逆转:基于中国的理论与实证研究
  • 批准号:
    70603008
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    17.0万元
  • 批准年份:
    2006
  • 负责人:
    牛晓健
  • 依托单位: