Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation

DOI10.1007/s10107-006-0043-yzbMath1146.90059OpenAlexW1990399046MaRDI QIDQ2465657

Jens Lysgaard, Artur Alves Pessoa, Eduardo Uchoa, Ricardo Fukasawa, Marcus Poggi de Aragão, Diogo V. Andrade

Publication date: 7 January 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0043-y

zbMATH Keywords

pricing subproblemq-arbs

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear algebraic groups over finite fields (20G40) Maximal subgroups (20E28) Modular representations and characters (20C20) Combinatorial optimization (90C27)

Related Items (29)

Petroleum supply planning: reformulations and a novel decomposition algorithm ⋮ Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem ⋮ A branch-and-price algorithm for the ring-tree facility location problem ⋮ Layered graph approaches for combinatorial optimization problems ⋮ ILP formulation of the degree-constrained minimum spanning hierarchy problem ⋮ A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem ⋮ Some recent contributions to network optimization ⋮ A biased random-key genetic algorithm for the capacitated minimum spanning tree problem ⋮ Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems ⋮ A Branch-and-Bound Algorithm for Building Optimal Data Gathering Tree in Wireless Sensor Networks ⋮ Enhancing discretized formulations: the knapsack reformulation and the star reformulation ⋮ Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems ⋮ New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems ⋮ RAMP for the capacitated minimum spanning tree problem ⋮ On a generalization of the master cyclic group polyhedron ⋮ On the edge capacitated Steiner tree problem ⋮ Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems ⋮ Models and heuristics for the k ‐degree constrained minimum spanning tree problem with node‐degree costs ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ A new extended formulation of the generalized assignment problem and some associated valid inequalities ⋮ Unnamed Item ⋮ GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem ⋮ A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem ⋮ Improved lower bounds for the split delivery vehicle routing problem ⋮ Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams ⋮ A Branch-and-Price-and-Cut Algorithm for the Cable-Routing Problem in Solar Power Plants ⋮ Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty

Uses Software

• OR-Library
• VRP
• CVRPSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• The capacitated minimal spanning tree problem: An experiment with a hop-indexed model
• The volume algorithm: Producing primal solutions with a subgradient method
• The capacitated minimum spanning tree problem: revisiting hop-indexed formulations
• A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem.
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• The capacitated minimum spanning tree problem: On improved multistar constraints
• An exact algorithm for the capacitated shortest spanning arborescence
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• On the capacitated concentrator location problem: a reformulation by discretization
• A memory adaptive reasoning technique for solving the capacitated minimum spanning tree problem
• Solving capacitated arc routing problems using a transformation to the CVRP
• Projection results for vehicle routing
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• 2-Path Cuts for the Vehicle Routing Problem with Time Windows
• Lot-Sizing with Start-Up Times
• A branch and bound algorithm for the capacitated minimum spanning tree problem
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• A Polyhedral Intersection Theorem for Capacitated Spanning Trees
• A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Multistars and directed flow formulations
• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• Multimodal Express Package Delivery: A Service Network Design Application
• Models and heuristics for a minimum arborescence problem
• Exact solution of the centralized network design problem on directed graphs
• Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem

This page was built for publication: Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation