Edge Constraint satisfaction in a Directed Graph Path?
Assume first that the $x_i$ can take any arbitrary values. Then the constraint $A_i + B_i x_i = V$ just states that $V \equiv A_i \pmod{B_i}$. Two such constraints are contradictory if $A_i\not\equiv A_j \pmod{(B_i,B_j)}$, where $(B_i,B_j)$ is the GCD of $B_i$ and $B_j$. The Chinese Remainder Theorem should show (after some work) that any set of constraints in which no two are contradictory can be simultaneously satisfied. (Prove or refute!)

The constraint that $x_i \geq 0$ doesn't actually impose any further constraints. Indeed, take a solution $V$ to the original problem. By adding to $V$ a large enough multiply of $\prod_i B_i$, we obtain another solution in which all $x_i$ are non-negative.

This reduces your problem to the following problem:


  Given a directed graph and a set of forbidden pairs of edges, does there exist a path from $s$ to $t$ that doesn't contain a forbidden pair of edges?


Unfortunately, this problem is NP-complete, by reduction from SAT. Given $m$ clauses $\varphi_1,\ldots,\varphi_m$, there will be $m+1$ vertices $v_0,\ldots,v_m$. For each literal $\ell \in \varphi_i$, there is a corresponding edge from $v_{i-1}$ to $v_i$. Two complementary literals form a forbidden pair. A legal path from $v_0$ to $v_m$ exists iff the instance is satisfiable.

There are now two options:


Either your particular instance has more structure, which you can employ to get a more efficient solution;
Or your original problem is also NP-hard.