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

• Type: Article in International Scientific Journal
• Date: 2006

Authors

Dalila B.M.M. Fontes (Author) FEP; Hadjiconstantinou, E (Author) Other; Christofides, N (Author) Other

Journal

Title: Journal of Global Optimization

Vol. 34 No. 1

Pages: 97-125

ISSN: 0925-5001

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 3 Citations

Other information

Authenticus ID: P-004-Q4B

DOI: 10.1007/s10898-005-1657-y

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 29