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
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
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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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 (5)
- A conic quadratic formulation for a class of convex congestion functions in network flow problems
- 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
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)
