Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint

DOI10.1016/j.endm.2010.05.063zbMath1237.90243MaRDI QIDQ2883603

Mohamed Haouari, Safa Bhar Layeb, Hanif D. Sherali

Publication date: 13 May 2012

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2010.05.063

zbMATH Keywords

mixed integer programming; Steiner tree; reformulation-linearization technique; MTZ subtour elimination constraints

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

A divide and conquer matheuristic algorithm for the prize-collecting Steiner tree problem, Exact algorithms for budgeted prize-collecting covering subgraph problems

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• A note on the prize collecting traveling salesman problem
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• Strong lower bounds for the prize collecting Steiner problem in graphs
• Algorithmic expedients for the prize collecting Steiner tree problem
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Integer Programming Formulation of Traveling Salesman Problems