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

solverforge_solver/phase/vnd/
phase.rs
