Using dual feasible functions to construct fast lower bounds for routing and location problems

DOI10.1016/j.dam.2014.05.017zbMath1321.05039OpenAlexW2021603409MaRDI QIDQ499343

Gilles Goncalves, Daniel Cosmin Porumbel

Publication date: 30 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.05.017

zbMATH Keywords

column generation\(p\)-mediandual feasible functionsfast lower boundsgeneral routing

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Combinatorial aspects of packing and covering (05B40)

Related Items (1)

Primal and dual bounds for the vertex \(p\)-median problem with balance constraints

Cites Work

• A survey of dual-feasible and superadditive functions
• A general framework for bounds for higher-dimensional orthogonal packing problems.
• The directional \(p\)-median problem: definition, complexity, and algorithms
• Computational study of large-scale \(p\)-median problems
• Exploiting sparsity in pricing routines for the capacitated arc routing problem
• Bidimensional packing by bilinear programming
• The fleet size and mix problem for capacitated arc routing
• Stabilized column generation
• Two exact algorithms for the capacitated \(p\)-median problem
• The two-dimensional finite bin packing problem. I: New lower bounds for the oriented case
• A column generation approach to capacitated \(p\)-median problems
• Where are the hard knapsack problems?
• New lower bounds for the three-dimensional finite bin packing problem
• A capacitated general routing problem on mixed networks
• Worst-case analysis of maximal dual feasible functions
• Conservative scales in packing problems
• A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem
• New data-dependent dual-feasible functions and lower bounds for a two-dimensional bin-packing problem
• Solution methods for thep-median problem: An annotated bibliography
• A fundamental problem in vehicle routing
• Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem
• New classes of fast lower bounds for bin packing problems

This page was built for publication: Using dual feasible functions to construct fast lower bounds for routing and location problems