[Set-Cover-CFT] Outer Refinement Procedure#4628
Conversation
| const DualState& current_dual_state; | ||
| const DualState& best_dual_state; | ||
|
|
||
| // Avoid copying unused reduced cost during subgradient |
There was a problem hiding this comment.
The DualState abstraction has been introduced to keep multipliers, LB, and reduced costs in sync. However, I noticed some overhead, and after profiling, I saw it was due to needless copies of the "best reduced costs" that can simply be computed once at the end instead.
| private: | ||
| Cost squared_norm_; | ||
|
|
||
| // This addition implements a simplified stabilization technique inspired by |
There was a problem hiding this comment.
While the subgradient seems faster at converging with this technique, the multipliers it converges to are often of poorer quality. Furthermore, there are strange interactions between this kind of technique and all the other heuristic and arbitrary parameters. For the time being, we revert to the original implementation.
| BaseInt exit_test_countdown_; | ||
| BaseInt exit_test_period_; | ||
| BaseInt last_core_update_countdown_; | ||
| BaseInt unfixed_run_extension_; |
There was a problem hiding this comment.
Custom parameter to intensify the subgradient search (i.e., spend more iterations refining the current multipliers). I often use it to manually force higher effort on the subgradient, however, it could become an algorithm parameter.
Mizux
added
Solver: Set Cover
3 participants
Hi,
This PR introduces the outer refinement procedure for the CFT heuristic.
The procedure itself is fairly simple, the main potential source of issues is integrating it cleanly into the existing structure.