Lower Bounds from State Space Relaxations for Concave Cost Network Flow Problems |
| |
Authors: | Dalila B M M Fontes Eleni Hadjiconstantinou Nicos Christofides |
| |
Institution: | (1) LIACC, Faculdade de Economia da Universidade do Porto Rua Dr. Roberto Frias, 4200-464 Porto, Portugal;(2) Tanaka Business School, Imperial College London South Kensington Campus, London, SW7 2AZ, UK |
| |
Abstract: | In this paper we obtain Lower Bounds (LBs) to concave cost network flow problems. The LBs are derived from state space relaxations
of a dynamic programming formulation, which involve the use of non-injective mapping functions guaranteing a reduction on
the cardinality of the state space. The general state space relaxation procedure is extended to address problems involving
transitions that go across several stages, as is the case of network flow problems. Applications for these LBs include: estimation
of the quality of heuristic solutions; local search methods that use information of the LB solution structure to find initial
solutions to restart the search (Fontes et al., 2003, Networks, 41, 221–228); and branch-and-bound (BB) methods having as
a bounding procedure a modified version of the LB algorithm developed here, (see Fontes et al., 2005a). These LBs are iteratively
improved by penalizing, in a Lagrangian fashion, customers not exactly satisfied or by performing state space modifications.
Both the penalties and the state space are updated by using the subgradient method. Additional constraints are developed to
improve further the LBs by reducing the searchable space. The computational results provided show that very good bounds can
be obtained for concave cost network flow problems, particularly for fixed-charge problems. |
| |
Keywords: | concave cost network flows dynamic programming lower bounds state space relaxation |
本文献已被 SpringerLink 等数据库收录! |
|