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$
6
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 18:12
  • $\begingroup$ I don't really know what other courses are usually included in operations research. $\endgroup$
    – mathreadler
    May 11, 2016 at 18:23

2 Answers 2

Reset to default
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)+(\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$
41
  • 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, 2016 at 17:54
  • 1
    $\begingroup$ Lets just say that I would not be surprised if everyone failed the question. $\endgroup$
    – Kuifje
    Apr 19, 2016 at 18:24
  • 1
    $\begingroup$ I started bounty. If there are no takers, I'm giving it to you. $\endgroup$
    – BCLC
    Apr 23, 2016 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, 2016 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, 2016 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$
21
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 3:46
  • 1
    $\begingroup$ I don't actually see why that's a problem. @Kuifje Can you elaborate? $\endgroup$
    – Erick Wong
    May 15, 2016 at 12:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .