Applied Math Seminar- Fractional Integer Queueing-Based Network Design Problems : Reformulation and Algorithmic Framework

Date and Time: Feb 14, 2025 (2:00 PM – 3:00 PM)

Location: Phillips Hall, Room 730

Title:  Fractional Integer Queueing-Based Network Design Problems : Reformulation and Algorithmic Framework

Speaker: Dr. Nguyen Hoang Nam (GWU, Department of Decision Science)

Abstract: We develop a comprehensive framework for modeling, reformulating, and solving network design queueing-based optimization problems. The network consists of a series of interdependent queueing systems with variable number of servers and endogenous service time and arrival rate, and aims at responding promptly to time-sensitive demand. Defining the number of servers deployed at a facility as a decision variable significantly increases the complexity of the problem formulation. The resulting model is a fractional nonlinear integer problem that includes factorial, polynomial, and exponential terms, as well as summations where the term count is a decision variable. The MILP reformulation framework encompasses five main steps and is general enough to be applied to the main queueing systems, such as M/M/K, M/G/K, G/M/K, and G/G/K. Specifically, we introduce new quasi-multilinearization and multilinearization processes for high-degree polynomials and develop novel analytical methods providing closed form formulae to calculate the coefficients of multilinear monomials. We devise a branch-and-cut algorithm, solving at each node an outer approximation of the MILP problem which is gradually tightened through the dynamic introduction of lazy constraints and valid inequalities. Notably, we derive a new family of nested valid inequalities and demonstrate their computational effectiveness. Numerical tests on real data show the applicability of the reformulation and algorithmic framework.