Linear Programming - Separation of Points

[lockedup]

Homework Statement

I made this problem up as an example for a bigger problem I have to do. P = {(-2,4),(1,3)} and Q = {(-1,1),(0,0)}. I need to use linear programming to find the best line to go between them.

Homework Equations

Max d
subject to:
y_{i}≥ax_{i}+b+d (for all points above the line (P))
y_{i}≤ax_{i}+b-d (for all points below the line (Q))

The Attempt at a Solution

Max d
subject to:
4≥-2a+b+d
3≥ a+b+d
1≤ -a+b-d
0≤ b-d

I put this into Excel (the file is attached) and it's telling me that it is not feasible. I'm trying to do the Simplex Algorithm by hand but it is taking forever. I'm thinking that maybe I don't have it set up right in Excel. Any suggestions? Thanks in advance for any help you all can give!

 

[Ray Vickson]

Homework Statement

I made this problem up as an example for a bigger problem I have to do. P = {(-2,4),(1,3)} and Q = {(-1,1),(0,0)}. I need to use linear programming to find the best line to go between them.

Homework Equations

Max d
subject to:
y_{i}≥ax_{i}+b+d (for all points above the line (P))
y_{i}≤ax_{i}+b-d (for all points below the line (Q))

The Attempt at a Solution

Max d
subject to:
4≥-2a+b+d
3≥ a+b+d
1≤ -a+b-d
0≤ b-d

I put this into Excel (the file is attached) and it's telling me that it is not feasible. I'm trying to do the Simplex Algorithm by hand but it is taking forever. I'm thinking that maybe I don't have it set up right in Excel. Any suggestions? Thanks in advance for any help you all can give!

I assume you want to minimize the maximum vertical distance from the line to the four points. The absolute distance between point P1=(-2,4) and line y = ax + b is 4 - a(-2)-b, and you want the max absolute deviation z to be at least that large, so you need z >= 4+2a-b or z -2a+b>= 4; this is different from your first constraint (my z = your d). Use similar reasoning for the other three points, then minimize z. I get a perfectly well-defined optimal solution.

RGV

 

[lockedup]

I assume you want to minimize the maximum vertical distance from the line to the four points. The absolute distance between point P1=(-2,4) and line y = ax + b is 4 - a(-2)-b, and you want the max absolute deviation z to be at least that large, so you need z >= 4+2a-b or z -2a+b>= 4; this is different from your first constraint (my z = your d). Use similar reasoning for the other three points, then minimize z. I get a perfectly well-defined optimal solution.

RGV

I'm really sorry. I've read your post a hundred times and I don't understand what you're trying to say. It seems like you just rewrote z in terms of my first constraint. ?

 

[Ray Vickson]

Well, you say that when you run your formulation you get a signal that the problem is infeasible, However, when I run your formulation (with the added constraint d >= 0) i get the solution a=-1, b=0, d=0. The resulting line y = -x passes exactly through points Q but misses points P and has positive (absolute) errors at point P. Thus, whatever your d may be, it is NOT the maximum absolute error!

For point P1 = (-2,4) the error is 4 - [a*(-2)+b], and assuming the line lies below (-2,4), this is *also* the absolute error at P1. At P2 = (1,3) the (absolute) error is 3 - [a*1+b]. At Q1=(-1,1) the absolute error is [a*(-1) + b]-1 (because Q1 lies above the line) and at Q2 = (0,0) the absolute error is [a*0+b]-0. To get the minimum of the largest absolute error, we just need to minimize a variable, z (or d, or whatever), subject to z being >= all the individual absolute errors; minimizing z will slam z down until it reaches one of the absolute errors, and since z is >= all of them, it will equal the largest of them; furthermore, this largest will be forced to be a small as possible, because a and b are adjusted to give the minimum possible value. So, the problem is:
min z,
subject to
z >= 4 +2a-b (from P1),
z >= 3-a-b (from P2),
z >= -a+b-1 (from Q1),
z >= b (from Q2)

This problem has optimal solution a = -1/3, b = 5/3, z = 5/3, so I get the line y = 5/3 - x/3. (Note that when using an LP package on this problem we need to permit negative values of a and/or b.)

RGV

 

[Ray Vickson]

Well, you say that when you run your formulation you get a signal that the problem is infeasible, However, when I run your formulation (with the added constraint d >= 0) i get the solution a=-1, b=0, d=0. The resulting line y = -x passes exactly through points Q but misses points P and has positive (absolute) errors at point P. Thus, whatever your d may be, it is NOT the maximum absolute error!

For point P1 = (-2,4) the error is 4 - [a*(-2)+b], and assuming the line lies below (-2,4), this is *also* the absolute error at P1. At P2 = (1,3) the (absolute) error is 3 - [a*1+b]. At Q1=(-1,1) the absolute error is [a*(-1) + b]-1 (because Q1 lies above the line) and at Q2 = (0,0) the absolute error is [a*0+b]-0. To get the minimum of the largest absolute error, we just need to minimize a variable, z (or d, or whatever), subject to z being >= all the individual absolute errors; minimizing z will slam z down until it reaches one of the absolute errors, and since z is >= all of them, it will equal the largest of them; furthermore, this largest will be forced to be a small as possible, because a and b are adjusted to give the minimum possible value. So, the problem is:
min z,
subject to
z >= 4 +2a-b (from P1),
z >= 3-a-b (from P2),
z >= -a+b-1 (from Q1),
z >= b (from Q2)

This problem has optimal solution a = -1/3, b = 5/3, z = 5/3, so I get the line y = 5/3 - x/3. (Note that when using an LP package on this problem we need to permit negative values of a and/or b.)

RGV

Sorry: I meant to say that Q1 lies *below* the line (as does Q2). I would have edited the post if I could find an "edit" button, but this now seems to be gone!

RGV

 

[lockedup]

You're going to think I'm really dumb but I figured out what I was doing wrong. I did not use the right cells for my constraints in the solver.

 

[Ray Vickson]

You're going to think I'm really dumb but I figured out what I was doing wrong. I did not use the right cells for my constraints in the solver.

That is a common type of mistake, which is why when I was teaching I always strongly advised my students to use _names_. For example, if you have a block of variable cells in Solver, you can give them a name, such as 'Vars'. Then you can just type the word Vars in the variable cells menu tab. This makes model development easier and helps to avoid errors; also, it makes it easy to do absolute addressing, so you don't need to use the $ sign to pin down row or column locations.

RGV