Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: continuous and discrete problems

Abstract

This paper tries to minimize the sum of a linear and a linear fractional function over a closed convex set defined by some linear and conic quadratic constraints. At first, we represent some necessary and sufficient conditions for the pseudoconvexity of the problem. For each of the conditions, under some reasonable assumptions, an appropriate second-order cone programming (SOCP) reformulation of the problem is stated and a new applicable solution procedure is proposed. Efficiency of the proposed reformulations is demonstrated by numerical experiments. Secondly, we limit our attention to binary variables and derive a sufficient condition for SOCP representability. Using the experimental results on random instances, we show that the proposed conic reformulation is more efficient in comparison with the well-known linearization technique and it produces more eligible cuts for the branch and bound algorithm.

Keywords:

• Generalized fractional function
• pseudoconvexity
• second-order cone programming
• integer programming

Acknowledgements

The authors gratefully acknowledge Dr. M. Reza Peyghami[4] and the honourable reviewers for their valuable comments which led to a great improvement in the manuscript. We also highly appreciate the support of the honourable editors.

Notes

No potential conflict of interest was reported by the authors.

1 Convex Quadratic Programming

2 Semi-definite Programming

3 Convex Programming

4 K. N. Toosi University of Technology, Tehran, Iran