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

solverforge_solver/phase/vnd/
phase.rs
