Advancing Fractional Combinatorial Optimization: Computation and Applications

推进分数组合优化：计算和应用

• 批准号: 1818700
• 负责人: Andres Gomez
• 金额: $ 15万
• 依托单位: University of Pittsburgh
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-09-01 至 2021-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1818700&HistoricalAwards=false
• 关键词: Advancing; Fractional; Combinatorial; Optimization; Computation

Single- and multiple-ratio fractional combinatorial optimization problems naturally arise in diverse application contexts when modeling trade-offs such as maximizing return/investment, maximizing profit/time, minimizing cost/time or minimizing wasted/used material. For example, risk-adverse decision-makers are often interested in solutions that provide a good trade-off between the expected return and risk, which can be modeled naturally as the ratio function. Also, fractional objectives can be used for feature selection and clustering in data mining as well as for solving isoperimetric problems on graphs that can be applied for error-correcting codes and image segmentation. There are no adequate solution approaches for these classes of optimization problems if they involve integrality and/or combinatorial restrictions (constraints). Therefore, if successful, the proposed research will substantially enhance the ability to solve these hard classes of optimization problems and can lead to a more widespread use of single- and multiple-ratio fractional measures in existing and emerging applications.The project's main goal is to develop computational approaches with the solid underlying theoretical foundation, that deliver provably good solutions and can be used to solve realistically sized instances of single- and multiple-ratio fractional combinatorial optimization problems. In order to do so, the investigators propose to systematically exploit the combinatorial structure of the feasible region and structural properties of the ratio functions to construct strong convex relaxations of the fractional combinatorial optimization problems. The investigators will also explore single- and multiple-ratio fractional combinatorial optimization problems under parameter uncertainty. The proposed research, unlike most of previous work in the related literature, does not enforce restrictive simplifying assumptions on either the combinatorial structure induced by the constraint set or the number of ratios. Furthermore, the research does not rely on assuming that the functions in the numerators and denominators of the ratios are affine. The proposed approaches draw ideas and will contribute to the literature of mathematical optimization, particularly conic, fractional and discrete optimization, combinatorics, and algebraic graph theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

当建模诸如最大化回报/投资，最大化利润/时间，最小化成本/时间或最小化浪费/二手材料之类的折衷方案时，在不同的应用程序环境中自然会出现单比率分数组合优化问题。 例如，风险不利的决策者通常对提供预期收益和风险之间良好权衡的解决方案感兴趣，这些解决方案可以自然地建模为比率功能。同样，分数目标可用于数据挖掘中的特征选择和聚类，以及在图上求解等级问题，这些问题可用于错误纠正校正代码和图像分割。如果这些类别的优化问题涉及完整性和/或组合限制（约束），则没有足够的解决方案方法。因此，如果成功的话，拟议的研究将基本上增强解决这些困难类别的优化问题的能力，并可能导致在现有和新兴应用中更广泛地使用单比和多重分数措施，该项目的主要目标是开发计算方法，以实现良好的理论和可行的良好的结合，可以实现良好的良好的结合，从而实现了现实的结合，并且可以实现现实的结合。优化问题。为此，研究人员建议系统地利用可行区域的组合结构和比率功能的结构特性，以构建分数组合优化问题的强凸松弛。研究人员还将在参数不确定性下探索单比例分数组合优化问题。与相关文献中的大多数工作不同，拟议的研究并未强制对约束集或比率数量引起的组合结构的限制性简化假设。此外，该研究并不依赖于假设分子中的功能和比率的分母是仿射。所提出的方法提出了思想，并将为数学优化的文献做出贡献，尤其是锥形，分数和离散优化，组合学和代数图理论。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的评估来通过评估来获得支持的。

项目成果

Fractional 0–1 programming and submodularity

• DOI: 10.1007/s10898-022-01131-5
• 发表时间: 2020-12
• 期刊: Journal of Global Optimization
• 影响因子: 1.8
• 作者: Shaoning Han;A. Gómez;O. Prokopyev

Fractional 0–1 programs: links between mixed-integer linear and conic quadratic formulations

分数 0-1 程序：混合整数线性和二次曲线公式之间的联系

• DOI: 10.1007/s10898-019-00817-7
• 发表时间: 2019
• 期刊: Journal of Global Optimization
• 影响因子: 1.8
• 作者: Mehmanchi, Erfan;Gómez, Andrés;Prokopyev, Oleg A.
• 通讯作者: Prokopyev, Oleg A.

Solving a class of feature selection problems via fractional 0–1 programming

• DOI: 10.1007/s10479-020-03917-w
• 发表时间: 2021-03
• 期刊: Annals of Operations Research
• 影响因子: 4.8
• 作者: Erfan Mehmanchi;A. Gómez;O. Prokopyev

Submodularity in Conic Quadratic Mixed 0–1 Optimization

二次二次混合 0-1 优化中的子模性

• DOI: 10.1287/opre.2019.1888
• 发表时间: 2020
• 期刊: Operations Research
• 影响因子: 2.7
• 作者: Atamtürk, Alper;Gómez, Andrés
• 通讯作者: Gómez, Andrés

Sparse and Smooth Signal Estimation: Convexification of L0 Formulations

• 发表时间: 2018-11
• 期刊: J. Mach. Learn. Res.
• 作者: Alper Atamtürk;A. Gómez;Shaoning Han