Consider

$$f(x) = $$

$$1-x \ if \ 0 \le x < 1$$

$$x-1 \ if \ 1 \le x < 2$$

$$\frac{x}{2} \ if \ 2 \le x \le 3$$

where $$x \ge 0$$.

Convert

$$\min z = f(x)$$

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

$$1-x \ \text{if} \ 0 \le x \le 2/3$$

$$x-1 \ \text{if} \ x \ge 2$$

$$\frac{x}{2} \ \text{if} \ 2/3 \le x \le 2$$

If we allow only integer \(x\), then we have

$$g(x) = \max(1-x, x-1, x/2)$$

$$1-x \ \text{if} \ x=0$$

$$x-1 \ \text{if} \ x=2$$

$$\frac{x}{2} \ \text{if} \ x=1 or 2$$

If we allow only integer $x$ for $f$, then we have

$$f(x) = $$

$$1-x \ \text{if} \ x=0$$

$$x-1 \ \text{if} \ x=1$$

$$\frac{x}{2} \ \text{if} \ x=2 or 3$$

It doesn't look like $$f(x) = g(x)$$, w/ or w/o integer constraint. How can I approach this?


Based on answer below

Min

$$z = t$$

s.t.

$$1-x \le t$$

$$x-1 \le t$$

$$\frac{x}{2} \le t$$

$$x \ge 0$$

asked 19 Apr '16, 07:46

BCLC's gravatar image

BCLC
8312
accept rate: 0%

edited 01 May '16, 19:15


Well, how you posted the question, converting a piece-wise linear function into an optimization problem means that your function should be the only solution of that specific mathematical program. I am not an expert, but I have to admit that your question looks a little bit strange.

On the other hand, the link that you have provided is giving us lecture slides where something totally different is presented. Prof. Vandenberghe is showing how can one transform the problem of global optimization (minimization) of a convex piece-wise linear function into a linear program.

First, your function is not convex. Second, if we neglect the fact that your function is not convex, personally, I am not sure what you are trying to achieve in those three (sub)problems. What you wrote, i.e. what you presented are not mathematical programs. Maybe if you clarify a little bit more the goal of your question someone could help you.

I sincerely apologie if I did not understend something in your post.

link

answered 01 May '16, 14:21

RDjM's gravatar image

RDjM
3316
accept rate: 0%

edited 01 May '16, 15:21

Oh sorry thanks RDjM. I edited. Oh right my function isn't convex (It looks pretty close to convex). So now what? And hey, don't apologise. I'm glad to be helped out ^-^

(01 May '16, 17:10) BCLC

@BCLC In your case, just stick with the convex part of the function, i.e. reduce the problem and make an equivalent LP. Essentially, you don't have much to do, just follow the instructions of prof. Vandenberghe. I think that it wouldn't be appropriate to tell more, because there are some instructions on the forum about giving help. If something looks like a homework, one shouldn't help much, but give directions. You can do it. Just literally apply what prof. Vandenberghe wrote.

(01 May '16, 19:02) RDjM

RDjM, which part of Vandenberghe? His examples are for maximum between linear functions. The one I'm given isn't exactly a maximum so I tried to convert it to such. Did I do something wrong? Was on the wrong track? Do you mind pointing to a specific slide number?

(01 May '16, 19:06) BCLC

@BCLC Slide 2-4. Everything what professor wrote is applicable in your case, just read the slides carefully.

(01 May '16, 19:09) RDjM

Thanks RJjM ^-^ I edited my post. Is anything I tried correct or close? If so, which? I think what I have to do is find functions f1, f2, f3 such that $$f(x) = \max(f_1,f_2,f_3)$$ but what are those functions exactly? I don't think $$1-x,x-1,x/2$$ work

(01 May '16, 19:20) BCLC

@BCLC I am not sure what you meant by the last two/three sentences in your comment. Nevermind, you have almost done it. You need to erase something in your first post, at the end, and that's it. But please, check the theory a little bit more next time. I think that moderators are going to kill me after all this.:)

(01 May '16, 19:34) RDjM

Right so which one of my solutions is the closest to the correct one?

(01 May '16, 19:35) BCLC

RDjM how is Vandenberghe applicable if this function is not convex?

(18 May '16, 13:55) BCLC
showing 5 of 8 show 3 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×101
×25
×8
×3

Asked: 19 Apr '16, 07:46

Seen: 1,834 times

Last updated: 18 May '16, 13:55

OR-Exchange! Your site for questions, answers, and announcements about operations research.