solverforge_solver/heuristic/move/
ruin.rs

1/* RuinMove - unassigns a subset of entities for Large Neighborhood Search.
2
3This move "ruins" (unassigns) selected entities, allowing a construction
4heuristic to reassign them. This is the fundamental building block for
5Large Neighborhood Search (LNS) algorithms.
6
7# Zero-Erasure Design
8
9Uses typed function pointers for variable access. No `dyn Any`, no downcasting.
10*/
11
12use std::fmt::Debug;
13
14use smallvec::SmallVec;
15use solverforge_core::domain::PlanningSolution;
16use solverforge_scoring::Director;
17
18use super::Move;
19
20/// A move that unassigns multiple entities for Large Neighborhood Search.
21///
22/// This move sets the planning variable to `None` for a set of entities,
23/// creating "gaps" that a construction heuristic can fill. Combined with
24/// construction, this enables exploring distant regions of the search space.
25///
26/// # Type Parameters
27/// * `S` - The planning solution type
28/// * `V` - The variable value type
29///
30/// # Example
31///
32/// ```
33/// use solverforge_solver::heuristic::r#move::RuinMove;
34/// use solverforge_core::domain::PlanningSolution;
35/// use solverforge_core::score::SoftScore;
36///
37/// #[derive(Clone, Debug)]
38/// struct Task { assigned_to: Option<i32>, score: Option<SoftScore> }
39/// #[derive(Clone, Debug)]
40/// struct Schedule { tasks: Vec<Task>, score: Option<SoftScore> }
41///
42/// impl PlanningSolution for Schedule {
43///     type Score = SoftScore;
44///     fn score(&self) -> Option<Self::Score> { self.score }
45///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
46/// }
47///
48/// fn get_task(s: &Schedule, idx: usize) -> Option<i32> {
49///     s.tasks.get(idx).and_then(|t| t.assigned_to)
50/// }
51/// fn set_task(s: &mut Schedule, idx: usize, v: Option<i32>) {
52///     if let Some(t) = s.tasks.get_mut(idx) { t.assigned_to = v; }
53/// }
54///
55/// // Ruin entities 0, 2, and 4
56/// let m = RuinMove::<Schedule, i32>::new(
57///     &[0, 2, 4],
58///     get_task, set_task,
59///     "assigned_to", 0,
60/// );
61/// ```
62pub struct RuinMove<S, V> {
63    // Indices of entities to unassign
64    entity_indices: SmallVec<[usize; 8]>,
65    getter: fn(&S, usize) -> Option<V>,
66    // Set value for an entity
67    setter: fn(&mut S, usize, Option<V>),
68    variable_name: &'static str,
69    descriptor_index: usize,
70}
71
72impl<S, V> Clone for RuinMove<S, V> {
73    fn clone(&self) -> Self {
74        Self {
75            entity_indices: self.entity_indices.clone(),
76            getter: self.getter,
77            setter: self.setter,
78            variable_name: self.variable_name,
79            descriptor_index: self.descriptor_index,
80        }
81    }
82}
83
84impl<S, V: Debug> Debug for RuinMove<S, V> {
85    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
86        f.debug_struct("RuinMove")
87            .field("entities", &self.entity_indices.as_slice())
88            .field("variable_name", &self.variable_name)
89            .finish()
90    }
91}
92
93impl<S, V> RuinMove<S, V> {
94    /// Creates a new ruin move with typed function pointers.
95    ///
96    /// # Arguments
97    /// * `entity_indices` - Indices of entities to unassign
98    /// * `getter` - Function to get current value
99    /// * `setter` - Function to set value
100    /// * `variable_name` - Name of the planning variable
101    /// * `descriptor_index` - Entity descriptor index
102    pub fn new(
103        entity_indices: &[usize],
104        getter: fn(&S, usize) -> Option<V>,
105        setter: fn(&mut S, usize, Option<V>),
106        variable_name: &'static str,
107        descriptor_index: usize,
108    ) -> Self {
109        Self {
110            entity_indices: SmallVec::from_slice(entity_indices),
111            getter,
112            setter,
113            variable_name,
114            descriptor_index,
115        }
116    }
117
118    pub fn entity_indices_slice(&self) -> &[usize] {
119        &self.entity_indices
120    }
121
122    pub fn ruin_count(&self) -> usize {
123        self.entity_indices.len()
124    }
125}
126
127impl<S, V> Move<S> for RuinMove<S, V>
128where
129    S: PlanningSolution,
130    V: Clone + Send + Sync + Debug + 'static,
131{
132    fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
133        // At least one entity must be currently assigned
134        let solution = score_director.working_solution();
135        self.entity_indices
136            .iter()
137            .any(|&idx| (self.getter)(solution, idx).is_some())
138    }
139
140    fn do_move<D: Director<S>>(&self, score_director: &mut D) {
141        let getter = self.getter;
142        let setter = self.setter;
143        let descriptor = self.descriptor_index;
144
145        // Collect old values for undo
146        let old_values: SmallVec<[(usize, Option<V>); 8]> = self
147            .entity_indices
148            .iter()
149            .map(|&idx| {
150                let old = getter(score_director.working_solution(), idx);
151                (idx, old)
152            })
153            .collect();
154
155        // Unassign all entities
156        for &idx in &self.entity_indices {
157            score_director.before_variable_changed(descriptor, idx);
158            setter(score_director.working_solution_mut(), idx, None);
159            score_director.after_variable_changed(descriptor, idx);
160        }
161
162        // Register undo to restore old values
163        score_director.register_undo(Box::new(move |s: &mut S| {
164            for (idx, old_value) in old_values {
165                setter(s, idx, old_value);
166            }
167        }));
168    }
169
170    fn descriptor_index(&self) -> usize {
171        self.descriptor_index
172    }
173
174    fn entity_indices(&self) -> &[usize] {
175        &self.entity_indices
176    }
177
178    fn variable_name(&self) -> &str {
179        self.variable_name
180    }
181}
solverforge_solver/heuristic/move/ruin.rs

solverforge_solver/heuristic/move/
ruin.rs
