2
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ Which of your variables are integer? $\endgroup$
    – RobPratt
    Oct 19, 2020 at 2:16
  • $\begingroup$ And do you have any upper bounds on $x_1$ and $x_2$? $\endgroup$
    – RobPratt
    Oct 19, 2020 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, 2020 at 3:02
  • $\begingroup$ Do you have other constraints? Because otherwise the problem is unbounded. $\endgroup$
    – RobPratt
    Oct 19, 2020 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, 2020 at 3:05

1 Answer 1

5
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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