template<typename
Index>
class operations_research::glop::DynamicMaximum< Index >
Maintains a set of elements in [0, n), each with an associated value and allows to query the element of maximum value efficiently.
This is optimized for use in the pricing step of the simplex algorithm. Basically at each simplex iterations, you want to:
1/ Get the candidate with the maximum value. The number of candidates can be close to n, or really small. You also want some randomization if several elements have an equivalent (maximum) value.
2/ Update the set of candidate and their values, where the number of update is usually a lot smaller than n. Note that in some corner cases, there are two "updates" phases, so a position can be updated twice.
The idea is to be faster than O(num_candidates) per GetMaximum(), most of the time. All updates should be in O(1) with as little overhead as possible. The algorithm here dynamically maintain the top-k (for k=32) with best effort and use it instead of doing a O(num_candidates) scan when possible.
- Note
- when O(num_updates) << n, this can have a huge effect. A basic O(1) per update, O(num_candidates) per maximum query was taking around 60% of the total time on graph40-80-1rand.pb.gz ! with the top-32 algo coded here, it is around 3%, and the number of "fast" GetMaximum() that hit the top-k heap on the first 120s of that problem was 250757 / 255659. Note that n was 282624 in this case, which is not even the biggest size we can tackle.
Note(user): This could be moved to util/ as a general class if someone wants to reuse it, it is however tuned for use in Glop pricing step and might becomes even more specific in the future.
Definition at line 61 of file pricing.h.
template<typename
Index >
Returns the index with the maximum value or Index(-1) if the set is empty and there is no possible candidate. If there are more than one candidate with the same maximum value, this will return a random one (not always uniformly if there is a large number of ties).
Optimized version if the maximum is in tops_ already.
We do two things here: 1/ Filter tops_ to only contain valid entries. This is because we never remove element, so the value of one of the element in tops might have decreased now. Note that we leave threshold_ untouched, so it can actually be lower than the minimum of the element in tops. 2/ Get the maximum of the valid elements.
The two possible sources of "invalidity".
We need to iterate over all the candidates.
- Todo
- (user): Add a mode when we do not maintain the TopK for small sizes (like n < 1000) ? The gain might not be worth the extra code though.
Definition at line 209 of file pricing.h.
1.12.0