Integer programming

Question

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.

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. — lulu, Feb 16 '16 at 18:20
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. — lulu, Feb 16 '16 at 18:24
The problem is explained as I written here :) Just need to use "either or" logical constraint to get the problem resolved, but I still cannot figure it out. — Roza R. Poghossian, Feb 16 '16 at 18:26
@lulu, the problem seems complete to me, in the context of linear integer-programming. — Giovanni Resta, Feb 16 '16 at 18:37
@GiovanniResta: Ahh, I think your answer makes it a bit clearer what was intended. I still think you had to do a bit of mind-reading, but it's not as much of a stretch as I originally thought. — Brian Tung, Feb 16 '16 at 18:43
@lulu: The OP is looking for how to assert linear constraints such that $X$ is effectively restricted to the set ${1, 3, 5, 2, 4, 6, 8, 10, \ldots, 98, 100}$. — Brian Tung, Feb 16 '16 at 18:45
@RozaR.Poghossian: I think you should be able to reduce Giovanni Resta's answer to two supplementary variables $x_1, x_2$ with a bit of work. — Brian Tung, Feb 16 '16 at 18:51
What is the background of this constraint? I have never encountered a constraint like this. — Erwin Kalvelagen, Feb 18 '16 at 13:14

score 2 · Answer 1 · edited Feb 16 '16 at 21:30

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

Erwin Kalvelagen · Accepted Answer · 2016-02-16T21:58:55.803

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

Integer programming

2 Answers2