I am interested in the following flow problem, since it turns out to be equivalent to a more general problem.INPUT: A graph where each edge $e$ has an integer multiplier $q_e$, and a lower bound $b_v$ for each vertex $v$QUESTION: Is there a flow, such that the flow sent on each $e$ is a multiple of $q_e$ (in either direction), and such that the net flow in to each $v$ is greater than or equal to $b_v$?Is this problem in P or NP-complete?So far I have found it is in P if the $q$'s form a chain under division; but if to that we add upper and lower bounds to edges then it becomes NP-complete.I posted a reformulation using lattices on MO.
Quantized Unbounded Flow
ds.algorithms;graph algorithms;integer programming