On the Binary Linearly Constrained Quadratic Fractional Programming

This paper studies a class of nonconvex binary fractional minimization problem in which the feasible region is the intersection of the linear inequality constraints. Using Dinkelbach's idea and a linearization technique, ‎We propose a parametric algorithm based on the root-finding‎, ‎including Newton’s method, ‎which itself involves a Binary linear programming in each iteration. ‎The applications of the proposed formulation is illustrated through the case study on graph problems‎, ‎which are modeled as binary fractional minimization problem.

Keywords:

Binary Programming‎ , ‎Linearization‎ , ‎ Parametric Algorithm , Global Optimization‎.