Advancing Fractional Combinatorial Optimization: Computation and Applications

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.