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
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.
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
Cites work
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A branch-and-bound algorithm for the close-enough traveling salesman problem
- A conic integer programming approach to stochastic joint location-inventory problems
- A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
- A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
- A queueing approach to a multi class $M / G / 1$ make-to-stock with backlog
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A review of congestion models in the location of facilities with immobile servers
- A route generation algorithm for an optimal fuel routing problem between two single ports
- Advances in convex optimization: conic programming
- An algorithm to compute the waiting time distribution for the \(M/G/1\) queue
- An exact algorithm for the capacitated facility location problems with single sourcing
- An exact solution approach for portfolio optimization problems under stochastic and integer constraints
- An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming
- Analysis of an M/G/1 queue with vacations and multiple phases of operation
- Applications of second-order cone programming
- Convex relaxations for gas expansion planning
- Efficient solution of a class of location-allocation problems with stochastic demand and congestion
- Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems
- Fundamentals of queueing theory
- Intersection cuts for convex mixed integer programs from translated cones
- Intersection cuts for mixed integer conic quadratic sets
- Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Lift-and-project cuts for convex mixed integer nonlinear programs
- Linear formulations and valid inequalities for a classic location problem with congestion: a robust optimization application
- Location science
- Mixed integer second order cone programming.
- Mixed integer second-order cone programming formulations for variable selection in linear regression
- Mixed-integer second-order cone programming for lower hedging of American contingent claims in incomplete markets
- New algorithms for \(k\)-center and extensions
- On Polyhedral Approximations of the Second-Order Cone
- On minimal valid inequalities for mixed integer conic programs
- On the prevention of fraud and privacy exposure in process information flow
- Optimal learning in linear regression with combinatorial feature selection
- Perfect simulation of \(\mathrm{M}/\mathrm{G}/c\) queues
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
- Robust approximation to multiperiod inventory management
- Robust delay-constrained routing in telecommunications
- Second order cone programming approach to two-stage network data envelopment analysis
- Second order cone programming approaches for handling missing and uncertain data
- Second-order cone programming
- Solving conic systems via projection and rescaling
- Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain
- Stochastic second-order cone programming in mobile ad hoc networks
- Strong SOCP relaxations for the optimal power flow problem
- Subgradient based outer approximation for mixed integer second order cone programming
- Two-term disjunctions on the second-order cone
- Using the M/G/1 queue under processor sharing for exact simulation of queues
- Waiting-time distribution of \(M/D_{N}/1\) queues through numerical Laplace inversion
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
- Robust design of service systems with immobile servers under demand uncertainty
- Equity in genetic newborn screening
- Linear formulations and valid inequalities for a classic location problem with congestion: a robust optimization application
- Fast heuristics for the time-constrained immobile server problem
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)
