-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$

closed as unclear what you're asking by Casteels, lulu, Morgan Rodgers, Leucippus, corindo Feb 17 '16 at 2:03

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.