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
Best Answer
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]\}$).