Convert a piecewise linear non-convex function into a linear optimisation problem. Update: Problem and solution found here (p. 17, 61), although my prof's solution (formulation) is different.


Convert
$$\min z = f(x)$$
where
$$f(x) = \left\{\begin{matrix}
1-x, & 0 \le x < 1\\ 
x-1, & 1 \le x < 2\\ 
\frac{x}{2}, &  2 \le x \le 3
\end{matrix}\right.$$
s.t.
$$x \ge 0$$

into a linear integer programming problem.

What I tried:
It seems that according to this,

$$\min \ f(x) = \max(a_1x + b_1, a_2x + b_2, ..., a_mx + b_m), x \ge 0$$
is equivalent to
$$\min \ t \ \text{s.t.}$$
$$a_1x + b_1 \le t$$
$$a_2x + b_2 \le t$$
$$\vdots$$
$$a_mx + b_m \le t$$
$$x \ge 0$$


Following that, I tried
$$g(x) = \max(1-x, x-1, x/2) = \left\{\begin{matrix}
1-x, & 0 \le x \le 2/3\\ 
x-1, & x \ge 2\\ 
\frac{x}{2}, &  2/3 \le x \le 2
\end{matrix}\right.$$
If we allow only integer $x$, then we have
$$g(x) = \max(1-x, x-1, x/2) = \left\{\begin{matrix}
1-x, & x=0\\ 
x-1, & x=2\\ 
\frac{x}{2}, &  x=1 or 2
\end{matrix}\right.$$
If we allow only integer $x$ for $f$, then we have
$$f(x) = \left\{\begin{matrix}
1-x, & x=0\\ 
x-1, & x=1\\ 
\frac{x}{2}, &  x=2 or 3
\end{matrix}\right.$$
It doesn't look like $f(x) = g(x)$, w/ or w/o integer constraint. How can I approach this?

(The following is copied from an answer I deleted and comments on it)

Prof's answer (assuming I remembered question right):
Let Xi = X for ith constraint.
Minimise
$$z = (1-x_1)+(x_2-1)+(1/2)(x_3)$$
s.t.
$$0 \le x_1 \le y_1$$
$$y_2 \le x_2 \le 2y_2$$
$$2y_3 \le x_3 \le 3y_3$$
$$y_1, y_2, y_3 \in \{0,1\}$$
$$x_1,x_2,x_3 \ge 0$$

Comments below it:

(You should probably annotate this to indicate the source.) Anyway, if you suspected something was off about this solution, then you're right: it's incorrect. This formulation is similar to Kuifje's Option 3, but it incorrectly encodes the objective function. The minimum value occurs at $(y_1,y_2,y_3)=(1,0,0)$, presumably as expected, but here $(x_1,x_2,x_3)=(1,0,0)$ giving $z=−1$. The value $−1$ is never taken by the original function! The $(x_2−1)$ term should have been chosen to minimize at $0$ in the case that $y_2=0$, but it wasn't. – Erick Wong 1 hour ago 
@ErickWong I was lacking one thing: 'let xi=X for the ith constraint.' what about now? Thanks for the feedback XD honestly I haven't yet bothered to analyse any of these. We didn't discuss boolean logic. I'm about to ask my prof about this. I could have remembered the question wrong. I do remember that function and something about an integer linear programming problem – BCLC 11 mins ago   
That extra line shouldn't make a difference: it just declares the Intent of the variable $x_i$ (as an aid to the reader) but it doesn't change its value. Good luck, I do believe if the function is exactly as you remember then this answer is flawed. I haven't carefully analyzed Kuifje's answers and there may be minor typos there too :) – Erick Wong 5 mins ago
@ErickWong Edit: Thanks for the feedback XD honestly I haven't yet bothered to analyse any of these. I mean I guess I could understand if I analysed, but the point is that I don't think average student in my class can come up with this without boolean logic because we didn't discuss boolean logic. I'm about to ask my prof about this. I could have remembered the question wrong. I do remember that function and something about an integer linear programming problem. – BCLC 2 mins ago   edit   
@ErickWong THANK YOU XD – BCLC 2 mins ago   edit   
 A: There are many ways to do this. Here are three:
Option 1
Let $y_i$ be a binary that equals $1$ if and only if $x$ is in the $i^{th}$ interval ($i\in \{[0,1],[1,2],[2,3]\}$). The idea is then to express $x$ as a convex combination of the extreme points of the intervals. Therefore, we introduce variables $\lambda_0, \lambda_1,\lambda_2,\lambda_3 \in \mathbb{R}^+$ with which we will achieve this.
The objective function is
$$
f(0)\lambda_0+f(1)\lambda_1+f(2)\lambda_2+f(3)\lambda_3=\lambda_0+\lambda_2+1.5\lambda_3
$$
and the constraints are
\begin{align*}
&y_1+y_2+y_3 = 1\\
&x = 0\lambda_0+\lambda_1+2\lambda_2+3\lambda_3\\
&\lambda_0+\lambda_1+\lambda_2+\lambda_3=1\\
&y_1\le \lambda_0+\lambda_1\\
&y_2\le \lambda_1+\lambda_2\\
&y_3\le \lambda_2+\lambda_3\\
&y\in \{0,1\}\\
&\lambda\ge 0
\end{align*}
Option 2
Alternatively, you can write the objective function as
$$
f=(1-x_1)+(x_2)+(\frac{x_3}{2})
$$
with constraints
$$
x=x_1+x_2+x_3\\
x\le 3\\
y_1\le x_1 \le 1\\
y_2\le x_2 \le y_1\\
0 \le x_3 \le y_2\\
y_1,y_2\in \{0,1\}
$$
$y_1$ and $y_2$ are binaries that equal $1$ if and only if variables $x_1$ and $x_2$ reach their upper bound. This ensures that, for example, if $x=1.5$, the solver has to fix $x_1=1$ and $x_2=0.5$.
Option 3
Write the function as follows:
$$
f=(y_1-x_1)+(x_2)+(\frac{x_3}{2}+y_3)
$$
subject to
$$
x=(x_1)+(x_2+y_2)+(x_3+2y_2)\\
y_1+y_2+y_3=1\\
0\le x_1\le y_1\\
0\le x_2\le y_2\\
0\le x_3\le y_3\\
y_1,y_2,y_3\in \{0,1\}
$$
This time, binaries $y_i$ equal $1$ if and only if $x$ is in the $i^{th}$ interval ($i\in \{[0,1],[1,2],[2,3]\}$).
A: Prof's answer:
Let $X_i = X$ for ith constraint.
Minimise
$$z = (y_1-x_1)+(x_2-y_2)+(1/2)(x_3)$$
s.t.
$$0 \le x_1 \le y_1$$
$$y_2 \le x_2 \le 2y_2$$
$$2y_3 \le x_3 \le 3y_3$$
$$y_1+y_2+y_3=1$$
$$y_1, y_2, y_3 \in \{0,1\}$$
$$x_1,x_2,x_3 \ge 0$$
