modeling a set S as a mixed integer linear programming problem

Question

This is actually a homework question and I am very much stumped. I have to model the following set as an MILP

S = {x,y∈R| |x| + |y| = 1}

There is no need for an objective function but an arbitrary one can be included

Answer 1

I don´t see from this single constraint, that it is a MILP or can be transformed into one. But you can remove the absolute value signs.

Let´s define $x=x^+-x^-$, where $x^+,x^- \geq 0$

Then $|x|=x^++x^-$

Similar transformation for $y$. In total you get

$x^++x^- + y^++y^- = 1$

$x^+,x^- , y^+,y^- \geq 0$

This could be a part of the standard form of a $\text{linear program (LP)}$.

Answer 2

Think of what $S$ represents graphically: the lines of a square with corners at (-1,0), (0,1), (1,0), (0,-1), so you can write $S$ as follows:

$$S=\{y= 1-x, 0\le x \le 1,0\le y \le 1 \}\cup\{y= x+1,-1\le x \le 0,0\le y \le 1\}\cup\{y= -1+x,0\le x \le 1,-1\le y \le 0 \}\cup \{ y= -x-1,-1\le x \le 0,-1\le y \le 0 \}$$

Now introduce boolean variables to decide on which line you want to be: let $w_i =1$ if and only if you are on line $i$, $i=1,…,4$, let $M$ be a very large integer, and add the following (disjunctive) constraints:

$$x+y\le 1 + M(1-\omega_1)\quad \quad x+y\ge 1 -M(1-\omega_1)$$ $$x-y\le 1 + M(1-\omega_2)\quad \quad x-y\ge 1 -M(1-\omega_2)$$ $$-x+y\le 1 + M(1-\omega_3)\quad \quad -x+y\ge 1 -M(1-\omega_3)$$ $$-x-y\le 1 + M(1-\omega_4)\quad \quad -x-y\ge 1 -M(1-\omega_4)$$

Now to make sure you are on exactly one of the sides of the square, add:

$$ \omega_1+\omega_2+\omega_3+\omega_4=1$$

Depending on what your objective function is, you might have to adjust this last constraint.

Answer 3

Kuifje is on the right track, but it's not quite there. It's true that $|x|+|y|=1$ can be expressed as $|x|+|y|\leq 1$ and $|x|+|y|\geq 1$.

The first of these is convex so we don't need to do anything special convert it to linear inequalities. There are a variety of ways to do this but let's do it this way: $$x+y\leq 1, \quad -x+y\leq 1, \quad x-y\leq 1, \quad -x-y\leq 1$$ Now for $|x|+|y|\geq 1$ which is not convex. Let's express it as $$x+y\geq 1 ~~\text{or}~~ -x+y\geq 1 ~~\text{or}~~ x-y\geq 1 ~~\text{or}~~ -x-y\geq 1$$ This is where Kuifje was going. Introduce binary variables $w_1,w_2,w_3,w_4$ and do this: $$x+y\geq 1-2w_1 ~~\text{or}~~ -x+y\geq 1-2w_2 ~~\text{or}~~ x-y\geq 1-2w_3 ~~\text{or}~~ -x-y\geq 1-2w_4$$ Consider what happens when $w_1=1$, then we have $x+y\geq -1$. But this is equivalent to $-x-y\leq 1$, which is identical to the constraint above. So when $w_1=1$, that first constraint is effectively removed. A similar argument is true when $w_2$, $w_3$, or $w_4$ is 1.

However, we don't want $w_1=w_2=w_3=w_4=1$, because then all four of those constraints would be disabled, and to satisfy our disjunction we need at least one of them active. So we need to add this: $$w_1+w_2+w_3+w_4\leq 3.$$ In summary, our constraints are $$1-2w_1 \leq +x + y \leq 1$$ $$1-2w_2 \leq -x+y \leq 1$$ $$1-2w_3 \leq +x-y \leq 1$$ $$1-2w_4 \leq -x-y \leq 1$$ $$w_1+w_2+w_3+w_4\leq 3, \quad w_1,w_2,w_3,w_4\in\{0,1\}$$ This is the closest I could come to Kuifje's method. But if we had $n$ variables here instead of $2$, this wouldn't be the best approach, because it would end up creating $2^n$ constraints and $2^n$ new variables. Suppose we want to implement the constraint $\|x\|_1 = \sum_i|x_i|= 1$ for $x\in\mathbb{R}^n$. Our first step is to create a new variable $y\in\mathbb{R}^n$ and define: $$|x_i|=y_i, \quad i=1,2,\dots, n, \quad \sum_i y_i = 1.$$ Then we use a technique similar to the above to convert $|x_i|=y_i$. Defining $w\in\{0,1\}^n$, we create these constraints: $$-y_i \leq x_i \leq y_i,~~x_i\geq y_i-2w_i,~~-x_i\geq y_i-2(1-w_i), \quad i=1,2,\dots, n$$ If $w_i=0$, we have $x_i=y_i$, and if $w_i=1$, we have $-x_i=y_i$. Since $y_i\geq 0$ is implied by the first pair of inequalities, it must be the case that $|x_i|=y_i$. So we have $4n+1$ inequalities and $2n$ new variables. For sufficiently large $n$, this is going to be better.