Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
组合优化问题公式的优点和局限性。
基本信息
- 批准号:RGPIN-2020-04346
- 负责人:
- 金额:$ 2.48万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2022
- 资助国家:加拿大
- 起止时间:2022-01-01 至 2023-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Combinatorial optimization is an important area of mathematical optimization. It captures many real-life problems. Familiar examples of such problems are developing road networks or matching users' requests with servers in an optimal way. One way to solve such problems is to develop combinatorial algorithms, but this approach is usually problem specific and not robust with respect to including additional constraints. Another way to approach such problems is to formulate them in terms of convex or integer programs. This allows us to draw from the rich theory of convex and integer programming. This strategy often turns out to be successful, especially if a compact formulation exists. Indeed, linear programs can be solved efficiently both in theory and in practice. To formulate a problem in terms of a convex or integer program we encode the feasible solutions as points in a high dimensional space, such that the function to be optimized can be expressed as a linear function on the space. We then optimize a linear function over the convex hull of these high dimensional points. For typical combinatorial problems we need an exponentially large number of linear inequalities to describe the convex hull. Sometimes no such linear formulation is known. Surprisingly, when we introduce additional variables that encode information not explicit in the original problem, linear formulation may become possible. Moreover such extended formulations may involve many fewer linear inequalities, potentially polynomially many. Positive semidefinite formulations, in which we optimize a linear function over positive semidefinite matrices, offer an even more powerful framework. In particular, extended semidefinite formulations may be even more compact compared to linear ones. Whenever we succeed in obtaining a compact formulation, we may draw on existing theory and software to provide efficient computational solutions. In the proposed research I plan to study the power and limitations of formulations of combinatorial problems, and the algorithms based on such formulations. I would especially like to explore the interconnections of convex and combinatorial optimization. Through this research, we will gain understanding of formulations for fundamental optimization problems. The strength and limitations of formulations that we establish are of tremendous importance for designing efficient computational methods for these problems. For example, the stable matching problem with ties belongs to the scope of the proposed research plan. Any new insights in formulations of this problem may lead to breakthroughs in approximating maximum cardinality stable matchings. In the current proposal we hope to develop techniques to settle these and other important open questions about formulations, tightening the connections between such areas of knowledge as theory of combinatorial and continuous optimization, game theory and graph theory.
组合优化是数学优化的一个重要领域。它捕捉到了许多现实生活中的问题。此类问题的常见示例是开发道路网络或以最佳方式将用户的请求与服务器相匹配。解决此类问题的一种方法是开发组合算法,但这种方法通常是特定于问题的,并且在包含附加约束方面不稳健。解决此类问题的另一种方法是用凸规划或整数规划来表述它们。这使我们能够借鉴凸规划和整数规划的丰富理论。这种策略通常会被证明是成功的,尤其是在存在紧凑的公式的情况下。事实上,线性规划在理论上和实践中都可以有效地求解。为了用凸规划或整数规划来表述问题,我们将可行解编码为高维空间中的点,使得要优化的函数可以表示为空间上的线性函数。然后,我们在这些高维点的凸包上优化线性函数。对于典型的组合问题,我们需要指数级数量的线性不等式来描述凸包。有时不知道这样的线性公式。令人惊讶的是,当我们引入额外的变量来编码原始问题中不明确的信息时,线性公式可能成为可能。此外,这种扩展的公式可能涉及更少的线性不等式,可能涉及很多多项式。正半定公式,我们在正半定矩阵上优化线性函数,提供了一个更强大的框架。特别是,与线性公式相比,扩展半定公式可能更加紧凑。每当我们成功获得紧凑的公式时,我们就可以利用现有的理论和软件来提供有效的计算解决方案。在拟议的研究中,我计划研究组合问题公式的威力和局限性,以及基于此类公式的算法。我特别想探索凸优化和组合优化之间的相互联系。通过这项研究,我们将了解基本优化问题的公式。我们建立的公式的强度和局限性对于为这些问题设计有效的计算方法非常重要。例如,带关系的稳定匹配问题就属于本研究计划的范围。该问题的任何新见解都可能导致近似最大基数稳定匹配方面的突破。在当前的提案中,我们希望开发技术来解决这些以及其他有关公式的重要开放问题,加强组合理论和连续优化理论、博弈论和图论等知识领域之间的联系。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
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 }}
Pashkovich, Kanstantsin其他文献
Ideal Clutters That Do Not Pack
- DOI:
10.1287/moor.2017.0871 - 发表时间:
2018-05-01 - 期刊:
- 影响因子:1.7
- 作者:
Abdi, Ahmad;Pashkovich, Kanstantsin;Cornuejols, Gerard - 通讯作者:
Cornuejols, Gerard
Pashkovich, Kanstantsin的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Pashkovich, Kanstantsin', 18)}}的其他基金
Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
组合优化问题公式的优点和局限性。
- 批准号:
RGPIN-2020-04346 - 财政年份:2021
- 资助金额:
$ 2.48万 - 项目类别:
Discovery Grants Program - Individual
Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
组合优化问题公式的优点和局限性。
- 批准号:
RGPIN-2020-04346 - 财政年份:2020
- 资助金额:
$ 2.48万 - 项目类别:
Discovery Grants Program - Individual
Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
组合优化问题公式的优点和局限性。
- 批准号:
DGECR-2020-00265 - 财政年份:2020
- 资助金额:
$ 2.48万 - 项目类别:
Discovery Launch Supplement
相似国自然基金
LAMP2-A介导的分子伴侣自噬维持卡路里限制中骨脂分化稳态的机制研究
- 批准号:82300993
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
天然免疫限制因子Tetherin抑制狂犬病病毒复制的分子机制研究
- 批准号:32302874
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
雌雄同株植物调整性分配和种子大小适应花粉限制的对策
- 批准号:32371560
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:面上项目
新疆春季低温干旱对返青期苜蓿光合活性的限制机制研究
- 批准号:32360346
- 批准年份:2023
- 资助金额:34 万元
- 项目类别:地区科学基金项目
氮限制下产油微藻油脂积累过程中光系统激发能和电子流的再分配调节机制研究
- 批准号:32301305
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
相似海外基金
Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
组合优化问题公式的优点和局限性。
- 批准号:
RGPIN-2020-04346 - 财政年份:2021
- 资助金额:
$ 2.48万 - 项目类别:
Discovery Grants Program - Individual
Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
组合优化问题公式的优点和局限性。
- 批准号:
RGPIN-2020-04346 - 财政年份:2020
- 资助金额:
$ 2.48万 - 项目类别:
Discovery Grants Program - Individual
Strengths and Limitations of Formulations for Combinatorial Optimization Problems.
组合优化问题公式的优点和局限性。
- 批准号:
DGECR-2020-00265 - 财政年份:2020
- 资助金额:
$ 2.48万 - 项目类别:
Discovery Launch Supplement
Comprehensive Study on Information Management in Civil Litigation Records and Protection of Interests of Parties
民事诉讼档案信息管理与当事人利益保护综合研究
- 批准号:
20K01414 - 财政年份:2020
- 资助金额:
$ 2.48万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
日本型憲法訴訟論の構築
构建日本式宪法诉讼理论
- 批准号:
20K01289 - 财政年份:2020
- 资助金额:
$ 2.48万 - 项目类别:
Grant-in-Aid for Scientific Research (C)