Title: Convexification of Queueing Formulas by Mixed-Integer Second-Order Cone Programming: An Application to a Discrete Location Problem with Congestion,
Abstract: Mixed-Integer Second-Order Cone Programs (MISOCPs) form a nice class of
mixed-inter convex programs, which can be solved very efficiently due to the
recent advances in optimization solvers. Our paper bridges the gap between
modeling a class of optimization problems and using MISOCP solvers. It is shown
how various performance metrics of M/G/1 queues can be molded by different
MISOCPs. To motivate our method practically, it is first applied to a
challenging stochastic location problem with congestion, which is broadly used
to design socially optimal service networks. Four different MISOCPs are
developed and compared on sets of benchmark test problems. The new formulations
efficiently solve large-size test problems, which cannot be solved by the best
existing method. Then, the general applicability of our method is shown for
similar optimization problems that use queue-theoretic performance measures to
address customer satisfaction and service quality.