Delay-constrained shortest paths: approximation algorithms and second-order cone models

DOI10.1007/s10957-014-0624-5zbMath1321.90086OpenAlexW2068762076WikidataQ118165447 ScholiaQ118165447MaRDI QIDQ2342143

Laura Galli, Maria Grazia Scutellà, Antonio Frangioni

Publication date: 11 May 2015

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: http://eprints.adm.unipi.it/2302/1/TR%2D13%2D06.pdf.gz

zbMATH Keywords

approximation algorithmsmixed-integer nonlinear programmingperspective reformulationdelay-constrained routingsecond-order cone model

Mathematics Subject Classification ID

Convex programming (90C25) Applications of mathematical programming (90C90) Mixed integer programming (90C11) Nonlinear programming (90C30)

Related Items

Delay-constrained routing problems: accurate scheduling models and admission control, An exact algorithm for a resource allocation problem in mobile wireless communications, Improving the approximated projected perspective reformulation by dual information, QPLIB: a library of quadratic programming instances, Approximated perspective relaxations: a project and lift approach

Cites Work

• Unnamed Item
• Unnamed Item
• A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes
• Convex extensions and envelopes of lower semi-continuous functions
• Resource extension functions: properties, inversion, and generalization to segments
• Perspective cuts for a class of convex 0-1 mixed integer programs
• A survey of resource constrained shortest path problems: Exact solution approaches
• Projected Perspective Reformulations with Applications in Design Problems
• Perspective Reformulation and Applications
• Shortest path methods: A unifying approach
• Shortest Path Problems with Resource Constraints