# Divisibility constraint in Integer programming

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!

• Which of your variables are integer? – RobPratt Oct 19 '20 at 2:16
• And do you have any upper bounds on $x_1$ and $x_2$? – RobPratt Oct 19 '20 at 2:56
• @RobPratt x1 and x2 are integers and no upper bounds on x1 and x2, what could be a possible solution to this? – whtitefall Oct 19 '20 at 3:02
• Do you have other constraints? Because otherwise the problem is unbounded. – RobPratt Oct 19 '20 at 3:03
• @RobPratt yeah I know, the question is only to model the problem, not to solve the problem, so no other constraints... – whtitefall Oct 19 '20 at 3:05

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}