Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint
From MaRDI portal
Publication:2883603
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
mixed integer programmingSteiner treereformulation-linearization techniqueMTZ subtour elimination constraints
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
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