News for hackers. Stuff that matters.
Re:Linear Programming: How Does It Work? by Pamar on Monday June 06, 2016 @01:54AM (#11844914)
It has been decades but I think that no, you don't need a list of best-current vertices. The solutions space is convex, so you move from one solution to a better one (or are on a edge where all solutions are identical) so the moment you get to Solution N which is < of Solution N-1 you know you have just moved over the maximum and N-1 is what you were looking for.

Basically you visit all vertex in sequence moving along the boundary of the solution space. As soon the result start decreasing you are done.

Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @02:40AM (#11845048)
You need a queue of current-best vertices when the objective function is equal best on all those vertices. Obviously you don't need to search less optimal vertices.
Re:Linear Programming: How Does It Work? by adrianN on Monday June 06, 2016 @02:58AM (#11845102)
Either you have a neighboring vertex that is strictly better than your current solution, or you have found an optimal solution. I don't think you need to store vertices with equal value, because you never backtrack.
Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @11:21AM (#11847410)
Ok, I think I'm getting it. This line from the OP confused me:

'But there’s an obvious risk of winding up in a “cycle” where you get back to a vertex that you already hit earlier–in which case the program will never terminate.'

Re:Linear Programming: How Does It Work? by sevensor on Monday June 06, 2016 @12:17PM (#11847882)
You only get a cycle if multiple vertices have the same objective function value. There's a similar problem of degeneracy, where you pivot back and forth between binding constraints on the same vertex and never go anywhere.
Re:Linear Programming: How Does It Work? by bernardom on Monday June 06, 2016 @12:53PM (#11848188)
And a way to avoid cycles in simplex is known: https://en.wikipedia.org/wiki/Bland%27s_rule
Re:Linear Programming: How Does It Work? by argonaut on Monday June 06, 2016 @04:17AM (#11845316)
You do not need to store vertices with equal value. Simplex is basically a greedy iterative algorithm - you keep moving forwards.