-2
$\begingroup$

Can anyone help me to find the right solution?

How can integer programming be used to ensure that X takes on values 1,3, 5 or any even number less than 100?

In practice we have a integer programming problem involving the variable $X$. We want to force $X$ to have one of the above values. In general, this is accomplished introducing some further variables and constraints.

$\endgroup$
14
  • 2
    $\begingroup$ What is $X$? Your question is very unclear, please expand. $\endgroup$ – Casteels Feb 16 '16 at 18:18
  • $\begingroup$ X is an integer variable $\endgroup$ – Roza R. Poghossian Feb 16 '16 at 18:19
  • $\begingroup$ Surely this is incomplete. If all I care about is that $X$ be one of the given values, then just return $1$. Presumably you want your output to do more than this...like maybe return each possible value with equal probability. But we really can't guess what you have in mind. $\endgroup$ – lulu Feb 16 '16 at 18:20
  • $\begingroup$ @lulu I have inserted the problem as stated in the book. $\endgroup$ – Roza R. Poghossian Feb 16 '16 at 18:22
  • 1
    $\begingroup$ I'm sure the book explains what $X$ is in greater detail. If it really is this vague, then, as I said, just take the constant $1$. That is a possible value, yes? I doubt this is an acceptable answer, but it doesn't contradict anything you have written. $\endgroup$ – lulu Feb 16 '16 at 18:24
1
$\begingroup$

As usual there many different ways to formulate these things. I actually think we can formulate the condition $x \in \{1,2,3,4,5,6,8,10,12,..,100\}$ with fewer variables than using the encoding suggested in the other answer. Probably in practice this will not make much of a difference.

Here is my attempt: \begin{align} & 6 - (1-\delta)M \le x \le 5 + \delta M\\ & 2y -(1-\delta)M \le x \le 2y+(1-\delta)M \\ & 1 \le x \le 100 \\ & x \> \text{integer}\\ & y \> \text{integer}\\ & \delta \> \text{binary} \end{align}

Basically this says: \begin{align} & \delta=0 \implies x\le 5 \\ & \delta=1 \implies x\ge 6, x = 2y \end{align}

We can choose $M=100$.

$\endgroup$
2
$\begingroup$

This is just my first idea. Maybe you can refine it in something better, exploiting the fact that the values in between $1$, $3$, $5$ i.e., $2$ and $4$, are also allowed because even. In the following I used a technique which should work for arbitrary values.

Substitute your integer variable $X$, wherever it appears, with the sum

$$ x_1+3x_2+5x_3+2x_4 $$

where $x_1,x_2,x_3,x_4\ge0$, and $x_1,x_2,x_3\le1$ and the additional constraints

$x_1+x_2+x_3\le 1$, so no more than one value $x_1,x_2,x_3$ can be $1$.

$x_4 \le 50(1-x_1-x_2-x_3)$, because, if none of the $x_1,x_2,x_3$ are 1, then the bound is $x_4\le 50$, otherwise it is like $x_4\le 0$, so $x_4$ it is forced to be $0$.

$x_1+x_2+x_3+x_4\ge 1$, at least one value is taken, so $X$ cannot be $0$.

So, if $x_1=1$, the value is 1, if $x_2=1$, the value is $3$, if $x_3=1$ the value is $5$. If $x_4\ge1$ the value of $X$ is an even integer less or equal to $100$.

$\endgroup$

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