Minimum-cost flow problem

A minimum-cost flow problem is a type of optimization problem that involves finding the most efficient way to move a flow from a source node to a sink node in a network, while minimizing the cost associated with each flow. It is closely related to the maximum flow problem, which is a simpler version of the same problem where the goal is to maximize the flow without considering cost.From: Linear and Integer Optimization [2019], Airline Operations and Scheduling [2019]

Network Analysis

View Chapter

Purchase Book

Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018

Michael W. Carter, Camille C. Price, Ghaith Rabadi

One efficient technique for solving the minimum cost flow problem is a specialization of Dantzig’s Simplex algorithm, and has been called the Simplex on a graph algorithm (Kennington 1980). One implementation of this method is reported to be over 100 times faster than a general linear programming code applied to the minimum cost flow problem.

Optimizing time–cost trade-off decisions in an interval transportation problem with multiple shipment options

View Article

Journal Information

Published in Engineering Optimization, 2023

Shalabh Singh

The minimum cost flow problem is constructed by taking the minimum cost coefficient among all the multi-choice costs of the problem . Since the problem has m sources, n destinations and k multi-choice cost values, the computational complexity for taking the minimum cost is . The best-known strongly polynomial-time algorithm for an uncapacitated minimum cost flow problem with ‘n’ nodes and ‘m’ arcs is (Orlin 1993). The problem has ‘’ nodes and ‘’ arcs. So, the computational complexity is , which is a polynomial-time algorithm. To get all the Pareto optimal time–cost pairs for problem , a finite number of minimum cost flow problems () are solved, and so the above algorithm is also a polynomial-time algorithm.

Minimum-cost flow problem

Explore chapters and articles related to this topic

Network Analysis

Optimizing time–cost trade-off decisions in an interval transportation problem with multiple shipment options