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.

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

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

Sparse and Smooth Signal Estimation: Convexification of L0 Formulations

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