0

I have a feasible solution for a linear programming problem that is not necessarily a corner point. What algorithm can I use to move to a corner point feasible solution from this solution, so that I can then use this as a starting point for the Simplex method?

Edit:

Another way of thinking of this problem:

How can I start the Simplex method using an internal feasible point, not a corner point?

Dylan
  • 125

1 Answers1

1

Draw a line from your point and find the intersections of that line and all the hyperplanes formed by the constraints. Pick the nearest hyperplane. Now restrict your attention to the affine subspace described by that constraint. Draw a line from the point of intersection to find the next active constraint. Lather, rinse, repeat.

If your original problem was in the plane then your first constraint will be a line, and restricting your attention to that line, considering the points of intersection of the other constraints with the active constraint, the nearest point to your point of intersection will be your basic solution.

deinst
  • 5,646
  • What method should I use to determine the direction of each line? P.S. I am looking for an algorithm suitable for execution on a computer, i.e. not graphical methods. – Dylan Jun 11 '13 at 09:52
  • Also, the "plane" I mention is in fact a hyperplane, so the first constraint is not a line, if that makes a difference. – Dylan Jun 11 '13 at 09:52
  • If all you want is a basic solution, choose it by convenience, let all but one coordinate be 0. This is suitable for computers, it is just that linear algebra is easier, at least for me to understand visually. – deinst Jun 11 '13 at 12:29
  • It makes no difference what the dimension of the space is (except how long it takes to get to a basic solution.) – deinst Jun 11 '13 at 12:31
  • Do you think this approach is competitive in terms of performance compared with Simplex Phase 1, i.e. am I gaining anything from using this internal feasible point? – Dylan Jun 11 '13 at 14:36
  • Yes, almost certainly. The linear algebra involved is straightforward and fast, finding the intersection of a line and a hyperplane is almost trivial, and finding a line restricted to an affine subspace is not hard. In practice you can probably just add one variable to the mix at each step, further simplifying the algebra. Simplex phase 1 can wander in the wilderness for quite a while. – deinst Jun 11 '13 at 14:57
  • I'm trying to implement this. However I think the line direction has got to be consistent with all of the equality constraints. How can I easily find such a direction? – Dylan Jun 12 '13 at 15:27
  • Say you have $n$ equality constraints. Fix all but $n+1$ variables. Choose a new value for the $n+1$'st, say one more than the $n$th, solve for the other $n$ variables. You now have 2 points, and so a line. You will need to deal with the case where there are degeneracies, but in general, all you do is find another point satisfying all the active constraints by perturbing all but n coordinates and solving for the other n. – deinst Jun 12 '13 at 16:22