Convexification of queueing formulas by mixed-integer second-order cone programming: an application to a discrete location problem with congestion
From MaRDI portal
Publication:5058005
DOI10.1287/IJOC.2021.1125zbMATH Open1502.90042arXiv1710.05794OpenAlexW2766459328WikidataQ113749948 ScholiaQ113749948MaRDI QIDQ5058005FDOQ5058005
Authors: Amir Ahmadi-Javid, Pooya Hoseinpour 
Publication date: 1 December 2022
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1710.05794
Recommendations
- Second-order cone optimization formulations for service system design problems with congestion
- Alternate second order conic program reformulations for hub location under stochastic demand and congestion
- Linear formulations and valid inequalities for a classic location problem with congestion: a robust optimization application
- scientific article; zbMATH DE number 7708795
- A conic quadratic formulation for a class of convex congestion functions in network flow problems
optimizationnetworksinteger programmingqueuescapacity planningservice system designstochastic facility location
Convex programming (90C25) Queues and service in operations research (90B22) Mixed integer programming (90C11) Discrete location and assignment (90B80)
Cites Work
- Title not available (Why is that?)
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Fundamentals of queueing theory
- Applications of second-order cone programming
- An exact algorithm for the capacitated facility location problems with single sourcing
- Second-order cone programming
- A conic integer programming approach to stochastic joint location-inventory problems
- On Polyhedral Approximations of the Second-Order Cone
- Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain
- Robust approximation to multiperiod inventory management
- Stochastic second-order cone programming in mobile ad hoc networks
- An exact solution approach for portfolio optimization problems under stochastic and integer constraints
- Advances in convex optimization: conic programming
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
- Mixed integer second order cone programming.
- Mixed integer second-order cone programming formulations for variable selection in linear regression
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- On minimal valid inequalities for mixed integer conic programs
- Second order cone programming approaches for handling missing and uncertain data
- A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
- Intersection cuts for mixed integer conic quadratic sets
- Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
- Two-term disjunctions on the second-order cone
- A review of congestion models in the location of facilities with immobile servers
- Perfect simulation of \(\mathrm{M}/\mathrm{G}/c\) queues
- Using the \(M/G/1\) queue under processor sharing for exact simulation of queues
- Efficient solution of a class of location-allocation problems with stochastic demand and congestion
- Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
- Robust delay-constrained routing in telecommunications
- Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems
- An algorithm to compute the waiting time distribution for the \(M/G/1\) queue
- Location science
- Lift-and-project cuts for convex mixed integer nonlinear programs
- New algorithms for \(k\)-center and extensions
- Waiting-time distribution of \(M/D_{N}/1\) queues through numerical Laplace inversion
- Analysis of an M/G/\(1\) queue with vacations and multiple phases of operation
- Subgradient based outer approximation for mixed integer second order cone programming
- Strong SOCP relaxations for the optimal power flow problem
- Convex relaxations for gas expansion planning
- A branch-and-bound algorithm for the close-enough traveling salesman problem
- Solving conic systems via projection and rescaling
- Second order cone programming approach to two-stage network data envelopment analysis
- An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming
- Intersection cuts for convex mixed integer programs from translated cones
- A queueing approach to a multi class $M / G / 1$ make-to-stock with backlog
- Mixed-integer second-order cone programming for lower hedging of American contingent claims in incomplete markets
- Linear formulations and valid inequalities for a classic location problem with congestion: a robust optimization application
- On the prevention of fraud and privacy exposure in process information flow
- Optimal learning in linear regression with combinatorial feature selection
- A route generation algorithm for an optimal fuel routing problem between two single ports
Cited In (8)
- Second-order cone optimization formulations for service system design problems with congestion
- A conic quadratic formulation for a class of convex congestion functions in network flow problems
- Alternate second order conic program reformulations for hub location under stochastic demand and congestion
- Modeling and solving an economies‐of‐scale service system design problem
- Equity in genetic newborn screening
- Robust design of service systems with immobile servers under demand uncertainty
- Fast heuristics for the time-constrained immobile server problem
- Linear formulations and valid inequalities for a classic location problem with congestion: a robust optimization application
Uses Software
This page was built for publication: Convexification of queueing formulas by mixed-integer second-order cone programming: an application to a discrete location problem with congestion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5058005)
