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

DOI10.1016/j.endm.2010.05.063zbMath1237.90243OpenAlexW2067501168MaRDI 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 programmingSteiner treereformulation-linearization techniqueMTZ subtour elimination constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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

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