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

作者：Fakhri Ashkan; Ghatee Mehdi^*

来源：Optimization, 2016, 65(5): 1023-1038.

DOI：10.1080/02331934.2015.1113532

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

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.

• 出版日期2016-5-3