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, MoveArena};
10use crate::heuristic::selector::MoveSelector;
11use crate::phase::control::{
12    append_interruptibly, settle_search_interrupt, should_interrupt_evaluation, StepInterrupt,
13};
14use crate::phase::Phase;
15use crate::scope::ProgressCallback;
16use crate::scope::{PhaseScope, SolverScope, StepScope};
17
18/// Variable Neighborhood Descent phase.
19///
20/// Wraps a tuple of move selectors (neighborhoods) and explores them in sequence,
21/// restarting from the first whenever an improvement is found.
22///
23/// Uses macro-generated tuple implementations for zero type erasure.
24///
25/// # Type Parameters
26/// * `T` - Tuple of move selectors
27/// * `M` - The move type produced by all selectors
28///
29/// # Example
30///
31/// ```
32/// use solverforge_solver::phase::vnd::VndPhase;
33/// use solverforge_solver::heuristic::r#move::ChangeMove;
34/// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
35/// use solverforge_core::domain::PlanningSolution;
36/// use solverforge_core::score::SoftScore;
37///
38/// #[derive(Clone, Debug)]
39/// struct MySolution {
40///     values: Vec<Option<i32>>,
41///     score: Option<SoftScore>,
42/// }
43///
44/// impl PlanningSolution for MySolution {
45///     type Score = SoftScore;
46///     fn score(&self) -> Option<Self::Score> { self.score }
47///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
48/// }
49///
50/// fn get_value(s: &MySolution, idx: usize) -> Option<i32> {
51///     s.values.get(idx).copied().flatten()
52/// }
53/// fn set_value(s: &mut MySolution, idx: usize, v: Option<i32>) {
54///     if let Some(slot) = s.values.get_mut(idx) { *slot = v; }
55/// }
56///
57/// type MyMove = ChangeMove<MySolution, i32>;
58///
59/// let selector = ChangeMoveSelector::simple(
60///     get_value, set_value, 0, "value", vec![1, 2, 3]
61/// );
62///
63/// // Single neighborhood VND
64/// let vnd: VndPhase<_, MyMove> = VndPhase::new((selector,));
65/// ```
66pub struct VndPhase<T, M>(pub T, PhantomData<fn() -> M>);
67
68impl<T: Debug, M> Debug for VndPhase<T, M> {
69    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
70        f.debug_tuple("VndPhase").field(&self.0).finish()
71    }
72}
73
74impl<T, M> VndPhase<T, M> {
75    pub fn new(neighborhoods: T) -> Self {
76        Self(neighborhoods, PhantomData)
77    }
78}
79
80// Generates `Phase` implementations for VndPhase with tuple neighborhoods.
81macro_rules! impl_vnd_phase {
82    // Single neighborhood
83    ($idx:tt: $MS:ident) => {
84        impl<S, D, BestCb, M, $MS> Phase<S, D, BestCb> for VndPhase<($MS,), M>
85        where
86            S: PlanningSolution,
87            D: Director<S>,
88            BestCb: ProgressCallback<S>,
89            M: Move<S>,
90            $MS: MoveSelector<S, M>,
91        {
92            fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
93                let mut arena = MoveArena::<M>::new();
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                    arena.reset();
100                    let generation_interrupted = {
101                        let iter = (self.0).$idx.iter_moves(step_scope.score_director());
102                        append_interruptibly(&step_scope, &mut arena, iter)
103                    };
104                    if generation_interrupted {
105                        match settle_search_interrupt(&mut step_scope) {
106                            StepInterrupt::Restart => continue,
107                            StepInterrupt::TerminatePhase => break,
108                        }
109                    }
110
111                    match find_best_improving_move_index(&arena, &mut step_scope, &current_score) {
112                        MoveSearchResult::Found(selected_index, selected_score) => {
113                            let selected_move = arena.take(selected_index);
114                            selected_move.do_move(step_scope.score_director_mut());
115                            step_scope.set_step_score(selected_score);
116                            current_score = selected_score;
117                            step_scope.phase_scope_mut().update_best_solution();
118                            step_scope.complete();
119                        }
120                        MoveSearchResult::NotFound => {
121                            step_scope.complete();
122                            break;
123                        }
124                        MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
125                            StepInterrupt::Restart => continue,
126                            StepInterrupt::TerminatePhase => break,
127                        },
128                    }
129                }
130            }
131
132            fn phase_type_name(&self) -> &'static str {
133                "VariableNeighborhoodDescent"
134            }
135        }
136    };
137
138    // Multiple neighborhoods
139    ($($idx:tt: $MS:ident),+) => {
140        impl<S, D, BestCb, M, $($MS),+> Phase<S, D, BestCb> for VndPhase<($($MS,)+), M>
141        where
142            S: PlanningSolution,
143            D: Director<S>,
144            BestCb: ProgressCallback<S>,
145            M: Move<S>,
146            $($MS: MoveSelector<S, M>,)+
147        {
148            fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
149                const COUNT: usize = impl_vnd_phase!(@count $($idx),+);
150                let mut arena = MoveArena::<M>::new();
151                let mut phase_scope = PhaseScope::new(solver_scope, 0);
152                let mut current_score = phase_scope.calculate_score();
153                let mut k = 0usize;
154
155                while k < COUNT {
156                    let mut step_scope = StepScope::new(&mut phase_scope);
157                    arena.reset();
158
159                    // Populate arena from neighborhood k
160                    match k {
161                        $($idx => {
162                            let generation_interrupted = {
163                                let iter = (self.0).$idx.iter_moves(step_scope.score_director());
164                                append_interruptibly(&step_scope, &mut arena, iter)
165                            };
166                            if generation_interrupted {
167                                match settle_search_interrupt(&mut step_scope) {
168                                    StepInterrupt::Restart => continue,
169                                    StepInterrupt::TerminatePhase => break,
170                                }
171                            }
172                        },)+
173                        _ => {}
174                    }
175
176                    match find_best_improving_move_index(&arena, &mut step_scope, &current_score) {
177                        MoveSearchResult::Found(selected_index, selected_score) => {
178                            let selected_move = arena.take(selected_index);
179                            selected_move.do_move(step_scope.score_director_mut());
180                            step_scope.set_step_score(selected_score);
181                            current_score = selected_score;
182                            step_scope.phase_scope_mut().update_best_solution();
183                            step_scope.complete();
184                            k = 0; // Restart from first neighborhood
185                        }
186                        MoveSearchResult::NotFound => {
187                            step_scope.complete();
188                            k += 1; // Try next neighborhood
189                        }
190                        MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
191                            StepInterrupt::Restart => continue,
192                            StepInterrupt::TerminatePhase => break,
193                        },
194                    }
195                }
196            }
197
198            fn phase_type_name(&self) -> &'static str {
199                "VariableNeighborhoodDescent"
200            }
201        }
202    };
203
204    // Helper: count tuple elements
205    (@count $($idx:tt),+) => {
206        0 $(+ { let _ = $idx; 1 })+
207    };
208}
209
210/* Finds the index of the best improving move in the arena.
211
212Returns `Some((index, score))` if an improving move is found, `None` otherwise.
213*/
214enum MoveSearchResult<Sc> {
215    Found(usize, Sc),
216    NotFound,
217    Interrupted,
218}
219
220fn find_best_improving_move_index<S, D, BestCb, M>(
221    arena: &MoveArena<M>,
222    step_scope: &mut StepScope<'_, '_, '_, S, D, BestCb>,
223    current_score: &S::Score,
224) -> MoveSearchResult<S::Score>
225where
226    S: PlanningSolution,
227    D: Director<S>,
228    BestCb: ProgressCallback<S>,
229    M: Move<S>,
230{
231    let mut best: Option<(usize, S::Score)> = None;
232
233    for i in 0..arena.len() {
234        if should_interrupt_evaluation(step_scope, i) {
235            return MoveSearchResult::Interrupted;
236        }
237
238        let m = arena.get(i).unwrap();
239
240        if !m.is_doable(step_scope.score_director()) {
241            continue;
242        }
243
244        let mut recording = RecordingDirector::new(step_scope.score_director_mut());
245        m.do_move(&mut recording);
246        let move_score = recording.calculate_score();
247        recording.undo_changes();
248
249        if move_score > *current_score {
250            match &best {
251                Some((_, best_score)) if move_score > *best_score => {
252                    best = Some((i, move_score));
253                }
254                None => {
255                    best = Some((i, move_score));
256                }
257                _ => {}
258            }
259        }
260    }
261
262    match best {
263        Some((index, score)) => MoveSearchResult::Found(index, score),
264        None => MoveSearchResult::NotFound,
265    }
266}
267
268impl_vnd_phase!(0: MS0);
269impl_vnd_phase!(0: MS0, 1: MS1);
270impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2);
271impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3);
272impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4);
273impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5);
274impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5, 6: MS6);
275impl_vnd_phase!(0: MS0, 1: MS1, 2: MS2, 3: MS3, 4: MS4, 5: MS5, 6: MS6, 7: MS7);
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280    use crate::heuristic::r#move::ChangeMove;
281    use crate::heuristic::selector::ChangeMoveSelector;
282    use crate::test_utils::{
283        create_nqueens_director, get_queen_row, set_queen_row, NQueensSolution,
284    };
285    type NQueensMove = ChangeMove<NQueensSolution, i64>;
286
287    fn create_move_selector(
288        values: Vec<i64>,
289    ) -> ChangeMoveSelector<
290        NQueensSolution,
291        i64,
292        crate::heuristic::selector::FromSolutionEntitySelector,
293        crate::heuristic::selector::StaticValueSelector<NQueensSolution, i64>,
294    > {
295        ChangeMoveSelector::simple(get_queen_row, set_queen_row, 0, "row", values)
296    }
297
298    #[test]
299    fn test_vnd_improves_solution() {
300        let director = create_nqueens_director(&[0, 0, 0, 0]);
301        let mut solver_scope = SolverScope::new(director);
302
303        let initial_score = solver_scope.calculate_score();
304
305        let values: Vec<i64> = (0..4).collect();
306        let mut phase: VndPhase<_, NQueensMove> = VndPhase::new((
307            create_move_selector(values.clone()),
308            create_move_selector(values),
309        ));
310
311        phase.solve(&mut solver_scope);
312
313        let final_score = solver_scope.best_score().copied().unwrap_or(initial_score);
314        assert!(final_score >= initial_score);
315    }
316
317    #[test]
318    fn test_vnd_single_neighborhood() {
319        let director = create_nqueens_director(&[0, 0, 0, 0]);
320        let mut solver_scope = SolverScope::new(director);
321
322        let initial_score = solver_scope.calculate_score();
323
324        let values: Vec<i64> = (0..4).collect();
325        let mut phase: VndPhase<_, NQueensMove> = VndPhase::new((create_move_selector(values),));
326
327        phase.solve(&mut solver_scope);
328
329        let final_score = solver_scope.best_score().copied().unwrap_or(initial_score);
330        assert!(final_score >= initial_score);
331    }
332}
solverforge_solver/phase/vnd/phase.rs

solverforge_solver/phase/vnd/
phase.rs
