  Let $D$ be a directed graph cellularly embedded in a surface together with
non-negative cost on its arcs. Given any integer circulation in $D$, we study
the problem of finding a minimum-cost non-negative integer circulation in $D$
that is homologous over the integers to the given circulation. A special case
of this problem arises in recent work on the stable set problem for graphs with
bounded odd cycle packing number, in which the surface is non-orientable
(Conforti et al., SODA'20).
  For orientable surfaces, polynomial-time algorithms have been obtained for
different variants of this problem. We complement these results by showing that
the convex hull of feasible solutions has a very simple polyhedral description.
  In contrast, only little seems to be known about the case of non-orientable
surfaces. We show that the problem is strongly NP-hard for general
non-orientable surfaces, and give the first polynomial-time algorithm for
surfaces of fixed genus. For the latter, we provide a characterization of
homology (over the integers) that allows us to recast the problem as a special
integer program, which can be efficiently solved using proximity results and
dynamic programming.
