Advancing Fractional Combinatorial Optimization: Computation and Applications

单比和多比分数组合优化问题自然出现在不同的应用环境中，当建模权衡，如最大限度地提高回报/投资，最大限度地提高利润/时间，最小化成本/时间或最小化浪费/使用的材料。 例如，风险逆向决策者通常对在预期收益和风险之间提供良好权衡的解决方案感兴趣，这可以自然地建模为比率函数。此外，分数目标可用于数据挖掘中的特征选择和聚类，以及用于解决可用于纠错码和图像分割的图上的等周问题。如果这些优化问题涉及完整性和/或组合约束（约束），则没有适当的解决方案。因此，如果成功，拟议的研究将大大提高解决这些困难的优化问题的能力，并可能导致在现有和新兴应用中更广泛地使用单比和多比分数测度。该项目的主要目标是开发具有坚实的基础理论基础的计算方法，提供可证明的良好解决方案，并可用于解决实际大小的单比和多比分数组合优化问题的实例。为了做到这一点，研究人员建议系统地利用可行域的组合结构和比率函数的结构性质来构造分数阶组合优化问题的强凸松弛。研究人员还将探索参数不确定性下的单比和多比分数组合优化问题。所提出的研究，不像大多数以前的工作在相关文献中，不强制限制性的简化假设，无论是组合结构诱导的约束集或比率的数量。此外，该研究不依赖于假设比率的分子和分子中的函数是仿射的。建议的方法绘制的想法，并将有助于数学优化，特别是圆锥曲线，分数和离散优化，组合学和代数图论的文献。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.