Divisibility constraint in Integer programming

Question

I have a simple question regarding the divisibility in integer programming

suppose the objective function is

$\text{max}\quad x_1 + x_2$

where the constraint is that the sum of $x_1$ and $x_2$ are divisible by either 5, 7 or 9

I'm wondering how can I model the constraint of divisibility?

The only solution I can think of is like

max 
x1+x2+ 0*x3


subject to 

y1+y2+y3 >= 0

y1*(x1+x2) = 5*x3*y1
y2*(x1+x2) = 7*x3*y2
y3(x1+x2) = 9*x3*y3

x1>=0,x2>=0,x3>=0

Is it correct to solve divisibility constraints like this?

Thank you!

Answer 1

Suppose $x_1+x_2$ is bounded above by some $M$; otherwise the problem is unbounded. Let $D=\{5,7,9\}$, and for $d\in D$, introduce binary variable $z_d$ and nonnegative integer variable $w_d$. You can enforce the desired behavior by imposing the following linear constraints: \begin{align} x_1 + x_2 &= \sum_{d\in D} d\cdot w_d \\ d\cdot w_d &\le M\cdot z_d &&\text{for $d\in D$}\\ \sum_{d\in D} z_d &= 1 \end{align}