×

Experiments with a hybrid interior point/combinatorial approach for network flow problems. (English) Zbl 1177.90287

Summary: Interior point (IP) algorithms for Min Cost Flow (MCF) problems have been shown to be competitive with combinatorial approaches, at least on some problem classes and for very large instances. This is in part due to availability of specialized crossover routines for MCF; these allow early termination of the IP approach, sparing it with the final iterations where the Karush Kuhn-Tucker (KKT) systems become more difficult to solve. As the crossover procedures are nothing but combinatorial approaches to MCF that are only allowed to perform few iterations, the IP algorithm can be seen as a complex ’multiple crash start’ routine for the combinatorial ones. We report our experiments of allowing one primal-dual combinatorial algorithm to MCF to perform as many iterations as required to solve the problem after being warm-started by an IP approach. Our results show that the efficiency of the combined approach critically depends on the accurate selection of a set of parameters among very many possible ones, for which designing accurate guidelines appears not to be an easy task; however, they also show that the combined approach can be competitive with the original combinatorial algorithm, at least on some ’difficult’ instances.

MSC:

90C05 Linear programming
90C51 Interior-point methods
90B10 Deterministic network models in operations research

Software:

DIMACS; PDNET; RelaxIV
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja R. K., Network Flows: Theory, Algorithms and Applications (1993)
[2] DOI: 10.1002/(SICI)1097-0037(200003)35:2<91::AID-NET1>3.0.CO;2-T · Zbl 0957.90022 · doi:10.1002/(SICI)1097-0037(200003)35:2<91::AID-NET1>3.0.CO;2-T
[3] Resende M. G.C., Network Flows and Matching: First DIMACS Implementation Challenge 12 pp 299– (1993)
[4] DOI: 10.1137/0803025 · Zbl 0794.90014 · doi:10.1137/0803025
[5] Bertsekas, D. P. and Tseng, P. 1994. ”Relax-IV: a faster version of the Relax code for solving minimum cost flow problems”. Massachusetts Institute of Technology. LIDS-P-2276. Department of Electrical Engineering and Computer Science
[6] DOI: 10.1006/jagm.1995.0805 · Zbl 05473508 · doi:10.1006/jagm.1995.0805
[7] Kennington J. L., Algorithms for Network Programming (1980) · Zbl 0502.90056
[8] DOI: 10.1007/BF02288322 · doi:10.1007/BF02288322
[9] DOI: 10.1287/mnsc.42.12.1719 · Zbl 0893.90130 · doi:10.1287/mnsc.42.12.1719
[10] Megiddo N., ORSA Journal on Computing 3 pp 63– (1991) · Zbl 0755.90056 · doi:10.1287/ijoc.3.1.63
[11] DOI: 10.1137/0802028 · Zbl 0773.90047 · doi:10.1137/0802028
[12] Roos T., Theory and Algorithms for Linear Optimization: an Interior Point Approach (1997) · Zbl 0954.65041
[13] Wright S. J., Primal-Dual Interior-Point Methods (1997) · Zbl 0863.65031 · doi:10.1137/1.9781611971453
[14] DOI: 10.1137/S1052623498341879 · Zbl 0955.90087 · doi:10.1137/S1052623498341879
[15] DOI: 10.1023/A:1021882330897 · Zbl 1035.90101 · doi:10.1023/A:1021882330897
[16] DOI: 10.1137/S105262340240519X · Zbl 1073.90064 · doi:10.1137/S105262340240519X
[17] DOI: 10.1287/ijoc.11.4.370 · Zbl 1034.90534 · doi:10.1287/ijoc.11.4.370
[18] DOI: 10.1287/ijoc.1040.0081 · Zbl 1241.90158 · doi:10.1287/ijoc.1040.0081
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.