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

项目成果

期刊论文数量(3)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Quadratic Combinatorial Optimization Using Separable Underestimators
  • DOI:
    10.1287/ijoc.2017.0789
  • 发表时间:
    2018-06-01
  • 期刊:
  • 影响因子:
    2.1
  • 作者:
    Buchheim, Christoph;Traversi, Emiliano
  • 通讯作者:
    Traversi, Emiliano
Separable Non-convex Underestimators for Binary Quadratic Programming
  • DOI:
    10.1007/978-3-642-38527-8_22
  • 发表时间:
    2013-06
  • 期刊:
  • 影响因子:
    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
  • 期刊:
  • 影响因子:
    1.8
  • 作者:
    Buchheim;Christoph;Montenegro;Maribel;Wiegele;Angelika
  • 通讯作者:
    Angelika
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Professor Dr. Christoph Buchheim其他文献

Professor Dr. Christoph Buchheim的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Professor Dr. Christoph Buchheim', 18)}}的其他基金

Strategic planning of seaport hinterland networks with focus on LCL shipment consoldiation in gateways
以口岸拼箱集运为重点的海港腹地网络战略规划
  • 批准号:
    421917839
  • 财政年份:
    2019
  • 资助金额:
    --
  • 项目类别:
    Research Grants (Transfer Project)
Exact and heuristic algorithms for uncertain and time-dependent hub location problems based on quadratic optimization
基于二次优化的不确定且与时间相关的枢纽位置问题的精确启发式算法
  • 批准号:
    201197672
  • 财政年份:
    2011
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Two-stage optimization for planning logistics service networks
物流服务网络规划的两阶段优化
  • 批准号:
    504583220
  • 财政年份:
  • 资助金额:
    --
  • 项目类别:
    Research Grants
Convex relaxations of PDE-constrained optimization problems with combinatorial switching constraints
具有组合切换约束的偏微分方程约束优化问题的凸松弛
  • 批准号:
    468720830
  • 财政年份:
  • 资助金额:
    --
  • 项目类别:
    Research Grants

相似国自然基金

资本外逃及其逆转:基于中国的理论与实证研究
  • 批准号:
    70603008
  • 批准年份:
    2006
  • 资助金额:
    17.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

CAREER: Lower Bounds for Shallow Circuits
职业生涯:浅层电路的下限
  • 批准号:
    2338730
  • 财政年份:
    2024
  • 资助金额:
    --
  • 项目类别:
    Continuing Grant
Complexity Lower Bounds from Expansion
扩展带来的复杂性下限
  • 批准号:
    23K16837
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
Non-parametric estimation under covariate shift: From fundamental bounds to efficient algorithms
协变量平移下的非参数估计:从基本界限到高效算法
  • 批准号:
    2311072
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Towards new classes of conic optimization problems
迈向新类别的二次曲线优化问题
  • 批准号:
    23K16844
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
Branching Program Lower Bounds
分支程序下界
  • 批准号:
    RGPIN-2019-06288
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Tighter error bounds for representation learning and lifelong learning
表征学习和终身学习的更严格的误差范围
  • 批准号:
    RGPIN-2018-03942
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
AF: Small: New Techniques for Optimal Bounds on MCMC Algorithms
AF:小:MCMC 算法最优边界的新技术
  • 批准号:
    2147094
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Lower bounds, meta-algorithms, and pseudorandomness
下界、元算法和伪随机性
  • 批准号:
    RGPIN-2019-05543
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Extremal Combinatorics Exact Bounds
极值组合精确界
  • 批准号:
    574168-2022
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    University Undergraduate Student Research Awards
Lower bounds on ranks of nontrivial toric vector bundles
非平凡环面向量丛的秩下界
  • 批准号:
    558713-2021
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Postgraduate Scholarships - Doctoral
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了