We propose a copositive reformulation of the mixed-integer fractional quadratic problem (MIFQP) under general linear constraints. This problem class arises naturally in many applications, e.g., for optimizing communication or social networks, or studying game theory problems arising from genetics. It includes several APX-hard subclasses: the maximum cut problem, the $k$-densest subgraph problem and several of its variants, or the ternary fractional quadratic optimization problem (TFQP). Problems of this type arise when modelling density clustering problems with two voting options plus the possibility of an abstention, which is a criterion-based graph tri-partitioning problem. This paper adds to the rich evidence for the versatility of copositive optimization approaches, and hints at possible novel approximation strategies combining continuous and discrete optimization techniques in the domain of (fractional) polynomial optimization.
Citation
Preprint NI14043-POP, Isaac Newton Institute for Mathematical Sciences, University of Cambridge UK, submitted