A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks. (English) Zbl 1487.90641

Castro, Jordi; Nasini, Stefano

Eur. J. Oper. Res. 290, No. 3, 857-869 (2021).

Summary: The computation of the Newton direction is the most time consuming step of interior-point methods. This direction was efficiently computed by a combination of Cholesky factorizations and conjugate gradients in a specialized interior-point method for block-angular structured problems. In this work we refine this algorithmic approach to solve very large instances of minimum cost flows problems in bipartite networks, for convex objective functions with diagonal Hessians (i.e., either linear, quadratic or separable nonlinear objectives). For this class of problems the specialized algorithm only required the solution of a system by conjugate gradients at each interior-point iteration, avoiding Cholesky factorizations. After analyzing the theoretical properties of the interior-point method for this kind of problems, we provide extensive computational experiments with linear and quadratic instances of up to one billion arcs (corresponding to 200 nodes and five million nodes in each subset of the node partition, respectively). For linear and quadratic instances our approach is compared with the barriers algorithms of CPLEX (both standard path-following and homogeneous-self-dual); for linear instances it is also compared with the different algorithms of the state-of-the-art network flow solver LEMON (namely: network simplex, capacity scaling, cost scaling and cycle canceling). The specialized interior-point approach significantly outperformed the other approaches in most of the linear and quadratic transportation instances tested. In particular, it always provided a solution within the time limit; and (like LEMON, and unlike CPLEX) it never exhausted the memory of the server used for the runs. For assignment problems the network algorithms in LEMON were the most efficient option.

MSC:

90C51	Interior-point methods
90B10	Deterministic network models in operations research
90C06	Large-scale problems in mathematical programming
90C35	Programming involving graphs or networks

Keywords:

large-scale optimization; interior-point methods; minimum cost flow problems; preconditioned conjugate gradient

Software:

IPM; CPLEX; LEMON; DIMACS

References:

[1]	Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2]	Ahuja, R. K., Magnanti, T. L., Orlin, J. B., & Reddy, M. R. (1995). Applications of network optimization. In Handbooks in operations research and management Science (Vol. 7), pp. 1-83. Elsevier. · Zbl 0833.90116
[3]	Alguacil, N.; Motto, A. L.; Conejo, A. J., Transmission expansion planning: A mixed-integer LP approach, IEEE Transactions on Power Systems, 18, 3, 1070-1077 (2003)
[4]	Bellavia, S.; Gondzio, J.; Morini, B., A matrix-free preconditioner for sparse symmetric positive definite systems and least-squares problems, SIAM Journal on Scientific Computing, 35, 1, A192-A211 (2013) · Zbl 1264.65036
[5]	Bergamaschi, L.; Gondzio, J.; Zilli, G., Preconditioning indefinite systems in interior point methods for optimization, Computational Optimization and Applications, 28, 2, 149-171 (2004) · Zbl 1056.90137
[6]	Boland, N.; Christiansen, J.; Dandurand, B.; Eberhard, A.; Oliveira, F., A parallelizable augmented Lagrangian method applied to large-scale non-convex-constrained optimization problems, Mathematical Programming, 175, 1-2, 503-536 (2019) · Zbl 1431.90116
[7]	Revised reprint
[8]	Cao, Y.; Laird, C. D.; Zavala, V. M., Clustering-based preconditioning for stochastic programs, Computational Optimization and Applications, 64, 2, 379-406 (2016) · Zbl 1350.90026
[9]	Castro, J., A specialized interior-point algorithm for multicommodity network flows, SIAM Journal on Optimization, 10, 3, 852-877 (2000) · Zbl 0955.90087
[10]	Castro, J., Interior-point solver for convex separable block-angular problems, Optimization Methods and Software, 31, 1, 88-109 (2016) · Zbl 1338.90455
[11]	Castro, J.; Cuesta, J., Quadratic regularizations in an interior-point method for primal block-angular problems, Mathematical Programming, 130, 2, 415-445 (2011) · Zbl 1229.90086
[12]	Castro, J.; Nasini, S., On geometrical properties of preconditioners in IPMs for classes of block-angular problems, SIAM Journal on Optimization, 27, 3, 1666-1693 (2017) · Zbl 1369.90102
[13]	Castro, J.; Nasini, S.; Saldanha-da Gama, F., A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method, Mathematical Programming, 163, 1-2, 411-444 (2017) · Zbl 1365.90169
[14]	Curtis, F. E.; Jiang, H.; Robinson, D. P., An adaptive augmented Lagrangian method for large-scale constrained optimization, Mathematical Programming, 152, 1, 201-245 (2015) · Zbl 1323.49015
[15]	Frangioni, A.; Gentile, C., New preconditioners for KKT systems of network flow problems, SIAM Journal on Optimization, 14, 3, 894-913 (2004) · Zbl 1073.90064
[16]	Goldberg, A. V.; Tarjan, R. E., Finding minimum-cost circulations by canceling negative cycles, Journal of the ACM, 36, 4, 873-886 (1989) · Zbl 0697.68063
[17]	Goldberg, A. V.; Tarjan, R. E., Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research, 15, 3, 430-466 (1990) · Zbl 0727.90024
[18]	Gondzio, J., Convergence analysis of an inexact feasible interior point method for convex quadratic programming, SIAM Journal on Optimization, 23, 3, 1510-1527 (2013) · Zbl 1286.65075
[19]	Guajardo, M.; Rönnqvist, M.; Flisberg, P.; Frisk, M., Collaborative transportation with overlapping coalitions, European Journal of Operational Research, 271, 1, 238-249 (2019) · Zbl 1403.90115
[20]	Güler, O.; Ye, Y., Convergence behaviour of interior-point algorithms, Mathematical Programming, 60, 215-228 (1993) · Zbl 0803.90087
[21]	Jenabi, M.; Fatemi-Ghomi, S.; Torabi, S.; Hosseinian, S., Acceleration strategies of Benders decomposition for the security constraints power system expansion planning, Annals of Operational Research, 235, 337-369 (2015) · Zbl 1332.90177
[22]	Network flows and matching: First DIMACS implementation challenge, (Johnson, D. S.; McGeoch, C. C. (1993), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0781.00013
[23]	Klein, M., A primal method for minimal cost flows with applications to the assignment and transportation problems, Management Science, 14, 3, 205-220 (1967) · Zbl 0178.22902
[24]	Kovács, P., Minimum-cost flow algorithms: an experimental evaluation, Optimization Methods and Software, 30, 1, 94-127 (2015) · Zbl 1320.90095
[25]	Lee, H.; Garcia-Diaz, A., A network flow approach to solve clustering problems in group technology, The International Journal of Production Research, 31, 3, 603-612 (1993)
[26]	López-Ramos, F.; Nasini, S.; Sayed, M. H., An integrated planning model in centralized power systems, European Journal of Operational Research, 287, 361-377 (2020) · Zbl 1443.91218
[27]	Mulmuley, K.; Vazirani, U. V.; Vazirani, V. V., Matching is as easy as matrix inversion, Combinatorica, 7, 1, 105-113 (1987) · Zbl 0632.68041
[28]	Mulvey, J. M., Testing of a large-scale network optimization program, Mathematical Programming, 15, 1, 291-314 (1978) · Zbl 0389.65032
[29]	Nesterov, Y., Introductory lectures on convex optimization: A basic course, 87 (2004), Kluwer · Zbl 1086.90045
[30]	Oliveira, A. R.; Sorensen, D. C., A new class of preconditioners for large-scale linear systems from interior point methods for linear programming, Linear Algebra and its Applications, 394, 1-24 (2005) · Zbl 1071.65088
[31]	Orlin, J. B., A polynomial time primal network simplex algorithm for minimum cost flows, Mathematical Programming, 78, 2, 109-129 (1997) · Zbl 0888.90058
[32]	Resende, M. G.; Veiga, G., An implementation of the dual affine scaling algorithm for minimum-cost flow on bipartite uncapacitated networks, SIAM Journal on Optimization, 3, 3, 516-537 (1993) · Zbl 0794.90014
[33]	Romero, R.; Montincelli, A.; Garcia, A.; Haffner, S., Test systems and mathematical models for transmission network expansion planning, IEE Proceedings - Generation, Transmission and Distribution, 149, 27-36 (2002)
[34]	Wright, S., Primal-dual interior-point methods (1996), SIAM: SIAM Philadelphia, PA
[35]	Zangwill, W. I., Minimum concave cost flows in certain networks, Management Science, 14, 7, 429-450 (1968) · Zbl 0159.49102