Hello. It would be great if someone could help me with the following
problem (that I need to solve but where I am not specialized in):
First, a quick but hard question of geometry: would anyone know if the
following claim is true:
Let A and B be two parallelepipeds of any dimensions (A=[0,1]^n and
B=[0,1]^m).Let E be an affine space, and let f:A->E and g:B->E be affine maps such
that f(A) is included in g(B).Then there exists an affine map h:A->B such that f=goh.

It seems to be true but I could not prove it (the first nontrivial case is
when n=2, m=3 and f(A) and g(B) have dimension 2).
In fact this question interests me mainly as an indication of a method to
deal with the following algorithmic problem of computing the compatibility
of flows in graphs, which is the real problem I am facing and would much
appreciate to get help for :
Let M be a finite set, and let P be the set of all unordered pairs of
elements of M.
Let r be a map from M to the set R+ of positive or null real numbers, and
let s be a map from P to R+, such that the sum of r over M and the sum of
s over P are equal (we can see the graph with M as set of vertices, whose
edges are the pairs where s does not cancel).
Let A(s) be the set of maps c from MxM (deprived of its diagonal) to R+,
such that c(x,y)+c(y,x)= s{x,y}.
(note that A(s) is a parallelepiped whose dimension equals to the number
of edges of the graph)
Let f: A(s) -> {maps from M to R+} defined by

f(c)(x) = sum of c(x,y) over all y in M.

I know that the following relation X(s,r) :

    (For all subset F of M, the sum of r on F is higher than or equal to
    the sum of s over all edges included in F)
is equivalent to

    (There exists a c in A(s) such that r = f(c)).

(This problem is a maximum flow problem for which, if I understood well
the existing works in the subject, the way to test this condition X(s,r)
is by the Ford-Fulkerson algorithm, to try to build a possible preimage c
of r by f in A(s) by uses of paths in the graph...).
But this is still not the actual problem I am facing.

My problem is to deal with the condition X(s,r) generalized to the case
where s may have negative values.
I know that, if s = s1 - s2 where s1 and s2 are positive, then the
condition X(s,r) is equivalent to:
For all b in A(s2) there exists a c in A(s1) such that r + f(b) = f(c).

Of course by convexity it is enough to check this condition on all
vertices of the parallelepiped A(s2), but still this does not give a
practical computation when its dimension (the number of negative edges)
comes to hundreds or thousands (when there are thousands of edges), since
the number of vertices of a parallelepiped is exponential.
So a natural idea to make this computation practical would be to find an
affine map h: A(s2) -> A(s1) such that for all b in A(s2) we have r + f(b)
= f(h(b)).If we had the map h, the verification of this relation could be done in
polynomial time in an obvious way (by checking the edges one by one).
Now here are precisely the operations that I need to run:

To start with, say the maps s,r are equal to zero.

At each time, the program will receive the request of an elementary move
(x,y,u) where x,y are in M and u is a real number, asking to change r(x)
into r(x)+u and s{x,y} into s{x,y} + u (while all other values stay
unchanged). The problem is, then, to check whether the condition X(s,r)
remains valid (and forbid the moves for which it does not).
So, for this, my idea (do you have another method ??) is at each step to
find a possible new expression of the map h.Of course there is no problem when u>0 (the condition always stays true
and we just take the restriction of h to the new sets), so the problem is
when u<0. If it was only a matter of extending h, it would not be too
difficult: just a use of the Ford-Fulkerson algorithm (isn't it ? but
anyway do you have a good reference describing this algorithm ?).Unfortunately it may happen that the construction of the new map h
requires to find a better choice of h before extending it. But I have no
idea of how to change h as needed.
So my problem is I need a good algorithm able to find a possible new value
of h or prove its impossibility, at the request of an elementary move,
that still works with a set M with thousands of elements. (Or, any other
method to check the condition X(s,r) at each step).
Also, it would be interesting to have an algorithm that is run in the
absence of a request, to automatically "relax" the choice of h to a new
choice that has better chances to simply extend at the next move request
without complicated modifications.
Thank you very much for any help you can give.