The min-cost flow problem's integrality theorem states that given "integral data", there is always an integral solution to the problem that corresponds to minimum-cost flow. The notion of integral data is slightly confusing to me as most papers, tutorials say that the demands, supplies and capacities should be integral. Now, a capacity constraint is typically represented as
l_i <= c_i <= u_i
where l_i
is the lower bound on the capacity of edge i
, and u_i
is the upper bound. In order for the integrality theorem to hold, is it enough that l_i and u_i
are integers? The doubt comes from the fact that this doesn't necessarily mean that the flows are always integers themselves as for example, for l_i = 0, u_i = 1
, edge i
can have a flow of 0.5.
Yes, that is exactly what the integrality theorem says.
If all of the l_i
and u_i
are integers, and any feasible solution exists, then there must exist a solution where all flows are integers.
This does not mean that all solutions must be integers. Just that at least one will be.