Convexification of Queueing Formulas by Mixed-Integer Second-Order Cone Programming: An Application to a Discrete Location Problem with Congestion
研究如何将M/G/1排队系统的性能指标建模为混合整数二阶锥规划，并应用于带拥塞的随机选址问题，提出三种新模型，能高效求解现有线性规划方法无法解决的大规模问题。
Mixed-integer second-order cone programs (MISOCPs) form a novel class of mixed-integer convex programs, which can be solved very efficiently as a result of the recent advances in optimization solvers. This paper shows how various performance metrics of M/G/1 queues can be modeled by different MISOCPs. To motivate the reformulation method, it is first applied to a challenging stochastic location problem with congestion, which is broadly used to design socially optimal service systems. Three different MISOCPs are developed and compared on different sets of benchmark test problems. The new formulations efficiently solve very large-size test problems that cannot be solved by the two existing methods developed based on linear programming within reasonable time. The superiority of the conic reformulation method is next shown over a state-space decomposition method recently used to solve an assignment problem in queueing systems. Finally, the general applicability of the method is shown for similar optimization problems that use queue-theoretic performance measures to address customer satisfaction and service quality.