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

solverforge_solver/phase/vnd/
phase.rs
