solverforge_solver/phase/vnd/
phase.rs

1// Variable Neighborhood Descent phase implementation.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5use std::time::Instant;
6
7use solverforge_core::domain::PlanningSolution;
8use solverforge_scoring::{Director, RecordingDirector};
9use tracing::info;
10
11use crate::heuristic::r#move::Move;
12use crate::heuristic::selector::move_selector::{CandidateId, MoveCursor};
13use crate::heuristic::selector::MoveSelector;
14use crate::phase::control::{
15    settle_search_interrupt, should_interrupt_evaluation, should_interrupt_generation,
16    StepInterrupt,
17};
18use crate::phase::hard_delta::{hard_score_delta, HardScoreDelta};
19use crate::phase::vnd::telemetry::{candidate_selector_label, VndProgress};
20use crate::phase::Phase;
21use crate::scope::ProgressCallback;
22use crate::scope::{PhaseScope, SolverScope, StepScope};
23use crate::stats::{format_duration, whole_units_per_second};
24
25/// Variable Neighborhood Descent phase.
26///
27/// Wraps a tuple of move selectors (neighborhoods) and explores them in sequence,
28/// restarting from the first whenever an improvement is found.
29///
30/// Uses macro-generated tuple implementations for zero type erasure.
31///
32/// # Type Parameters
33/// * `T` - Tuple of move selectors
34/// * `M` - The move type produced by all selectors
35///
36/// # Example
37///
38/// ```
39/// use solverforge_solver::phase::vnd::VndPhase;
40/// use solverforge_solver::heuristic::r#move::ChangeMove;
41/// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
42/// use solverforge_core::domain::PlanningSolution;
43/// use solverforge_core::score::SoftScore;
44///
45/// #[derive(Clone, Debug)]
46/// struct MySolution {
47///     values: Vec<Option<i32>>,
48///     score: Option<SoftScore>,
49/// }
50///
51/// impl PlanningSolution for MySolution {
52///     type Score = SoftScore;
53///     fn score(&self) -> Option<Self::Score> { self.score }
54///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
55/// }
56///
57/// fn get_value(s: &MySolution, idx: usize, _variable_index: usize) -> Option<i32> {
58///     s.values.get(idx).copied().flatten()
59/// }
60/// fn set_value(s: &mut MySolution, idx: usize, _variable_index: usize, v: Option<i32>) {
61///     if let Some(slot) = s.values.get_mut(idx) { *slot = v; }
62/// }
63///
64/// type MyMove = ChangeMove<MySolution, i32>;
65///
66/// let selector = ChangeMoveSelector::simple(
67///     get_value, set_value, 0,  0, "value", vec![1, 2, 3]
68/// );
69///
70/// // Single neighborhood VND
71/// let vnd: VndPhase<_, MyMove> = VndPhase::new((selector,));
72/// ```
73pub struct VndPhase<T, M>(pub T, PhantomData<fn() -> M>);
74
75impl<T: Debug, M> Debug for VndPhase<T, M> {
76    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
77        f.debug_tuple("VndPhase").field(&self.0).finish()
78    }
79}
80
81impl<T, M> VndPhase<T, M> {
82    pub fn new(neighborhoods: T) -> Self {
83        Self(neighborhoods, PhantomData)
84    }
85}
86
87// Generates `Phase` implementations for VndPhase with tuple neighborhoods.
88macro_rules! impl_vnd_phase {
89    // Single neighborhood
90    ($idx:tt: $MS:ident) => {
91        impl<S, D, BestCb, M, $MS> Phase<S, D, BestCb> for VndPhase<($MS,), M>
92        where
93            S: PlanningSolution,
94            D: Director<S>,
95            BestCb: ProgressCallback<S>,
96            M: Move<S>,
97            $MS: MoveSelector<S, M>,
98        {
99            fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
100                let phase_name = "Variable Neighborhood Descent";
101                let mut phase_scope = PhaseScope::with_phase_type(solver_scope, 0, phase_name);
102                let phase_index = phase_scope.phase_index();
103                let mut current_score = phase_scope.calculate_score();
104                let mut progress = VndProgress::new();
105
106                info!(
107                    event = "phase_start",
108                    phase = phase_name,
109                    phase_index = phase_index,
110                    score = %current_score,
111                );
112                phase_scope.solver_scope().report_progress();
113
114                loop {
115                    let mut step_scope = StepScope::new(&mut phase_scope);
116                    let mut cursor = (self.0).$idx.open_cursor(step_scope.score_director());
117
118                    match find_best_improving_move(&mut cursor, &mut step_scope, &current_score, &mut progress) {
119                        MoveSearchResult::Found(selected_move, selected_score, selector_index) => {
120                            step_scope.apply_committed_move(&selected_move);
121                            if let Some(selector_index) = selector_index {
122                                step_scope
123                                    .phase_scope_mut()
124                                    .record_selector_move_accepted(selector_index);
125                                step_scope
126                                    .phase_scope_mut()
127                                    .record_selector_move_applied(selector_index);
128                            } else {
129                                step_scope.phase_scope_mut().record_move_accepted();
130                                step_scope.phase_scope_mut().record_move_applied();
131                            }
132                            step_scope.set_step_score(selected_score);
133                            current_score = selected_score;
134                            step_scope.phase_scope_mut().update_best_solution();
135                            step_scope.complete();
136                        }
137                        MoveSearchResult::NotFound => {
138                            step_scope.complete();
139                            break;
140                        }
141                        MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
142                            StepInterrupt::Restart => continue,
143                            StepInterrupt::TerminatePhase => break,
144                        },
145                    }
146                }
147
148                phase_scope.solver_scope().report_progress();
149                let duration = phase_scope.elapsed();
150                let steps = phase_scope.step_count();
151                let speed = whole_units_per_second(progress.moves_evaluated(), duration);
152                let stats = phase_scope.stats();
153                info!(
154                    event = "phase_end",
155                    phase = phase_name,
156                    phase_index = phase_index,
157                    duration = %format_duration(duration),
158                    steps = steps,
159                    moves_generated = stats.moves_generated,
160                    moves_evaluated = stats.moves_evaluated,
161                    moves_accepted = stats.moves_accepted,
162                    score_calculations = stats.score_calculations,
163                    generation_time = %format_duration(stats.generation_time()),
164                    evaluation_time = %format_duration(stats.evaluation_time()),
165                    speed = speed,
166                    score = %current_score,
167                );
168            }
169
170            fn phase_type_name(&self) -> &'static str {
171                "VariableNeighborhoodDescent"
172            }
173        }
174    };
175
176    // Multiple neighborhoods
177    ($($idx:tt: $MS:ident),+) => {
178        impl<S, D, BestCb, M, $($MS),+> Phase<S, D, BestCb> for VndPhase<($($MS,)+), M>
179        where
180            S: PlanningSolution,
181            D: Director<S>,
182            BestCb: ProgressCallback<S>,
183            M: Move<S>,
184            $($MS: MoveSelector<S, M>,)+
185        {
186            fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
187                const COUNT: usize = impl_vnd_phase!(@count $($idx),+);
188                let phase_name = "Variable Neighborhood Descent";
189                let mut phase_scope = PhaseScope::with_phase_type(solver_scope, 0, phase_name);
190                let phase_index = phase_scope.phase_index();
191                let mut current_score = phase_scope.calculate_score();
192                let mut progress = VndProgress::new();
193                let mut k = 0usize;
194
195                info!(
196                    event = "phase_start",
197                    phase = phase_name,
198                    phase_index = phase_index,
199                    score = %current_score,
200                );
201                phase_scope.solver_scope().report_progress();
202
203                while k < COUNT {
204                    let mut step_scope = StepScope::new(&mut phase_scope);
205                    let search_result = match k {
206                        $($idx => {
207                            let mut cursor = (self.0).$idx.open_cursor(step_scope.score_director());
208                            find_best_improving_move(&mut cursor, &mut step_scope, &current_score, &mut progress)
209                        },)+
210                        _ => MoveSearchResult::NotFound,
211                    };
212
213                    match search_result {
214                        MoveSearchResult::Found(selected_move, selected_score, selector_index) => {
215                            step_scope.apply_committed_move(&selected_move);
216                            if let Some(selector_index) = selector_index {
217                                step_scope
218                                    .phase_scope_mut()
219                                    .record_selector_move_accepted(selector_index);
220                                step_scope
221                                    .phase_scope_mut()
222                                    .record_selector_move_applied(selector_index);
223                            } else {
224                                step_scope.phase_scope_mut().record_move_accepted();
225                                step_scope.phase_scope_mut().record_move_applied();
226                            }
227                            step_scope.set_step_score(selected_score);
228                            current_score = selected_score;
229                            step_scope.phase_scope_mut().update_best_solution();
230                            step_scope.complete();
231                            k = 0; // Restart from first neighborhood
232                        }
233                        MoveSearchResult::NotFound => {
234                            step_scope.complete();
235                            k += 1; // Try next neighborhood
236                        }
237                        MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
238                            StepInterrupt::Restart => continue,
239                            StepInterrupt::TerminatePhase => break,
240                        },
241                    }
242                }
243
244                phase_scope.solver_scope().report_progress();
245                let duration = phase_scope.elapsed();
246                let steps = phase_scope.step_count();
247                let speed = whole_units_per_second(progress.moves_evaluated(), duration);
248                let stats = phase_scope.stats();
249                info!(
250                    event = "phase_end",
251                    phase = phase_name,
252                    phase_index = phase_index,
253                    duration = %format_duration(duration),
254                    steps = steps,
255                    moves_generated = stats.moves_generated,
256                    moves_evaluated = stats.moves_evaluated,
257                    moves_accepted = stats.moves_accepted,
258                    score_calculations = stats.score_calculations,
259                    generation_time = %format_duration(stats.generation_time()),
260                    evaluation_time = %format_duration(stats.evaluation_time()),
261                    speed = speed,
262                    score = %current_score,
263                );
264            }
265
266            fn phase_type_name(&self) -> &'static str {
267                "VariableNeighborhoodDescent"
268            }
269        }
270    };
271
272    // Helper: count tuple elements
273    (@count $($idx:tt),+) => {
274        0 $(+ { let _ = $idx; 1 })+
275    };
276}
277
278/* Finds the index of the best improving move in the arena.
279
280Returns `Some((index, score))` if an improving move is found, `None` otherwise.
281*/
282enum MoveSearchResult<M, Sc> {
283    Found(M, Sc, Option<usize>),
284    NotFound,
285    Interrupted,
286}
287
288fn find_best_improving_move<S, D, BestCb, M, C>(
289    cursor: &mut C,
290    step_scope: &mut StepScope<'_, '_, '_, S, D, BestCb>,
291    current_score: &S::Score,
292    progress: &mut VndProgress,
293) -> MoveSearchResult<M, S::Score>
294where
295    S: PlanningSolution,
296    D: Director<S>,
297    BestCb: ProgressCallback<S>,
298    M: Move<S>,
299    C: MoveCursor<S, M>,
300{
301    let mut best: Option<(CandidateId, S::Score)> = None;
302
303    let mut generated = 0usize;
304    let mut evaluated = 0usize;
305    loop {
306        if should_interrupt_generation(step_scope, generated) {
307            return MoveSearchResult::Interrupted;
308        }
309        let generation_started = Instant::now();
310        let Some(candidate_index) = cursor.next_candidate() else {
311            break;
312        };
313        let generation_elapsed = generation_started.elapsed();
314        generated += 1;
315        let mov = cursor
316            .candidate(candidate_index)
317            .expect("discovered candidate id must remain borrowable");
318        let selector_index = cursor.selector_index(candidate_index);
319        let selector_label = selector_index.map(|_| candidate_selector_label(&mov));
320        if let Some(selector_index) = selector_index {
321            step_scope
322                .phase_scope_mut()
323                .record_selector_generated_move_with_label(
324                    selector_index,
325                    selector_label.as_deref().unwrap_or("selector"),
326                    generation_elapsed,
327                );
328        } else {
329            step_scope
330                .phase_scope_mut()
331                .record_generated_move(generation_elapsed);
332        }
333        progress.record_generated();
334
335        if should_interrupt_evaluation(step_scope, evaluated) {
336            return MoveSearchResult::Interrupted;
337        }
338        evaluated += 1;
339        let evaluation_started = Instant::now();
340        if !mov.is_doable(step_scope.score_director()) {
341            if let Some(selector_index) = selector_index {
342                step_scope
343                    .phase_scope_mut()
344                    .record_selector_evaluated_move(selector_index, evaluation_started.elapsed());
345                step_scope
346                    .phase_scope_mut()
347                    .record_selector_move_not_doable(selector_index);
348            } else {
349                step_scope
350                    .phase_scope_mut()
351                    .record_evaluated_move(evaluation_started.elapsed());
352                step_scope.phase_scope_mut().record_move_not_doable();
353            }
354            progress.record_evaluated();
355            progress.maybe_report(step_scope, current_score);
356            continue;
357        }
358
359        let mut recording = RecordingDirector::new(step_scope.score_director_mut());
360        mov.do_move(&mut recording);
361        let move_score = recording.calculate_score();
362        recording.undo_changes();
363        step_scope.phase_scope_mut().record_score_calculation();
364
365        let hard_delta = hard_score_delta(*current_score, move_score);
366        match hard_delta {
367            Some(HardScoreDelta::Improving) => {
368                step_scope.phase_scope_mut().record_move_hard_improving();
369            }
370            Some(HardScoreDelta::Neutral) => {
371                step_scope.phase_scope_mut().record_move_hard_neutral();
372            }
373            Some(HardScoreDelta::Worse) => {
374                step_scope.phase_scope_mut().record_move_hard_worse();
375            }
376            None => {}
377        }
378
379        if mov.requires_hard_improvement() && hard_delta != Some(HardScoreDelta::Improving) {
380            if let Some(selector_index) = selector_index {
381                step_scope
382                    .phase_scope_mut()
383                    .record_selector_evaluated_move(selector_index, evaluation_started.elapsed());
384                step_scope
385                    .phase_scope_mut()
386                    .record_selector_move_acceptor_rejected(selector_index);
387            } else {
388                step_scope
389                    .phase_scope_mut()
390                    .record_evaluated_move(evaluation_started.elapsed());
391                step_scope.phase_scope_mut().record_move_acceptor_rejected();
392            }
393            progress.record_evaluated();
394            progress.maybe_report(step_scope, current_score);
395            continue;
396        }
397
398        if let Some(selector_index) = selector_index {
399            step_scope
400                .phase_scope_mut()
401                .record_selector_evaluated_move(selector_index, evaluation_started.elapsed());
402        } else {
403            step_scope
404                .phase_scope_mut()
405                .record_evaluated_move(evaluation_started.elapsed());
406        }
407        progress.record_evaluated();
408        progress.maybe_report(step_scope, current_score);
409
410        if move_score > *current_score {
411            match &best {
412                Some((_, best_score)) if move_score > *best_score => {
413                    best = Some((candidate_index, move_score));
414                }
415                None => {
416                    best = Some((candidate_index, move_score));
417                }
418                _ => {}
419            }
420        }
421    }
422
423    match best {
424        Some((index, score)) => {
425            let selector_index = cursor.selector_index(index);
426            MoveSearchResult::Found(cursor.take_candidate(index), score, selector_index)
427        }
428        None => MoveSearchResult::NotFound,
429    }
430}
431
432impl_vnd_phase!(0: MS0);
433impl_vnd_phase!(0: MS0, 1: MS1);
434impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2);
435impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3);
436impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4);
437impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5);
438impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5, 6: MS6);
439impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5, 6: MS6, 7: MS7);
440
441#[cfg(test)]
442#[path = "phase_tests.rs"]
443mod tests;
solverforge_solver/phase/vnd/phase.rs

solverforge_solver/phase/vnd/
phase.rs
