8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It was a long time ago since I did this, but I will give it a go. One dimension per interval with function $f_k$ (vars $x_k$) and then use slack variables $s_k$ as imitating booleans. $$s_1\cdot f_1(x_1) +s_2\cdot f_2(x_2) + s_3\cdot f_3(x_3)$$ Optimality should be in a "corner" if it is a linear problem (two of $s_k$ being 0). But wait, this will destroy linearity won't it? $\endgroup$ – mathreadler May 11 '16 at 17:23
  • $\begingroup$ @mathreadler thanks ^-^ 1 So your answer is the same as Kuifje's Option 1? 2 So the problem might have no solution since such approach destroys linearity? What about Kuifje's Option 1? 3 Do you think this problem is beyond reasonable expectation of difficulty presented to a beginning operations student with practically no background on Boolean algebra? $\endgroup$ – BCLC May 11 '16 at 17:54
  • 1
    $\begingroup$ I don't think it is identical. Kuifjes answer nr 1 is sure to be linear as it only takes the function value at the specific end-points (this works because of piecewise linearity combined with the corner solution property). I think it is a good question in any way. Maybe not suitable for an exam, but very interesting and practically useful question anyway. $\endgroup$ – mathreadler May 11 '16 at 18:10
  • $\begingroup$ @mathreadler Ah, thanks ^-^ Do you think average operations research can answer this during an exam without knowing boolean algebra? $\endgroup$ – BCLC May 11 '16 at 18:12
  • $\begingroup$ I don't really know what other courses are usually included in operations research. $\endgroup$ – mathreadler May 11 '16 at 18:23
4
+150
$\begingroup$

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-1+y_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]\}$).

$\endgroup$
  • 2
    $\begingroup$ Well, I think so. If you are familiar with boolean logic, than it should not be a problem. It is however hard to come up with this on your own if you are not used to mathematical modeling. As I said in my answer there are other options involving different types of binary variables, but they are not (in my opinion) easier than the answer I proposed. If you had never seen any question like this one in class before the exam, than it is a difficult question. $\endgroup$ – Kuifje Apr 19 '16 at 17:54
  • 1
    $\begingroup$ Lets just say that I would not be surprised if everyone failed the question. $\endgroup$ – Kuifje Apr 19 '16 at 18:24
  • 1
    $\begingroup$ I started bounty. If there are no takers, I'm giving it to you. $\endgroup$ – BCLC Apr 23 '16 at 13:44
  • 1
    $\begingroup$ @BCLC I suspect the question was written a bit hastily given the circumstances. Notice that $f$ isn't even well-defined: the domain is supposed to be $x\ge 0$, but $f(4)$ does not exist. $\endgroup$ – Erick Wong Apr 23 '16 at 14:45
  • 1
    $\begingroup$ @BCLC Well, to be honest I also read the question hastily. The title said "linear optimization" and the function wasn't convex, which seemed unreasonable. I originally thought that this was also caused by hastiness – but later I saw that the question body says "integer-linear optimization". This makes it able to handle arbitrary computation, so non-convex objective functions are fair game. $\endgroup$ – Erick Wong May 7 '16 at 15:41
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ (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. $\endgroup$ – Erick Wong May 11 '16 at 15:40
  • 1
    $\begingroup$ 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 :) $\endgroup$ – Erick Wong May 11 '16 at 16:50
  • 1
    $\begingroup$ The problem with the model as it is, is that it will never consider the third interval. For example, if $x=3$, the solver has absolutely no reason to set $y_3$ to $1$. $\endgroup$ – Kuifje May 13 '16 at 19:20
  • 1
    $\begingroup$ @BCLC Looks pretty reasonable now. Each of the terms $(y_1-x_1), (x_2-y_2), (x_3/2)$ has been carefully chosen so that when $y_i = 1$ it is equivalent to the appropriate function among $1-x, x-1, x/2$, while when $x_i=y_i=0$ it is equivalent to $0$. To achieve both aims simultaneously the trick is to replace any constant terms $c$ with $cy_i$ for the appropriate $i$. I do note that the nonnegativity conditions on $x_i$ are redundant. $\endgroup$ – Erick Wong May 14 '16 at 3:46
  • 1
    $\begingroup$ I don't actually see why that's a problem. @Kuifje Can you elaborate? $\endgroup$ – Erick Wong May 15 '16 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.