A linear programming approach to the minimum maximum flow degree problem

Consider a network $\Net$ with arc capacities, a sink node and a set of source nodes, where each source node has a positive integer flow demand to be sent through $\Net$ to the sink. Each possible sending of the total demand that does not exceed the arc capacities defines a feasible flow. The sum of the flow entering and leaving a node $v$ of $\Net$ in a feasible flow is the flow degree of $v$. Given a feasible flow, its maximum flow degree is the maximum flow degree of the nodes of $\Net$. The minimum maximum flow degree problem (MMFDP) consists in determining a feasible flow such that its maximum flow degree is minimum. We introduce a mixed integer linear program for the MMFDP and show how to solve it in polynomial time. We report results of computational experiments that compares the proposed method with two other existing methods.