Convexification of Queueing Formulas by Mixed-Integer Second-Order Cone Programming: An Application to a Discrete Location Problem with Congestion

Amir Ahmadi-Javid () and Pooya Hoseinpour ()
Additional contact information
Amir Ahmadi-Javid: Department of Industrial Engineering & Management Systems, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran
Pooya Hoseinpour: Department of Industrial Engineering & Management Systems, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran

INFORMS Journal on Computing, 2022, vol. 34, issue 5, 2621-2633

Abstract: 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.

Keywords: queues; optimization; integer programming; networks; service system design; capacity planning; stochastic facility location (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1125 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:5:p:2621-2633

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().