A relaxation/decomposition algorithm for the fixed charged network problem

Bala Shetty

Naval Research Logistics (NRL), 1990, vol. 37, issue 2, 327-340

Abstract: This article makes use of relaxation in conjunction with decomposition for the solution of a fixed charge network problem. The solution technique exploits the underlying network structure. The solution approach is via the solution of a series of problem relaxation and bound adjustments. Upper bounds on the optimal objective value are obtained by use of a decomposition of the problem based on parametric changes in variable upper bounds. The Lagrangian dual provides a lower bound on the optimal objective as well as an initial allocation for the upper bounding procedure. The algorithm has been tested on 112 randomly generated problems with up to 1500 nodes, 6600 arcs, and 3000 fixed charge arcs. These test results demonstrate that even for relatively large problems, when certain convergence requirements are relaxed, our algorithm can be very effective in generating near‐optimal solutions. We obtain integer solutions that were, on the average, well within 2% of the optimum in approximately 1% of the time required by XMP to solve the continuous relaxation.

Date: 1990
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199004)37:23.0.CO;2-U

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:37:y:1990:i:2:p:327-340

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().