Solving the minimum label spanning tree problem by mathematical programming techniques
Summary: We present exact mixed integer programming approaches including branch-and-cut and branch-and-cut-and-price for the minimum label spanning tree problem as well as a variant of it having multiple labels assigned to each edge. We compare formulations based on network flows and directed connectivity cuts. Further, we show how to use odd-hole inequalities and additional inequalities to strengthen the formulation. Label variables can be added dynamically to the model in the pricing step. Primal heuristics are incorporated into the framework to speed up the overall solution process. After a polyhedral comparison of the involved formulations, comprehensive computational experiments are presented in order to compare and evaluate the underlying formulations and the particular algorithmic building blocks of the overall branch-and-cut- (and-price) framework.
- A mixed integer linear formulation for the minimum label spanning tree problem
- A polyhedral approach to the generalized minimum labeling spanning tree problem
- The minimum labeling spanning trees
- On the minimum label spanning tree problem
- An efficient mixed integer linear programming model for the minimum spanning tree problem
- A mixed integer linear formulation for the minimum label spanning tree problem
- A note on the minimum label spanning tree.
- Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem
- scientific article; zbMATH DE number 795222 (Why is no real title available?)
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- Integer Programming Formulation of Traveling Salesman Problems
- Local search for the minimum label spanning tree problem with bounded color classes.
- Obtaining optimal \(k\)-cardinality trees fast
- On implementing the push-relabel method for the maximum flow problem
- On the 0,1 facets of the set covering polytope
- On the minimum label spanning tree problem
- Solving a k-node minimum label spanning arborescence problem to compress fingerprint templates
- Solving matching problems with linear programming
- The minimum labeling spanning trees
- Variable neighbourhood search for the minimum labelling Steiner tree problem
- Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
- A mixed integer linear formulation for the minimum label spanning tree problem
- Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
- A hybrid metaheuristic for the minimum labeling spanning tree problem
- Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
- Complexity and approximation results on the shared transportation problem
- A polyhedral approach to the generalized minimum labeling spanning tree problem
- An improved flow-based formulation and reduction principles for the minimum connectivity inference problem
- Finding minimum label spanning trees using cross‐entropy method
- An efficient mixed integer linear programming model for the minimum spanning tree problem
- On the shared transportation problem: computational hardness and exact approach
This page was built for publication: Solving the minimum label spanning tree problem by mathematical programming techniques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q666399)
