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

References

• Ahmadi-Javid AA, Azad N (2010) Incorporating location, routing and inventory decisions in supply chain network design. Transportation Res. Part E Logist. Transportation Rev. 46(5):582–597.Crossref, Google Scholar
• Ahmadi-Javid A, Ramshe N (2020) Linear formulations and valid inequalities for a classic location problem with congestion: A robust optimization application. Optim. Lett. 14:1265–1285.Crossref, Google Scholar
• Alizadeh F, Goldfarb D (2003) Second-order cone programming. Math. Programming 95(1):3–51.Crossref, Google Scholar
• Andersen K, Jensen AN (2013) Intersection cuts for mixed integer conic quadratic sets. Goemans M, Correa J, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science (Springer, Berlin).Crossref, Google Scholar
• Atamtürk A, Berenguer G, Shen ZJ (2012) A conic integer programming approach to stochastic joint location-inventory problems. Oper. Res. 60(2):366–381.Link, Google Scholar
• Bai X, Gopal R, Nunez M, Zhdanov D (2012) On the prevention of fraud and privacy exposure in process information flow. INFORMS J. Comput. 24(3):416–432.Link, Google Scholar
• Baron O, Kerner Y (2016) A queueing approach to a multi class M/G/1 make-to-stock with backlog. Oper. Res. Lett. 44(5):666–671.Crossref, Google Scholar
• Belotti P, Goez JC, Pólik I, Ralphs TK, Terlaky T (2015) A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization. Al-Baali M, Grandinetti L, Purnama A, eds. Numerical Analysis and Optimization (Springer, Cham, Switzerland).Crossref, Google Scholar
• Benson HY, Sağlam Ü (2013) Mixed-integer second-order cone programming: A survey. Topaloglu H, ed. Theory Driven by Influential Applications. Tutorials in Operations Research (INFORMS, Catonsville, MD), 13–36.Link, Google Scholar
• Ben-Tal A, Nemirovski A (2001a) Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (SIAM, Philadelphia).Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2001b) On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2):193–205.Link, Google Scholar
• Bergman D, Cire AA (2017) Discrete nonlinear optimization by state-space decompositions. Management Sci. 64(10):4700–4720.Link, Google Scholar
• Berman O, Krass D (2019) Stochastic location models with congestion. Laporte G, Nickel S, Saldanha-da-Gama F, eds. Location Science, 2nd ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• Billionnet A, Elloumi S, Plateau MC (2008) Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations. RAIRO Oper. Res. 42(2):103–121.Crossref, Google Scholar
• Boffey B, Galvao R, Espejo L (2007) A review of congestion models in the location of facilities with immobile servers. Eur. J. Oper. Res. 178(3):643–662.Crossref, Google Scholar
• Bonami P, Lejeune MA (2009) An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Oper. Res. 57(3):650–670.Link, Google Scholar
• Bonami P, Tramontani A (2015) Advances in CPLEX for mixed integer nonlinear optimization. Internat. Sympos. Math. Programming.Google Scholar
• Borraz-Sánchez C, Bent R, Backhaus S, Hijazi H, Hentenryck PV (2016) Convex relaxations for gas expansion planning. INFORMS J. Comput. 28(4):645–656.Link, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Brandenberg R, Roth L (2009) New algorithms for k-center and extensions. J. Combin. Optim. 18(4):376–392.Crossref, Google Scholar
• Burer S, Letchford AN (2012) Non-convex mixed-integer nonlinear programming: A survey. Surveys Oper. Res. Management Sci. 17(2):97–106.Crossref, Google Scholar
• Chen K, Zhu J (2017) Second order cone programming approach to two-stage network data envelopment analysis. Eur. J. Oper. Res. 262(1):231–238.Crossref, Google Scholar
• Cheng Y, Drewes S, Philipp A, Pesavento M (2012) Joint network optimization and beamforming for coordinated multi-point transmission using mixed integer programming. Proc. IEEE Internat. Conf. Acoustics, Speech Signal Processing (IEEE), 3217–3220.Google Scholar
• Connor SB, Kendall WS (2015) Perfect simulation of M/G/c queues. Adv. Appl. Probab. 47(4):1039–1063.Crossref, Google Scholar
• Coutinho WP, Nascimento RQD, Pessoa AA, Subramanian A (2016) A branch-and-bound algorithm for the close-enough traveling salesman problem. INFORMS J. Comput. 28(4):752–765.Link, Google Scholar
• Daskin MS (2011) Network and Discrete Location: Models, Algorithms, and Applications (Wiley, Hoboken, NJ).Google Scholar
• Drewes S (2009) Mixed integer second order cone programming. Unpublished PhD thesis, Technische Universität Darmstadt, Germany.Google Scholar
• Drewes S, Ulbrich S (2012) Subgradient based outer approximation for mixed integer second order cone programming. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming, IMA Volumes in Mathematics and Its Applications (Springer, New York).Crossref, Google Scholar
• Drezner Z, Hamacher HW, eds. (2001) Facility Location: Applications and Theory (Springer, Berlin).Google Scholar
• Du Y, Chen Q, Quan X, Long L, Fung RY (2011) Berth allocation considering fuel consumption and vessel emissions. Transportation Res. Part E Logist. Transportation Rev. 47(6):1021–1037.Crossref, Google Scholar
• Elhedhli S (2006) Service system design with immobile servers, stochastic demand, and congestion. Manufacturing Service Oper. Management 8(1):92–97.Link, Google Scholar
• Goez JC (2013) Mixed integer second order cone optimization, disjunctive conic cuts: Theory and experiments. Unpublished PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• Gross D, Shortle JF, Thompson JM, Harris CM (2008) Fundamentals of Queueing Theory. 4th ed. (Wiley, Hoboken, NJ).Crossref, Google Scholar
• Han B, Ryzhov IO, Defourny B (2016) Optimal learning in linear regression with combinatorial feature selection. INFORMS J. Comput. 28(4):721–735.Link, Google Scholar
• He L, Mak HY, Rong Y, Shen ZJM (2017) Service region design for urban electric vehicle sharing systems. Manufacturing Service Oper. Management 19(2):309–327.Link, Google Scholar
• Hijazi H, Bonami P, Ouorou A (2013) Robust delay-constrained routing in telecommunications. Ann. Oper. Res. 206(1):163–181.Crossref, Google Scholar
• Holmberg K, Rönnqvist M, Yuan D (1999) An exact algorithm for the capacitated facility location problems with single sourcing. Eur. J. Oper. Res. 113(3):544–559.Crossref, Google Scholar
• IBM (2017) IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual (IBM Corp.).Google Scholar
• Kendall DG (1953) Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. Ann. Math. Statist. 24(3):338–354.Crossref, Google Scholar
• Kılınç MR, Linderoth J, Luedtke J (2017) Lift-and-project cuts for convex mixed integer nonlinear programs. Math. Programming Comput. 9:499–526.Crossref, Google Scholar
• Kılınç-Karzan F (2015) On minimal valid inequalities for mixed integer conic programs. Math. Oper. Res. 41(2):477–510.Link, Google Scholar
• Kılınç-Karzan F, Yıldız S (2015) Two-term disjunctions on the second-order cone. Math. Programming 154(1–2):463–491.Crossref, Google Scholar
• Kitahara T, Tsuchiya T (2018) An extension of Chubanov’s polynomial-time linear programming algorithm to second-order cone programming. Optim. Methods Software 33(1):1–25.Crossref, Google Scholar
• Kocuk B, Dey SS, Sun XA (2016) Strong SOCP relaxations for the optimal power flow problem. Oper. Res. 64(6):1177–1196.Link, Google Scholar
• Laporte G, Nickel S, da Gama FS, eds. (2019) Location Science, 2nd ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• Li J, Liu L, Jiang T (2018) Analysis of an M/G/1 queue with vacations and multiple phases of operation. Math. Methods Oper. Res. 87:51–72.Crossref, Google Scholar
• Lobo MS, Vandenberghe L, Boyd S, Lebret H (1998) Applications of second-order cone programming. Linear Algebra Appl. 284(1–3):193–228.Crossref, Google Scholar
• Maggioni F, Potra FA, Bertocchi MI, Allevi E (2009) Stochastic second-order cone programming in mobile ad hoc networks. J. Optim. Theory Appl. 143(2):309–328.Crossref, Google Scholar
• Mak HY, Rong Y, Shen ZJM (2013) Infrastructure planning for electric vehicles with battery swapping. Management Sci. 59(7):1557–1575.Link, Google Scholar
• Mak HY, Rong Y, Zhang J (2014) Appointment scheduling with limited distributional information. Management Sci. 61(2):316–334.Link, Google Scholar
• Miyashiro R, Takano Y (2015) Mixed integer second-order cone programming formulations for variable selection in linear regression. Eur. J. Oper. Res. 247(3):721–731.Crossref, Google Scholar
• Modaresi S, Kılınç MR, Vielma JP (2016) Intersection cuts for nonlinear integer programming: Convexification techniques for structured sets. Math. Programming 155(1–2):575–611.Crossref, Google Scholar
• Nemirovski A (2006) Advances in convex optimization: Conic programming. Proc. Internat. Congress Mathematicians (European Mathematical Society), 413–444.Google Scholar
• Nemirovski A, Scheinberg K (1996) Extension of Karmarkar’s algorithm onto convex quadratically constrained quadratic problems. Math. Programming 72(3):273–289.Crossref, Google Scholar
• Pattanayak U, Narayanan V (2017) Intersection cuts for convex mixed integer programs from translated cones. Discrete Optim. 24(C):103–128.Crossref, Google Scholar
• Pena J, Soheili N (2017) Solving conic systems via projection and rescaling. Math. Programming 166(1–2):87–111.Crossref, Google Scholar
• Pınar MÇ (2013) Mixed-integer second-order cone programming for lower hedging of American contingent claims in incomplete markets. Optim. Lett. 7(1):63–78.Crossref, Google Scholar
• Salimian M, Gürel S (2013) A mixed integer second order cone programming reformulation for a congested location and capacity allocation problem in supply chain network design. Unpublished MSc thesis, Middle East Technical University, Ankara, Turkey.Google Scholar
• Savelsbergh MW (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4):445–454.Link, Google Scholar
• See CT, Sim M (2010) Robust approximation to multiperiod inventory management. Oper. Res. 58(3):583–594.Link, Google Scholar
• Sherali HD, Adams WP (1999) A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems (Springer, Boston).Crossref, Google Scholar
• Shivaswamy PK, Bhattacharyya C, Smola AJ (2006) Second order cone programming approaches for handling missing and uncertain data. J. Machine Learn. Res. 7(47):1283–1314.Google Scholar
• Shortle JF, Fischer MJ, Brill PH (2007) Waiting-time distribution of M/DN/1 queues through numerical Laplace inversion. INFORMS J. Comput. 19(1):112–120.Link, Google Scholar
• Shortle JF, Brill PH, Fischer MJ, Gross D, Masi DM (2004) An algorithm to compute the waiting time distribution for the M/G/1 queue. INFORMS J. Comput. 16(2):152–161.Link, Google Scholar
• Sigman K (2016) Using the M/G/1 queue under processor sharing for exact simulation of queues. Ann. Oper. Res. 241(1–2):23–34.Crossref, Google Scholar
• Tanaka M, Kobayashi K (2019) A route generation algorithm for an optimal fuel routing problem between two single ports. Internat. Trans. Oper. Res. 26(2):529–550.Crossref, Google Scholar
• Taylor JA, Hover FS (2012) Convex models of distribution system reconfiguration. IEEE Trans. Power Systems 27(3):1407–1413.Crossref, Google Scholar
• Vidyarthi N, Jayaswal S (2014) Efficient solution of a class of location–allocation problems with stochastic demand and congestion. Comput. Oper. Res. 48:20–30.Crossref, Google Scholar
• Vidyarthi N, Elhedhli S, Jewkes E (2009) Response time reduction in make-to-order and assemble-to-order supply chain design. IIE Trans. 41(5):448–466.Crossref, Google Scholar
• Vielma JP, Ahmed S, Nemhauser GL (2008) A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS J. Comput. 20(3):438–450.Link, Google Scholar