Find minimum of the sigma

Question

Is there any polynomial algorithm to finding x₁,x₂,...,x_n for fixed a_i,j,p_i,j and g_i,j and (0 < i,j <= n) such that minimize sigma{p_i,jc_i,j} where :

a_i,j+x_i-x_j = c_i,j (mod g_i,j) , -1< c_i,j < g_i,j

Answer 1

x = a (mod b) is the same as: there is an integer q such that a + qb = x is integer, therefore, x = a (mod b) constraint is equivalent to x - bW = a, W >= 0, W is integral, i.e., your problem can be reformulated as a mixed-integer program, which is know to be NP-hard problem.