3 ms·
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 verti
by mathgenius 10y ago
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.
- adrianN 10y agoEither 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.
- mathgenius 10y agoOk, 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.'
- sevensor 10y agoYou 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.
- bernardom 10y agoAnd a way to avoid cycles in simplex is known: https://en.wikipedia.org/wiki/Bland%27s_rule https://en.wikipedia.org/wiki/Bland%27s_rule
- argonaut 10y agoYou do not need to store vertices with equal value. Simplex is basically a greedy iterative algorithm - you keep moving forwards.