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::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::SimpleScore;
34///
35/// #[derive(Clone, Debug)]
36/// struct MySolution {
37///     values: Vec<Option<i32>>,
38///     score: Option<SimpleScore>,
39/// }
40///
41/// impl PlanningSolution for MySolution {
42///     type Score = SimpleScore;
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    /// Creates a new VND phase from a tuple of move selectors.
73    pub fn new(neighborhoods: T) -> Self {
74        Self(neighborhoods, PhantomData)
75    }
76}
77
78/// Generates `Phase` implementations for VndPhase with tuple neighborhoods.
79macro_rules! impl_vnd_phase {
80    // Single neighborhood
81    ($idx:tt: $MS:ident) => {
82        impl<S, D, BestCb, M, $MS> Phase<S, D, BestCb> for VndPhase<($MS,), M>
83        where
84            S: PlanningSolution,
85            D: ScoreDirector<S>,
86            BestCb: BestSolutionCallback<S>,
87            M: Move<S>,
88            $MS: MoveSelector<S, M>,
89        {
90            fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
91                let mut arena = MoveArena::<M>::new();
92                let mut phase_scope = PhaseScope::new(solver_scope, 0);
93                let mut current_score = phase_scope.calculate_score();
94
95                loop {
96                    let mut step_scope = StepScope::new(&mut phase_scope);
97                    arena.reset();
98                    arena.extend((self.0).$idx.iter_moves(step_scope.score_director()));
99
100                    let best_index = find_best_improving_move_index(&arena, &mut step_scope, &current_score);
101
102                    if let Some((selected_index, selected_score)) = best_index {
103                        let selected_move = arena.take(selected_index);
104                        selected_move.do_move(step_scope.score_director_mut());
105                        step_scope.set_step_score(selected_score);
106                        current_score = selected_score;
107                        step_scope.phase_scope_mut().update_best_solution();
108                        step_scope.complete();
109                    } else {
110                        step_scope.complete();
111                        break;
112                    }
113                }
114            }
115
116            fn phase_type_name(&self) -> &'static str {
117                "VariableNeighborhoodDescent"
118            }
119        }
120    };
121
122    // Multiple neighborhoods
123    ($($idx:tt: $MS:ident),+) => {
124        impl<S, D, BestCb, M, $($MS),+> Phase<S, D, BestCb> for VndPhase<($($MS,)+), M>
125        where
126            S: PlanningSolution,
127            D: ScoreDirector<S>,
128            BestCb: BestSolutionCallback<S>,
129            M: Move<S>,
130            $($MS: MoveSelector<S, M>,)+
131        {
132            fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
133                const COUNT: usize = impl_vnd_phase!(@count $($idx),+);
134                let mut arena = MoveArena::<M>::new();
135                let mut phase_scope = PhaseScope::new(solver_scope, 0);
136                let mut current_score = phase_scope.calculate_score();
137                let mut k = 0usize;
138
139                while k < COUNT {
140                    let mut step_scope = StepScope::new(&mut phase_scope);
141                    arena.reset();
142
143                    // Populate arena from neighborhood k
144                    match k {
145                        $($idx => arena.extend((self.0).$idx.iter_moves(step_scope.score_director())),)+
146                        _ => {}
147                    }
148
149                    let best_index = find_best_improving_move_index(&arena, &mut step_scope, &current_score);
150
151                    if let Some((selected_index, selected_score)) = best_index {
152                        let selected_move = arena.take(selected_index);
153                        selected_move.do_move(step_scope.score_director_mut());
154                        step_scope.set_step_score(selected_score);
155                        current_score = selected_score;
156                        step_scope.phase_scope_mut().update_best_solution();
157                        step_scope.complete();
158                        k = 0; // Restart from first neighborhood
159                    } else {
160                        step_scope.complete();
161                        k += 1; // Try next neighborhood
162                    }
163                }
164            }
165
166            fn phase_type_name(&self) -> &'static str {
167                "VariableNeighborhoodDescent"
168            }
169        }
170    };
171
172    // Helper: count tuple elements
173    (@count $($idx:tt),+) => {
174        0 $(+ { let _ = $idx; 1 })+
175    };
176}
177
178/// Finds the index of the best improving move in the arena.
179///
180/// Returns `Some((index, score))` if an improving move is found, `None` otherwise.
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: ScoreDirector<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 = RecordingScoreDirector::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    use solverforge_core::score::SimpleScore;
240
241    type NQueensMove = ChangeMove<NQueensSolution, i64>;
242
243    fn create_move_selector(
244        values: Vec<i64>,
245    ) -> ChangeMoveSelector<
246        NQueensSolution,
247        i64,
248        crate::heuristic::selector::FromSolutionEntitySelector,
249        crate::heuristic::selector::StaticTypedValueSelector<NQueensSolution, i64>,
250    > {
251        ChangeMoveSelector::simple(get_queen_row, set_queen_row, 0, "row", values)
252    }
253
254    #[test]
255    fn test_vnd_improves_solution() {
256        let director = create_nqueens_director(&[0, 0, 0, 0]);
257        let mut solver_scope = SolverScope::new(director);
258
259        let initial_score = solver_scope.calculate_score();
260        assert!(initial_score < SimpleScore::of(0));
261
262        let values: Vec<i64> = (0..4).collect();
263        let mut phase: VndPhase<_, NQueensMove> = VndPhase::new((
264            create_move_selector(values.clone()),
265            create_move_selector(values),
266        ));
267
268        phase.solve(&mut solver_scope);
269
270        let final_score = solver_scope.best_score().copied().unwrap_or(initial_score);
271        assert!(final_score >= initial_score);
272    }
273
274    #[test]
275    fn test_vnd_single_neighborhood() {
276        let director = create_nqueens_director(&[0, 0, 0, 0]);
277        let mut solver_scope = SolverScope::new(director);
278
279        let initial_score = solver_scope.calculate_score();
280
281        let values: Vec<i64> = (0..4).collect();
282        let mut phase: VndPhase<_, NQueensMove> = VndPhase::new((create_move_selector(values),));
283
284        phase.solve(&mut solver_scope);
285
286        let final_score = solver_scope.best_score().copied().unwrap_or(initial_score);
287        assert!(final_score >= initial_score);
288    }
289}
solverforge_solver/phase/vnd/phase.rs

solverforge_solver/phase/vnd/
phase.rs
