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

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


Is it correct to solve divisibility constraints like this?

Thank you!

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.