An exponential cone integer programming and piece-wise linear approximation approach for 0-1 fractional programming

Hoang Giang Pham (), Thuy Anh Ta () and Tien Mai ()
Additional contact information
Hoang Giang Pham: Singapore Management University
Thuy Anh Ta: Phenikaa University
Tien Mai: Singapore Management University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 5, No 17, 16 pages

Abstract: 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 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01318-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01318-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01318-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().