Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem

DOI10.1002/net.20485zbMath1241.90187MaRDI QIDQ2892153

Eduardo Uchoa, Mauricio C. de Souza, Ricardo Fukasawa, Túlio A. M. Toffolo, Alexandre Xavier Martins

Publication date: 18 June 2012

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20485

zbMATH Keywords

network design; branch-and-cut; Fenchel cuts; MIP based local search

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

Related Items

Integer programming techniques for the nurse rostering problem, Layered graph approaches for combinatorial optimization problems, A hybrid VNS algorithm for solving the multi-level capacitated minimum spanning tree problem, Heuristics for the multi-level capacitated minimum spanning tree problem

Uses Software

• GRASP

Cites Work

• Unnamed Item
• Unnamed Item
• On the exact separation of mixed integer knapsack cuts
• Enhanced second order algorithm applied to the capacitated minimum spanning tree problem
• A computational study of exact knapsack separation for the generalized assignment problem
• Strong bounds with cut and column generation for class-teacher timetabling
• The capacitated minimum spanning tree problem: revisiting hop-indexed formulations
• A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem.
• On a generalization of the master cyclic group polyhedron
• GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• The Multilevel Capacitated Minimum Spanning Tree Problem
• An annotated bibliography of GRASP-Part II: Applications
• Generating Fenchel Cutting Planes for Knapsack Polyhedra
• Fenchel Cutting Planes for Integer Programs
• Solving capacitated facility location problems by Fenchel cutting planes
• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem