Optimization Online


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

Ahmadi-Javid Amir (ahmadi_javid***at***aut.ac.ir)
Hoseinpour Pooya(pooya.hoseinpour***at***mail.mcgill.ca)

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.

Keywords: Mixed-integer second-order cone programming; M/G/1 queues; Stochastic discrete location problems; Integer Nonlinear Programming; Network optimization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Applications -- OR and Management Sciences

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )


Download: [PDF]

Entry Submitted: 10/16/2017
Entry Accepted: 10/16/2017
Entry Last Modified: 10/16/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society