# Integer Linear Programs: An instance or not?

Given a set of integers $\{x_0, x_1, ... , x_{n-1}, x_n\} \subseteq \mathbb{Z}$, a set of integer variables $\{y_0, y_1, ... ,y_{n-1}, y_n\} \subseteq \mathbb{Z}$ and an integer $m \in \mathbb{Z}$ is the following equation an instance of an integer linear program (ILP):

$(x_1\cdot y_1) + (x_1\cdot y_1) + \cdots + (x_{n-1}\cdot y_{n-1}) + (x_n\cdot y_n) = m$ i.e. is there an assignment of variables $y_i$ such that the equation is true? After googling around I noticed that ILPs usually involve maximising or minimising a variable, but that is not what is needed here. If not, could anyone tell me what type of problem this is and if there are any known complexity results?

• Add optimisation criterion $\max 1$ and you are good to go; the search for an admissable solution remains.
– Raphael
Oct 28, 2014 at 9:09
• This is a Diophantine equation. Oct 28, 2014 at 9:15
• thanks @FalkHüffner, i found a similar question here: cs.stackexchange.com/questions/29254/… seems like they are solvable in P-Time Oct 28, 2014 at 10:31

Your problem has a solution if and only if $m$ is a multiple of the greatest common divisor of $x_1,\ldots,x_n$. You can compute the GCD in polynomial time using the Euclidean algorithm (the version where you divide in each step rather than subtract) applied $n-1$ times.
• Is this true even if $m,x_i$ and $y_i$ can be BOTH positive and negative integers? Nov 12, 2014 at 10:26
• Yes, and in fact you have to allow the $y_i$ to be positive, negative, or zero. Otherwise this criterion is not correct. Nov 12, 2014 at 15:15