Lower bounds from state space relaxations for concave cost network flow problems

DOI10.1007/S10898-005-1657-YMaRDI QIDQ2494472zbMATH OpenOpenAlexFDO

Authors Dalila B. M. M. Fontes, Eleni Hadjiconstantinou, Nicos Christofides

Publication date 28 June 2006

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-005-1657-y

zbMATH Keywords

dynamic programminglower boundsstate space relaxationconcave cost network flows

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10) Dynamic programming (90C39)

Recommendations

• A branch-and-bound algorithm for concave network flow problems
• A Lagrangean heuristic for the capacitated concave minimum cost network flow problem
• LP relaxations better than convexification for multicommodity network optimization problems with step increasing cost functions
• An improved branch and bound algorithm for minimum concave cost network flow problems
• Upper bounds for single-source uncapacitated concave minimum-cost network flow problems

Cites work

• A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
• A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems
• A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations
• A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure
• Algorithms for large scale set covering problems
• An algorithm for the min concave cost flow problem
• An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
• An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks
• Analysis of a flow problem with fixed charges
• Global search algorithms for minimum concave-cost network flow problems
• Linear approximations in a dynamic programming approach for the uncapacitated single-source minimum concave cost network flow problem in acyclic networks.
• Minimum Concave Cost Flows in Certain Networks
• Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach
• State-space relaxation procedures for the computation of bounds to routing problems
• Upper bounds for single-source uncapacitated concave minimum-cost network flow problems
• Validation of subgradient optimization

Cited in

(4)

• A branch-and-bound algorithm for concave network flow problems
• A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems
• scientific article; zbMATH DE number 2086966 (Why is no real title available?)
• A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem

Describes a project that uses

Uses Software

• OR-Library

This page was built for publication: Lower bounds from state space relaxations for concave cost network flow problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494472)