solverforge_solver/phase/vnd/
phase.rs

1// Variable Neighborhood Descent phase implementation.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use solverforge_core::domain::PlanningSolution;
7use solverforge_scoring::{Director, RecordingDirector};
8
9use crate::heuristic::r#move::Move;
10use crate::heuristic::selector::MoveSelector;
11use crate::phase::control::{
12    settle_search_interrupt, should_interrupt_evaluation, should_interrupt_generation,
13    StepInterrupt,
14};
15use crate::phase::Phase;
16use crate::scope::ProgressCallback;
17use crate::scope::{PhaseScope, SolverScope, StepScope};
18
19/// Variable Neighborhood Descent phase.
20///
21/// Wraps a tuple of move selectors (neighborhoods) and explores them in sequence,
22/// restarting from the first whenever an improvement is found.
23///
24/// Uses macro-generated tuple implementations for zero type erasure.
25///
26/// # Type Parameters
27/// * `T` - Tuple of move selectors
28/// * `M` - The move type produced by all selectors
29///
30/// # Example
31///
32/// ```
33/// use solverforge_solver::phase::vnd::VndPhase;
34/// use solverforge_solver::heuristic::r#move::ChangeMove;
35/// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
36/// use solverforge_core::domain::PlanningSolution;
37/// use solverforge_core::score::SoftScore;
38///
39/// #[derive(Clone, Debug)]
40/// struct MySolution {
41///     values: Vec<Option<i32>>,
42///     score: Option<SoftScore>,
43/// }
44///
45/// impl PlanningSolution for MySolution {
46///     type Score = SoftScore;
47///     fn score(&self) -> Option<Self::Score> { self.score }
48///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
49/// }
50///
51/// fn get_value(s: &MySolution, idx: usize) -> Option<i32> {
52///     s.values.get(idx).copied().flatten()
53/// }
54/// fn set_value(s: &mut MySolution, idx: usize, v: Option<i32>) {
55///     if let Some(slot) = s.values.get_mut(idx) { *slot = v; }
56/// }
57///
58/// type MyMove = ChangeMove<MySolution, i32>;
59///
60/// let selector = ChangeMoveSelector::simple(
61///     get_value, set_value, 0, "value", vec![1, 2, 3]
62/// );
63///
64/// // Single neighborhood VND
65/// let vnd: VndPhase<_, MyMove> = VndPhase::new((selector,));
66/// ```
67pub struct VndPhase<T, M>(pub T, PhantomData<fn() -> M>);
68
69impl<T: Debug, M> Debug for VndPhase<T, M> {
70    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
71        f.debug_tuple("VndPhase").field(&self.0).finish()
72    }
73}
74
75impl<T, M> VndPhase<T, M> {
76    pub fn new(neighborhoods: T) -> Self {
77        Self(neighborhoods, PhantomData)
78    }
79}
80
81// Generates `Phase` implementations for VndPhase with tuple neighborhoods.
82macro_rules! impl_vnd_phase {
83    // Single neighborhood
84    ($idx:tt: $MS:ident) => {
85        impl<S, D, BestCb, M, $MS> Phase<S, D, BestCb> for VndPhase<($MS,), M>
86        where
87            S: PlanningSolution,
88            D: Director<S>,
89            BestCb: ProgressCallback<S>,
90            M: Move<S>,
91            $MS: MoveSelector<S, M>,
92        {
93            fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
94                let mut phase_scope = PhaseScope::new(solver_scope, 0);
95                let mut current_score = phase_scope.calculate_score();
96
97                loop {
98                    let mut step_scope = StepScope::new(&mut phase_scope);
99                    let cursor = (self.0).$idx.open_cursor(step_scope.score_director());
100
101                    match find_best_improving_move(cursor, &mut step_scope, &current_score) {
102                        MoveSearchResult::Found(selected_move, selected_score) => {
103                            selected_move.do_move(step_scope.score_director_mut());
104                            step_scope.set_step_score(selected_score);
105                            current_score = selected_score;
106                            step_scope.phase_scope_mut().update_best_solution();
107                            step_scope.complete();
108                        }
109                        MoveSearchResult::NotFound => {
110                            step_scope.complete();
111                            break;
112                        }
113                        MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
114                            StepInterrupt::Restart => continue,
115                            StepInterrupt::TerminatePhase => break,
116                        },
117                    }
118                }
119            }
120
121            fn phase_type_name(&self) -> &'static str {
122                "VariableNeighborhoodDescent"
123            }
124        }
125    };
126
127    // Multiple neighborhoods
128    ($($idx:tt: $MS:ident),+) => {
129        impl<S, D, BestCb, M, $($MS),+> Phase<S, D, BestCb> for VndPhase<($($MS,)+), M>
130        where
131            S: PlanningSolution,
132            D: Director<S>,
133            BestCb: ProgressCallback<S>,
134            M: Move<S>,
135            $($MS: MoveSelector<S, M>,)+
136        {
137            fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
138                const COUNT: usize = impl_vnd_phase!(@count $($idx),+);
139                let mut phase_scope = PhaseScope::new(solver_scope, 0);
140                let mut current_score = phase_scope.calculate_score();
141                let mut k = 0usize;
142
143                while k < COUNT {
144                    let mut step_scope = StepScope::new(&mut phase_scope);
145                    let search_result = match k {
146                        $($idx => {
147                            let cursor = (self.0).$idx.open_cursor(step_scope.score_director());
148                            find_best_improving_move(cursor, &mut step_scope, &current_score)
149                        },)+
150                        _ => MoveSearchResult::NotFound,
151                    };
152
153                    match search_result {
154                        MoveSearchResult::Found(selected_move, selected_score) => {
155                            selected_move.do_move(step_scope.score_director_mut());
156                            step_scope.set_step_score(selected_score);
157                            current_score = selected_score;
158                            step_scope.phase_scope_mut().update_best_solution();
159                            step_scope.complete();
160                            k = 0; // Restart from first neighborhood
161                        }
162                        MoveSearchResult::NotFound => {
163                            step_scope.complete();
164                            k += 1; // Try next neighborhood
165                        }
166                        MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
167                            StepInterrupt::Restart => continue,
168                            StepInterrupt::TerminatePhase => break,
169                        },
170                    }
171                }
172            }
173
174            fn phase_type_name(&self) -> &'static str {
175                "VariableNeighborhoodDescent"
176            }
177        }
178    };
179
180    // Helper: count tuple elements
181    (@count $($idx:tt),+) => {
182        0 $(+ { let _ = $idx; 1 })+
183    };
184}
185
186/* Finds the index of the best improving move in the arena.
187
188Returns `Some((index, score))` if an improving move is found, `None` otherwise.
189*/
190enum MoveSearchResult<M, Sc> {
191    Found(M, Sc),
192    NotFound,
193    Interrupted,
194}
195
196fn find_best_improving_move<S, D, BestCb, M, I>(
197    moves: I,
198    step_scope: &mut StepScope<'_, '_, '_, S, D, BestCb>,
199    current_score: &S::Score,
200) -> MoveSearchResult<M, S::Score>
201where
202    S: PlanningSolution,
203    D: Director<S>,
204    BestCb: ProgressCallback<S>,
205    M: Move<S>,
206    I: IntoIterator<Item = M>,
207{
208    let mut best: Option<(M, S::Score)> = None;
209
210    for (generated, mov) in moves.into_iter().enumerate() {
211        if should_interrupt_generation(step_scope, generated) {
212            return MoveSearchResult::Interrupted;
213        }
214
215        if should_interrupt_evaluation(step_scope, generated) {
216            return MoveSearchResult::Interrupted;
217        }
218
219        if !mov.is_doable(step_scope.score_director()) {
220            continue;
221        }
222
223        let mut recording = RecordingDirector::new(step_scope.score_director_mut());
224        mov.do_move(&mut recording);
225        let move_score = recording.calculate_score();
226        recording.undo_changes();
227
228        if move_score > *current_score {
229            match &best {
230                Some((_, best_score)) if move_score > *best_score => {
231                    best = Some((mov, move_score));
232                }
233                None => {
234                    best = Some((mov, move_score));
235                }
236                _ => {}
237            }
238        }
239    }
240
241    match best {
242        Some((mov, score)) => MoveSearchResult::Found(mov, score),
243        None => MoveSearchResult::NotFound,
244    }
245}
246
247impl_vnd_phase!(0: MS0);
248impl_vnd_phase!(0: MS0, 1: MS1);
249impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2);
250impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3);
251impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4);
252impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5);
253impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5, 6: MS6);
254impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5, 6: MS6, 7: MS7);
255
256#[cfg(test)]
257#[path = "phase_tests.rs"]
258mod tests;
solverforge_solver/phase/vnd/phase.rs

solverforge_solver/phase/vnd/
phase.rs
