Publication Type

Journal Article

Version

acceptedVersion

Publication Date

7-2025

Abstract

We study a class of binary fractional programs commonly encountered in important application domains such as assortment optimization and facility location. These problems are known to be NP-hard to approximate within any constant factor, and existing solution approaches typically rely on mixed-integer linear programming or second-order cone programming reformulations. These methods often utilize linearization techniques (e.g., big-M or McCormick inequalities), which can result in weak continuous relaxations. In this work, we propose a novel approach based on an exponential cone reformulation combined with piecewise linear approximation. This allows the problem to be solved efficiently using standard cutting-plane or branch-and-cut procedures. We further provide a theoretical analysis of the approximation quality yielded by our reformulation and discuss strategies for optimizing the problem size of the exponential cone formulation. Experiments on instances of various sizes demonstrate that our approach delivers competitive performance on small and medium instances while offering superior performance on large instances compared to state-of-the-art baselines.

Keywords

Fractional program; exponential cone, piece-wise linear approximation, cutting plane

Discipline

Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Journal of Combinatorial Optimization

Volume

49

Issue

5

First Page

1

Last Page

16

ISSN

1382-6905

Identifier

10.1007/s10878-025-01318-y

Publisher

Springer

Additional URL

https://doi.org/10.1007/s10878-025-01318-y

Download

Share

COinS