A 2D Example

Here is a larger 2D example

H = {(3,1),(2,2),(4,3),(3,4),(0,5),(1,5),(5,5),(1,6),(2,7),(3,7),(1,8),(0,9),(2,10)}

M = {(9.0),(10,0),(10,1),(10,3),(8,4),(12,4),(9,5),(11,5),(6,6),(8,6),(10,6),(8,7), (9,7),(8,8),(5,8),(5,9),(7,9)}
h = 13, m = 17

Click here to view the linear program using Mangasarian's formulation

Click here to view the log file generated when solving the LP using CPLEX

Here is what the problem looks like:

Optimal Solution: a^T = [-4/3 -2/3], b = -11, all other variables are zero.
Optimal Value: 0 (implies that the two sets are linearly separable)

Lets make the sets linearly inseparable...

Add the following to H: {(6,7),(7,5),(6,4)}

Add the following to M: {(5,3),(3,9),(8,3)}
h = 16, m = 20
Click here to view the linear program using Mangasarian's formulation

Click here to view the log file generated when solving the LP using CPLEX

Here is what the new problem looks like:

Optimal Solution: a^T = [-4/3 -2/3], b = -11, y₁₆ = 2.66, z₂₀ = 4/3, all other variables are zero.
Optimal Value: 0.23 (implies that the two sets are linearly inseparable)

Note: why is the same hyperplane generated as in the above example? Perhaps you can answer this question be observing the new points which violate the hyperplane... (how far apart are they from the hyperplane? Could you visually come up with a better hyperplane than what is proposed?)

...Click here to return to the main page