solverforge_solver/phase/
dynamic_vnd.rs1use std::fmt::{self, Debug};
2use std::marker::PhantomData;
3use std::time::Instant;
4
5use solverforge_core::domain::PlanningSolution;
6use solverforge_scoring::{Director, RecordingDirector};
7use tracing::info;
8
9use crate::heuristic::r#move::Move;
10use crate::heuristic::selector::move_selector::{CandidateId, MoveCursor};
11use crate::heuristic::selector::MoveSelector;
12use crate::phase::control::{
13 settle_search_interrupt, should_interrupt_evaluation, should_interrupt_generation,
14 StepInterrupt,
15};
16use crate::phase::hard_delta::{hard_score_delta, HardScoreDelta};
17use crate::phase::vnd::telemetry::{candidate_selector_label, VndProgress};
18use crate::phase::Phase;
19use crate::scope::{PhaseScope, ProgressCallback, SolverScope, StepScope};
20use crate::stats::{format_duration, whole_units_per_second};
21
22pub struct DynamicVndPhase<S, M, MS> {
23 neighborhoods: Vec<MS>,
24 _phantom: PhantomData<(fn() -> S, fn() -> M)>,
25}
26
27impl<S, M, MS> DynamicVndPhase<S, M, MS> {
28 pub fn new(neighborhoods: Vec<MS>) -> Self {
29 Self {
30 neighborhoods,
31 _phantom: PhantomData,
32 }
33 }
34}
35
36impl<S, M, MS: Debug> Debug for DynamicVndPhase<S, M, MS> {
37 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
38 f.debug_struct("DynamicVndPhase")
39 .field("neighborhoods", &self.neighborhoods)
40 .finish()
41 }
42}
43
44impl<S, D, ProgressCb, M, MS> Phase<S, D, ProgressCb> for DynamicVndPhase<S, M, MS>
45where
46 S: PlanningSolution,
47 D: Director<S>,
48 ProgressCb: ProgressCallback<S>,
49 M: Move<S>,
50 MS: MoveSelector<S, M>,
51{
52 fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
53 let phase_name = "Variable Neighborhood Descent";
54 let mut phase_scope = PhaseScope::with_phase_type(solver_scope, 0, phase_name);
55 let phase_index = phase_scope.phase_index();
56 let mut current_score = phase_scope.calculate_score();
57 let mut progress = VndProgress::new();
58 let mut k = 0usize;
59
60 info!(
61 event = "phase_start",
62 phase = phase_name,
63 phase_index = phase_index,
64 score = %current_score,
65 );
66 phase_scope.solver_scope().report_progress();
67
68 while k < self.neighborhoods.len() {
69 let mut step_scope = StepScope::new(&mut phase_scope);
70 let mut cursor = self.neighborhoods[k].open_cursor(step_scope.score_director());
71
72 match find_best_improving_move(
73 &mut cursor,
74 &mut step_scope,
75 ¤t_score,
76 &mut progress,
77 ) {
78 MoveSearchResult::Found(selected_move, selected_score, selector_index) => {
79 step_scope.apply_committed_move(&selected_move);
80 if let Some(selector_index) = selector_index {
81 step_scope
82 .phase_scope_mut()
83 .record_selector_move_accepted(selector_index);
84 step_scope
85 .phase_scope_mut()
86 .record_selector_move_applied(selector_index);
87 } else {
88 step_scope.phase_scope_mut().record_move_accepted();
89 step_scope.phase_scope_mut().record_move_applied();
90 }
91 step_scope.set_step_score(selected_score);
92 current_score = selected_score;
93 step_scope.phase_scope_mut().update_best_solution();
94 step_scope.complete();
95 k = 0;
96 }
97 MoveSearchResult::NotFound => {
98 step_scope.complete();
99 k += 1;
100 }
101 MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
102 StepInterrupt::Restart => continue,
103 StepInterrupt::TerminatePhase => break,
104 },
105 }
106 }
107
108 phase_scope.solver_scope().report_progress();
109 let duration = phase_scope.elapsed();
110 let steps = phase_scope.step_count();
111 let speed = whole_units_per_second(progress.moves_evaluated(), duration);
112 let stats = phase_scope.stats();
113 info!(
114 event = "phase_end",
115 phase = phase_name,
116 phase_index = phase_index,
117 duration = %format_duration(duration),
118 steps = steps,
119 moves_generated = stats.moves_generated,
120 moves_evaluated = stats.moves_evaluated,
121 moves_accepted = stats.moves_accepted,
122 score_calculations = stats.score_calculations,
123 generation_time = %format_duration(stats.generation_time()),
124 evaluation_time = %format_duration(stats.evaluation_time()),
125 speed = speed,
126 score = %current_score,
127 );
128 }
129
130 fn phase_type_name(&self) -> &'static str {
131 "VariableNeighborhoodDescent"
132 }
133}
134
135enum MoveSearchResult<M, Sc> {
136 Found(M, Sc, Option<usize>),
137 NotFound,
138 Interrupted,
139}
140
141fn find_best_improving_move<S, D, ProgressCb, M, C>(
142 cursor: &mut C,
143 step_scope: &mut StepScope<'_, '_, '_, S, D, ProgressCb>,
144 current_score: &S::Score,
145 progress: &mut VndProgress,
146) -> MoveSearchResult<M, S::Score>
147where
148 S: PlanningSolution,
149 D: Director<S>,
150 ProgressCb: ProgressCallback<S>,
151 M: Move<S>,
152 C: MoveCursor<S, M>,
153{
154 let mut best: Option<(CandidateId, S::Score)> = None;
155
156 let mut generated = 0usize;
157 let mut evaluated = 0usize;
158 loop {
159 if should_interrupt_generation(step_scope, generated) {
160 return MoveSearchResult::Interrupted;
161 }
162 let generation_started = Instant::now();
163 let Some(candidate_index) = cursor.next_candidate() else {
164 break;
165 };
166 let generation_elapsed = generation_started.elapsed();
167 generated += 1;
168 let mov = cursor
169 .candidate(candidate_index)
170 .expect("discovered candidate id must remain borrowable");
171 let selector_index = cursor.selector_index(candidate_index);
172 let selector_label = selector_index.map(|_| candidate_selector_label(&mov));
173 if let Some(selector_index) = selector_index {
174 step_scope
175 .phase_scope_mut()
176 .record_selector_generated_move_with_label(
177 selector_index,
178 selector_label.as_deref().unwrap_or("selector"),
179 generation_elapsed,
180 );
181 } else {
182 step_scope
183 .phase_scope_mut()
184 .record_generated_move(generation_elapsed);
185 }
186 progress.record_generated();
187
188 if should_interrupt_evaluation(step_scope, evaluated) {
189 return MoveSearchResult::Interrupted;
190 }
191 evaluated += 1;
192 let evaluation_started = Instant::now();
193 if !mov.is_doable(step_scope.score_director()) {
194 if let Some(selector_index) = selector_index {
195 step_scope
196 .phase_scope_mut()
197 .record_selector_evaluated_move(selector_index, evaluation_started.elapsed());
198 step_scope
199 .phase_scope_mut()
200 .record_selector_move_not_doable(selector_index);
201 } else {
202 step_scope
203 .phase_scope_mut()
204 .record_evaluated_move(evaluation_started.elapsed());
205 step_scope.phase_scope_mut().record_move_not_doable();
206 }
207 progress.record_evaluated();
208 progress.maybe_report(step_scope, current_score);
209 continue;
210 }
211
212 let mut recording = RecordingDirector::new(step_scope.score_director_mut());
213 mov.do_move(&mut recording);
214 let move_score = recording.calculate_score();
215 recording.undo_changes();
216 step_scope.phase_scope_mut().record_score_calculation();
217
218 let hard_delta = hard_score_delta(*current_score, move_score);
219 match hard_delta {
220 Some(HardScoreDelta::Improving) => {
221 step_scope.phase_scope_mut().record_move_hard_improving();
222 }
223 Some(HardScoreDelta::Neutral) => {
224 step_scope.phase_scope_mut().record_move_hard_neutral();
225 }
226 Some(HardScoreDelta::Worse) => {
227 step_scope.phase_scope_mut().record_move_hard_worse();
228 }
229 None => {}
230 }
231
232 if mov.requires_hard_improvement() && hard_delta != Some(HardScoreDelta::Improving) {
233 if let Some(selector_index) = selector_index {
234 step_scope
235 .phase_scope_mut()
236 .record_selector_evaluated_move(selector_index, evaluation_started.elapsed());
237 step_scope
238 .phase_scope_mut()
239 .record_selector_move_acceptor_rejected(selector_index);
240 } else {
241 step_scope
242 .phase_scope_mut()
243 .record_evaluated_move(evaluation_started.elapsed());
244 step_scope.phase_scope_mut().record_move_acceptor_rejected();
245 }
246 progress.record_evaluated();
247 progress.maybe_report(step_scope, current_score);
248 continue;
249 }
250
251 if let Some(selector_index) = selector_index {
252 step_scope
253 .phase_scope_mut()
254 .record_selector_evaluated_move(selector_index, evaluation_started.elapsed());
255 } else {
256 step_scope
257 .phase_scope_mut()
258 .record_evaluated_move(evaluation_started.elapsed());
259 }
260 progress.record_evaluated();
261 progress.maybe_report(step_scope, current_score);
262
263 if move_score > *current_score {
264 match &best {
265 Some((_, best_score)) if move_score > *best_score => {
266 best = Some((candidate_index, move_score));
267 }
268 None => best = Some((candidate_index, move_score)),
269 _ => {}
270 }
271 }
272 }
273
274 match best {
275 Some((index, score)) => {
276 let selector_index = cursor.selector_index(index);
277 MoveSearchResult::Found(cursor.take_candidate(index), score, selector_index)
278 }
279 None => MoveSearchResult::NotFound,
280 }
281}
282
283#[cfg(test)]
284#[path = "dynamic_vnd_tests.rs"]
285mod tests;