Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs

Max Klimm () and Philipp Warode ()
Additional contact information
Max Klimm: Institute of Mathematics, Technische Universität Berlin, 10623 Berlin, Germany
Philipp Warode: Institute of Mathematics, Technische Universität Berlin, 10623 Berlin, Germany

Mathematics of Operations Research, 2022, vol. 47, issue 1, 812-846

Abstract: We develop algorithms solving parametric flow problems with separable, continuous, piecewise quadratic, and strictly convex cost functions. The parameter to be considered is a common multiplier on the demand of all nodes. Our algorithms compute a family of flows that are each feasible for the respective demand and minimize the costs among the feasible flows for that demand. For single commodity networks with homogenous cost functions, our algorithm requires one matrix multiplication for the initialization, a rank 1 update for each nondegenerate step and the solution of a convex quadratic program for each degenerate step. For nonhomogeneous cost functions, the initialization requires the solution of a convex quadratic program instead. For multi-commodity networks, both the initialization and every step of the algorithm require the solution of a convex program. As each step is mirrored by a breakpoint in the output this yields output-polynomial algorithms in every case.

Keywords: Primary: 90C31; secondary: 90C20; 90C49; 68Q25; 91A07; parametric quadratic program; parametric flow; computational complexity; graph Laplacian; Wardrop equilibrium (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1151 (application/pdf)

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:inm:ormoor:v:47:y:2022:i:1:p:812-846

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().