Global optimization of fractional programs with applications to engineering and management problems

• Main Author: Liu, Jianing
• Other Authors: Jitamitra Desai
• Format: Theses and Dissertations
• Language: English
• Published: 2017
• Subjects: DRNTU::Engineering::Industrial engineering::Operations research
• Online Access: http://hdl.handle.net/10356/72451
• Institution: Nanyang Technological University

In this dissertation, we focus on deriving globally optimal algorithms for three specialized fractional programming problems arising in the context of the independent set problem and management applications in wireless communications. Most of the research efforts thus far involving fractional programs have focused on solving various classes of the single-ratio fractional programs, or multi-ratio cases involving linear fractional functions. However, fractional programming problems become substantially more difficult as the number of ratios in the objective function increases, and this complexity is further amplified when the involved terms are higher-order polynomials. While some classes of multiple-ratio problems can be solved to optimality by recasting them as equivalent 0-1 mixed-integer programming problems, and embedding them within a tailored branch-and-bound algorithm, there is yet significant scope to devise specialized algorithms for solving the generic class of sum of ratios fractional programs, particularly for the case where the involved functions are higher-degree polynomials. We begin by investigating continuous optimization approaches, notably fractional programming methods, to determine the stability number (or independence number) of a graph. Traditionally, this problem has been solved using integer programming methods, but these methods have been known to suffer from a number of shortcomings, in addition to the complexity of dealing with discrete variables. In this context, a new class of vertex sets is defined, and the structure of these vertex sets is utilized to derive explicit characterizations of the number of alternate optima present in both discrete and continuous formulations. Moreover, these vertex sets also enable a simple, yet powerful, construction procedure to efficiently determine maximal independent sets. We also develop a global optimization algorithm to solve the FP formulation, and we demonstrate that this continuous approach stays on par with the 0-1 discrete formulation with respect to various performance metrics. As seen in our numerical experiments, we showed that the computational time required per optimal solution is comparable and in some instances lower for Problem FP as compared to Problem MIS (as the number of alternate optima for Problem FP is significantly greater when compared to Problem MIS) Having established the importance of fractional programming formulations as a viable source for solving hard optimization problems, in the next phase of this research, we focus on solving real-world applications arising in the context of cellular network design. We present a set of (exact and approximate) mathematical models and algorithms for determining the set of (globally) optimal distributed antenna deployments and the supported user demand in cellular code division multiple access (CDMA) systems. We focus on the uplink (user-to-base) formulation and assume that the base station combines all the received signals at each of the antennas using path-gain based weights. In CDMA systems, as all users occupy the system bandwidth at the same time thereby interfering with each other, this results in complicated mixed-integer 0-1 multi-linear programming problem, where the objective function maximizes the total system capacity, while ensuring that the minimum signal-to-interference plus noise ratio (SINR) constraints and maximum transit power constraints for each user are satisfied. This highly nonlinear, nonconvex problem is reformulated to yield a tight mixed-integer 0-1 linear programming representation via the addition of several auxiliary variables and constraints, and a specialized algorithm is designed to determine globally optimal solutions. Finally, we extend the above developed methodology for optimally locating DAS antennas in CDMA cellular networks in the presence of femtocells. Although a femtocell is a simple plug-and-play device, its location requires pre-approval by the service provider. The introduction of femtocells into a cellular network can be very beneficial to both service providers as well as end users. Once again, our focus is on developing an analytical framework that provides a way of computing optimal DAS deployments so that the total capacity is maximized in the CDMA cellular network. Such a framework would be critical for service providers who are interested in adopting the use of femtocells. In conclusion, this thesis provides an algorithmic framework for deriving globally optimal solutions for the class of fractional programming problems, and this approach is validated by solving various practical problems arising in engineering and management applications.